전략형 게임
덤프버전 :
분류
시뮬레이션 게임의 일종 '전략 게임'에 대한 내용은 전략 시뮬레이션 문서 참고하십시오.1. 개요[편집]
비협조적 게임 중에서, 경기자(player), 전략집합(strategy set), 보수(payoff)로 구성되어 있는 게임을 말한다. 전개형 게임과 종종 개념적으로 비교되는데 두 게임은 아주 다른 것이 아니라 다만 게임을 표현하는 방식이 다를 뿐이다.
전략형 게임의 목적은 경기자가 다른 경기자의 의사결정까지도 고려하여 자신의 전략을 어떻게 선택할 것인지, 그에 따른 게임의 결과는 무엇인지를 분석하는 것이다.
보통 게임이론을 배울 때 전략형 게임부터 배우므로, 게임이론의 가장 기초적인 개념 역시 전략형 게임을 배울 때 소개되는 편이다. 이 문서에서도 각종 기초 개념을 설명한다.
2. 구성 요소[편집]
전략형 게임을 정의하기 위해서는 먼저 구성 요소를 이해해야 한다. 전략형 게임의 구성 요소는 경기자(player), 전략집합(strategy set), 보수함수(payoff function)이다.
2.1. 경기자[편집]
게임을 하려면 게임에 참여하는 경제주체가 있어야 한다. 이는 단순히 한 사람 개개인뿐만 아니라 단체, 국가, 기업 등도 얼마든지 가능하다. 게임이론에서는 게임에 참여하는 다양한 경제주체를 통틀어 경기자(player)라고 한다. [math(n)]명의 경기자가 참여하는 게임을 [math(\boldsymbol n)]인 게임([math(n)]-person game)이라고 하며, [math(n)]인 게임의 경기자 집합 [math(I)]는 다음과 같다.
분류
경기자의 이름은 표기하기 나름이지만, 구별만 가능하면 되므로 최대한 단순화하자면 위와 같이 자연수로 표기할 수 있는 것이다. 또한 개별 경기자를 가리키는 변수는 [math(i)]로 표시한다.
2.2. 전략, 전략집합, 전략프로필[편집]
게임을 한다는 것은 게임에서 일정한 행위를 취한다는 것으로, 이러한 선택권이 없는 경기자는 게임에 참여한다고 할 수 없다. 따라서 모든 경기자에게는 자신이 선택할 수 있는 대안이 있으며, 게임이론에서는 이를 통틀어 전략(strategy)이라고 한다. 경기자 [math(i)]가 갖는 전략의 집합을 경기자 [math(i)]의 전략집합(strategy set)이라고 하며 [math(S_i)]로 표기한다. 경기자 [math(i)]가 '선택'을 한다는 것은 [math(S_i)]의 원소의 개수가 둘 이상이라는 뜻이다. 또한 [math(s_i\in S_i)]로 표시하여 [math(s_i)]가 경기자 [math(i)]가 택할 수 있는 전략 중 하나임을 나타낼 수 있다.
또한 각 경기자가 택한 전략을 나열해 놓은 것을 전략프로필(strategy profile)이라고 하며 다음과 같이 [math(s)]로 표시한다. 이는 개별 전략들의 순서쌍 또는 벡터 등으로 간주할 수 있는데, 전략프로필은 연산의 대상이 아니므로 벡터로 보기에는 무리가 있으며 '프로필'이라는 표현을 사용하는 것도 그 때문이다.
분류
또한 [math(s)]가 위와 같을 때 경기자 [math(i)] 이외의 경기자의 전략프로필을 다음과 같이 [math(s_{-i})]로 표시한다.
분류
그러면 다시 다음과 같이 쓸 수 있다.
분류
이렇게 표시하는 것의 장점은 전략프로필을 특정 경기자 [math(i)]의 전략과 다른 경기자의 전략으로 나누어 분석할 수 있다는 것이다. 실제로 아래에서 살펴볼 여러 개념들의 정의를 보면 이런 표기법의 필요성을 알게 될 것이다.
한편 가능한 모든 전략프로필을 모아놓은 집합, 즉 전략프로필의 집합 [math(S)] 그리고 경기자 [math(i)] 이외의 경기자들의 전략프로필 [math(S_{-i})]는 다음과 같이 곱집합으로 나타낼 수 있다.
분류
2.3. 보수함수[편집]
보수(payoff)란 경기자가 게임을 진행하고 난 뒤 얻는 편익이다. 소비자의 편익은 효용, 생산자의 편익은 이윤이듯이, 게임이론에서 게임의 경기자가 얻는 편익은 보통 보수라고 표현한다.
각 경기자가 전략을 선택하면 그에 따른 보수가 주어지며 게임은 종료된다. 이러한 전략과 보수의 관계를 함수로 나타낸 것이 바로 보수함수(payoff funciton)이다. 전략프로필이 같아도 그에 따른 보수는 일반적으로 경기자마다 같지 않다. 이에 따라 경기자 [math(i)]의 보수함수는 [math(u_i)]로 표시하며, 다음과 같이 나타낼 수 있다.
분류
즉, 보수함수는 전략프로필의 집합에서 실수의 집합으로 가는 함수로, 경기자들이 저마다 전략을 선택하여 전략프로필이 만들어지면, 그에 따른 보수가 실수 값으로 주어짐을 나타낸다. 은근히 놓치기 쉬운 점은 보수함수는 단일 경기자의 전략의 함수가 아니라 전략프로필의 함수라는 사실이다. 즉, 게임 이론 문서에서도 밝혔듯이 각 경기자가 얻는 보수가 자신의 전략뿐만 아니라 다른 경기자의 전략에도 영향을 받는다는 의미를 담고 있으므로, 보수함수라는 개념의 핵심과도 같다.
보수함수는 [math(u_i(s))]로 쓸 수 있으며, 분석의 편의를 위해 종종 [math(u_i(s_{-i},\,s_i))]로 쓰기도 한다.
3. 전략형 게임의 정의[편집]
구성 요소를 알아 보았으니 이제 전략형 게임을 정의할 수 있다. 경기자 집합 [math(I)], 각 경기자의 전략집합 [math(S_i)], 각 경기자의 보수함수 [math(u_i)]가 주어지면 이를 하나의 전략형 게임(strategic form game)이라고 하며 다음과 같이 표시한다.
분류
경기자의 수 그리고 각 경기자의 전략의 수가 유한하면 특별히 유한 전략형 게임(finite strategic form game)이라고 한다.
게임 이론#대전제 문서에서 밝혔듯이 경기자의 합리성(rationality)과 전략형 게임의 구성 요소는 모든 경기자 간의 공통 지식이다. 이와 같은 전제가 없으면 게임 이론에서 어느 하나 제대로 된 결론을 낼 수 없다.
또한 전략형 게임은 동시선택게임(simultaneous move game)이다. 동시에 선택한다는 것은 정말로 모든 경기자가 동일한 시간에 전략을 선택한다는 의미가 아니며, 단지 각 경기자가 전략을 선택할 때 다른 경기자들이 어떤 전략을 선택하는지 알지 못한다는 의미이다. 경기자들이 순차적으로 전략을 선택하더라도 서로의 전략을 모르면 동시에 선택하는 것이나 다름없다는 점에서 이러한 용어를 사용하는 것이다. 가위바위보를 예로 들면, 모든 경기자의 전략집합은 {가위, 바위, 보}이며, 모든 경기자는 동시에 자신의 전략을 공개해야 한다. 그런데 이렇게 하는 까닭은 서로의 전략을 알지 못하는 상태에서 전략을 결정하게끔 하기 위함이라고 할 수 있다. 따라서 꼭 동일한 시간에 전략을 공개하지 않더라도 상관없다. 가령 모든 경기자가 종이에 다른 사람이 볼 수 없도록 자신의 전략을 써 놓은 다음 한 사람씩 차례대로 공개하더라도 가위바위보의 본질은 변하지 않는다는 것이다. 이런 점에서 가위바위보는 동시선택게임이다.
4. 보수행렬[편집]
일반적으로 전략형 게임은 보수행렬(payoff matrix)로 시각화하여 나타낸다. 전략형 게임을 보수행렬로 옮기면 게임에 대한 분석이 한결 편리해진다. 보수행렬은 각 경기자의 전략과 그에 따른 보수를 표로 나타낸 것으로, 사실상 행렬이라기보다는 표이다. 즉 수학에서 말하는 행렬과는 무관한 개념이다. 수학의 행렬은 연산의 대상이지만 보수행렬은 단지 보수함수를 표로 시각화한 것이기 때문에 연산의 대상이 아니다.
보수행렬을 표시하는 방법을 알아보자. 경기자 1과 2가 각각 [math(m)]개와 [math(n)]개의 전략을 갖고 있는 2인 게임 [math(G)]가
분류
로 주어질 때, 이를 보수행렬로 나타내면 다음과 같다.
단, 보수행렬의 단점은 3인 이상의 게임을 나타내기 어렵다는 것이다. 보수행렬은 2차원이므로 2인까지밖에 포괄하지 못하기 때문이다. 억지로 나타낸다면야 보수행렬 외부에 제3, 제4의 경기자의 전략을 표시해 놓고 그 전략에 따른 보수행렬을 표시할 수는 있으나, 보수행렬을 여러 개 작성해야 하므로 매우 번거롭다. 이 작업은 경기자의 수가 늘어날수록 기하급수적으로 복잡해진다.
5. 전략형 게임의 동등성[편집]
두 전략형 게임 [math(G=\{I,\,\{S_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]와 [math(G'=\{I',\,\{S_i'\}_{i\in I'},\,\{v_i\}_{i\in I'}\})]가 동등하다(equivalent)는 것은 다음을 뜻한다.
- [math(I=I')]: 각 게임에 참여하는 경기자가 동일하다.
- 모든 [math(i)]에 대하여 [math(S_i=S_i')]: 모든 경기자는 각 게임에서 전략집합이 동일하다.
- 모든 [math(i)]에 대하여 [math(u_i=av_i+b)], [math(a>0)]: 두 게임의 보수함수는 상수 [math(a)]와 [math(b)]에 대하여 동족 변환(positive affine transformation) 관계이다.
두 게임의 보수함수는 완벽히 동일할 필요가 없으며, 동족 변환을 통하여 같아질 수 있으면 사실상 같은 것으로 본다. 이는 효용함수의 서수성(ordinality) 때문이다. 즉, 효용함수의 함숫값의 절대적 크기는 아무런 의미를 갖지 못하며 단지 상대적 크기가 경제주체의 선호관계를 설명한다는 것이다. 게임이론의 보수함수 역시 마찬가지로 서수성을 갖는다.
6. 순수전략, 혼합전략[편집]
전략형 게임 [math(G=\{I,\,\{S_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]에서, [math(S_i)]의 원소 하나하나를 순수전략(pure strategy)이라고 한다. 반면 서로 다른 순수전략들 중에서 어느 하나를 확률적으로 선택하는 전략을 혼합전략(mixed strategy)이라고 한다. 좀 더 수학적으로 말하면, 순수전략에 확률 분포를 부여하여 그 확률 분포에 따라 순수전략을 선택하는 것으로, 경기자 [math(i)]의 혼합전략 [math(\sigma_i)]의 정의는 다음과 같다.
분류
즉, [math(\sigma_i)]는 [math(S_i=\{s_{i1},\,s_{i2},\cdots,\,s_{in}\})]에 대한 확률 분포로서, [math(p_j)]는 순수전략 [math(s_{ij})]가 선택될 확률을 뜻한다. [math(p_j)]를 [math(\sigma_i(s_{ij}))]로 쓰기도 하는데, 이는 전략을 선택하는 경기자가 누구인지를 밝히기 위함으로 후자는 전자와 달리 경기자를 특정하는 [math(i)]가 표기에 포함되어 있다.
이 정의에 따르면, 결국 순수전략은 혼합전략의 특수한 경우가 된다. 즉, 순수전략 [math(s_{ij})]는 [math(j)]번째 순수전략을 1의 확률로, 나머지 순수전략을 0의 확률로 선택하는 경기자 [math(i)]의 혼합전략인 것이다.
[math(S_i)]가 주어짐에 따른 경기자 [math(i)]의 혼합전략의 집합은 [math(\Sigma_i)]로 표시한다. 순수전략의 개수가 유한하더라도, 둘 이상이기만 하면 각 순수전략에 배당하는 확률의 조합은 무수히 많으므로, 혼합전략은 무수히 많게 된다.
순수전략과 마찬가지로 각 경기자의 혼합전략을 나열하면 다음의 혼합전략프로필을 얻는다.
분류
또한 혼합전략프로필의 집합은 순수전략프로필의 집합과 마찬가지로 곱집합을 통해 나타낼 수 있다.
분류
이때, 순수전략은 혼합전략의 특수한 경우이므로 [math(S\subset\Sigma)]임은 당연하다.
또한, 전략형 게임을 혼합전략까지 확장하면
분류
로 표시할 수 있다. 또한 순수전략프로필과 마찬가지로, 경기자 [math(i)] 이외의 경기자의 혼합전략프로필은
분류
으로 표시하며, 이에 따라 [math(\sigma=(\sigma_1,\,\cdots,\,\sigma_n)=(\sigma_{-i},\,\sigma_i))]로 쓸 수 있다. 또한 [math(\sigma_{-i})]들을 다 모아놓은 집합을 [math(\Sigma_{-i})]로 표시한다.
6.1. 보수함수의 정의 확장[편집]
혼합전략의 개념을 알았으므로 이제 혼합전략프로필에 대한 보수를 계산하는 방법을 알아보자.
혼합전략프로필 [math(\sigma=(\sigma_1,\,\cdots,\,\sigma_n))]이 선택된 상황에서, 최종적으로 순수전략프로필 [math(s=(s_1,\,\cdots,\,s_n))]이 선택될 확률을 [math(\sigma(s))]로 표시하자. [math(s)]가 선택되려면, 경기자 [math(i)]는 [math(s_i)]를 선택해야 하고 그때의 확률은 각각 [math(\sigma_i(s_i))]이다. 각 경기자의 전략 선택은 독립이므로 각 경기자의 확률을 모두 곱하면 그것이 바로 [math(s)]가 선택될 확률이다. 즉, 다음이 성립한다.
분류
그렇다면 각 경기자가 얻는 보수는 이와 같은 확률을 반영한 기댓값으로 계산해야 한다.
분류
즉, 모든 [math(i)]에 대하여, 경기자 [math(i)]가 혼합전략 [math(\sigma_i)]를 선택하여 혼합전략프로필 [math(\sigma)]가 결정되었으면, 경기자 [math(i)]는 자신이 선택한 혼합전략으로부터 최종적으로 어느 하나의 순수전략 [math(s_i)]를 일정한 확률 [math(\sigma_i(s_i))]로 선택하게 된다. 그 확률들을 모두 곱한 값 [math(\sigma(s))]가 그 순수전략들을 모아놓은 순수전략프로필 [math(s)]가 선택될 확률이다. [math(s)]가 선택되면 그에 따른 보수는 [math(u_i(s))]이므로, 결국 혼합전략프로필 [math(\sigma)]하에서 경기자 [math(i)]가 [math(u_i(s))]의 보수를 받을 확률은 [math(\sigma_i(s_i))]이다. 이러한 계산을 [math(S)]의 모든 원소에 대하여 진행할 수 있으며, 기댓값의 정의에 의하여 최종적인 보수의 기댓값은 다양한 순수전략프로필에 따라 발생할 수 있는 여러 보수를 확률에 대한 가중평균으로 산출한 값이므로 [math(\sum_{s\in S}u_i(s)\sigma(s))]가 되는 것이다.
이상의 설명을 다음 예를 통해 쉽게 이해해 보자.
경기자 1이 [math(a)]를 [math(p)], [math(b)]를 [math((1-p))]의 확률로 사용하는 혼합전략 [math(\sigma_1)]을 사용하고, 경기자 2가 [math(c)]를 [math(q)], [math(d)]를 [math((1-q))]의 확률로 사용하는 혼합전략 [math(\sigma_2)]를 사용한다고 하자. 즉, 다음과 같이 쓰자.
분류
이때, 혼합전략프로필에 대한 각 경기자의 보수 [math(u_1(\sigma_1,\,\sigma_2))]와 [math(u_2(\sigma_1,\,\sigma_2))]를 계산해 보자. 혼합전략 [math(\sigma_1)]과 [math(\sigma_2)]에서, 최종적으로 어떤 순수전략이 선택되느냐에 따라 다른 순수전략프로필 그리고 다른 보수가 주어진다. 따라서 각 보수가 주어질 확률을 계산해야 한다.
그러면 두 경기자의 보수는 다음과 같이 계산된다.
6.2. 보수함수의 성질[편집]
혼합전략프로필에 대한 보수함수를 여러 방법으로 나타낼 수 있다. 먼저 첫째 성질은, 경기자 [math(i)]의 혼합전략 [math(\sigma_i)]에 대한 보수를 여러 순수전략 [math(s_i)]들에 대한 보수의 기댓값으로 나타낸 것이다.
분류
즉, 혼합전략프로필 [math(\sigma)]가 경기자 [math(i)]에게 주는 보수는, 경기자 [math(i)] 이외의 경기자들의 혼합전략프로필 [math(\sigma_{-i})]에 대하여 경기자 [math(i)]가 혼합전략 [math(\sigma_i)]를 선택할 때의 보수와 같다. 그런데 이는 경기자 [math(i)]의 각각의 순수전략 [math(s_i)]가 주는 보수 [math(u_i(\sigma_{-i},\,s_i))]에 그 순수전략이 선택될 확률 [math(\sigma_i(s_i))]를 곱한 값의 총합이다.
둘째 성질은 경기자 [math(i)] 이외의 경기자들의 혼합전략프로필 [math(\sigma_{-i})]에 대한 보수를 여러 순수전략프로필 [math(s_{-i})]들에 대한 보수의 기댓값으로 나타낸 것이다.
분류
즉, 혼합전략프로필 [math(\sigma)]가 경기자 [math(i)]에게 주는 보수는, 경기자 [math(i)] 이외의 경기자들의 혼합전략프로필 [math(\sigma_{-i})]에 대하여 경기자 [math(i)]가 혼합전략 [math(\sigma_i)]를 선택할 때의 보수와 같다. 그런데 이는 다른 경기자들의 각각의 순수전략프로필 [math(s_{-i})]가 주는 보수 [math(u_i(s_{-i},\,\sigma_i))]에 그 순수전략프로필이 선택될 확률 [math(\sigma_{-i}(s_{-i}))]를 곱한 값의 총합이다. 결국, [math(u_i(\sigma))]를 [math(u_i(\sigma_{-i},\,\sigma_i))]로 바꾸어 쓴 것까지는 첫째 성질과 동일하나, 기댓값으로 바꿔 표시하는 부분이 다른 것이다.
이 성질들을 바로 위 문단에서 들었던 다음 예를 통해 쉽게 이해해 보자.
위 문단과 마찬가지로, 다음과 같이 가정하자.
분류
이때, 혼합전략프로필에 대한 각 경기자의 보수 [math(u_1(\sigma_1,\,\sigma_2))]를 보수함수의 성질을 이용하여 계산해 보자. 원리가 동일한 [math(u_2(\sigma_1,\,\sigma_2))]의 계산은 생략한다.
먼저 첫째 성질로 계산해 보자. 첫째 성질은 보수를 계산하고자 하는 경기자의 전략을 어느 한 순수전략으로 고정시켜 보수를 구한 다음, 그 보수들에 해당 순수전략이 선택될 확률을 곱하여 더하는 방법이다.
경기자 1의 보수를 구하는 것이므로, 먼저 경기자 1이 전략을 [math(a)]로 확정한 경우와 [math(b)]로 확정한 경우의 보수를 각각 구하면 다음과 같다.
분류
각 경우는 모두 경기자 2가 [math(c)]를 선택한 경우와 [math(d)]를 선택한 경우를 모두 고려한 기댓값임에 주목하자. 이제 이렇게 계산한 두 경우의 보수에 경기자 1이 해당 순수전략을 선택할 확률을 곱하여 더하면 그것이 경기자 1이 얻는 최종적인 보수의 기댓값인 것이다.
이 값은 위 문단에서 혼합전략프로필로 확장한 보수함수의 정의로 계산했던 값과 일치한다. 이 계산에서
분류
부분을 일반화한 것이 다름 아닌 다음의 첫 번째 성질이다.
분류
이제 둘째 성질로 계산해 보자. 둘째 성질은 보수를 계산하고자 하는 경기자 이외의 경기자들의 전략프로필을 모두 어느 한 순수전략프로필로 고정시켜 보수를 구한 다음, 그 보수들에 해당 순수전략프로필이 선택될 확률을 곱하여 더하는 방법이다.
경기자 1의 보수를 구하는 것이므로, 먼저 경기자 2가 전략을 [math(c)]로 확정한 경우와 [math(d)]로 확정한 경우의 보수를 각각 구하면 다음과 같다.
분류
각 경우는 모두 경기자 1이 [math(a)]를 선택한 경우와 [math(b)]를 선택한 경우를 모두 고려한 기댓값임에 주목하자. 이제 이렇게 계산한 두 경우의 보수에 경기자 2가 해당 순수전략을 선택할 확률을 곱하여 더하면 그것이 경기자 1이 얻는 최종적인 보수의 기댓값인 것이다.
결국 역시 동일한 결과를 얻었다. 이 계산에서
분류
부분을 일반화한 것이 다름 아닌 다음의 두 번째 성질이다.
분류
7. 전략형 게임의 해[편집]
전략형 게임의 해(solution)란, 그 전략형 게임의 결과에 대한 이론적 예측을 말한다. 즉, 전략형 게임의 대전제 아래에서 합리적인 경기자가 선택하는 전략을 말한다. 모든 경기자의 합리적인 전략을 알아내면 하나의 전략프로필이 만들어질 것이며 이것이 바로 전략형 게임의 해이다. 전략형 게임의 해는 언제나 전략프로필임을 유념하자.
전략형 게임의 해를 구하기 위해서는 먼저 여러 개념을 이해해야 하며, 게임의 특성에 따라 해를 구하는 방법도 다르기 때문에 다양한 접근법을 알아야 한다.
7.1. 강우월전략[편집]
다른 경기자들의 전략이 어떠하든지, 항상 자신의 어떤 전략보다도 높은 보수를 가져다주는 전략이 있다면, 합리적인 경기자는 당연히 그 전략을 선택할 것이다. 이러한 전략을 강우월전략(strictly dominant strategy)이라고 한다. 수학적인 정의는 다음과 같다.
즉, [math(\sigma_{-i})]가 어떻게 주어지든지, 경기자 [math(i)]가 자신의 혼합전략집합 [math(\Sigma_i)]에서 혼합전략 [math(\sigma_i^*)]를 선택하는 것이 가장 높은 보수를 가져다준다는 뜻이다.
7.1.1. 성질 1[편집]
그런데 앞서 밝혔듯이 순수전략이 둘 이상이기만 하면 혼합전략은 무수히 많아진다. 따라서 위 정의대로 강우월전략을 찾으려면 무한히 많은 부등식을 비교해야 하는데 이는 불가능하다. 그러나 다음과 같은 강우월전략의 성질을 이용하면 편리하다.
즉, 다루기 까다로운 혼합전략프로필 [math(\sigma_{-i})]를 순수전략프로필 [math(s_{-i})]로 한정하여 생각해도 충분하다는 것이다. 이를 증명하여 보자. 먼저, 순수전략은 혼합전략의 일부이므로 [math(s_{-i})]는 [math(\sigma_{-i})]의 특수한 경우이다. 따라서 2가 성립하면 1도 성립한다. 이제 역을 증명하자. 여기에서는 혼합전략프로필에 대한 보수함수의 성질을 이용해야 한다.
분류
이므로, 1이 성립하면 2도 성립한다. 즉, 1과 2는 필요충분조건 관계이다.
7.1.2. 성질 2[편집]
또한, 강우월전략은 존재하면 반드시 순수전략이다. 순수전략이 아닌 혼합전략은 강우월전략이 될 수 없다. 귀류법으로 증명할 수 있다. 강우월전략 [math(\sigma_i^*)]가 순수전략이 아닌 혼합전략이라고 하자. 그러면 적어도 두 개 이상의 순수전략을 양의 확률로 사용한다는 뜻이며, 그 두 개의 순수전략을 [math(s_i^0)] 그리고 [math(s_i^1)]이라 하자. 즉, [math(\sigma_i^*(s_i^0)>0)]이고 [math(\sigma_i^*(s_i^1)>0)]이다. 강우월전략의 정의에 의하여 모든 [math(\sigma_{-i})] 및 [math(s_i)]에 대하여
분류
이며, 이 부등식의 양변에 [math(\sigma_i^*(s_i))]를 곱하면
분류
가 된다. 강부등호가 약부등호로 바뀐 이유는 [math(\sigma_i^*(s_i)=0)]인 경우가 있기 때문이다. 그러나 [math(\sigma_i^*(s_i^0)>0)]이고 [math(\sigma_i^*(s_i^1)>0)]으로 가정했으므로 [math(s_i^0)] 및 [math(s_i^1)]에 대해서는 다음과 같이 부등식이 강부등호로 성립한다.
분류
따라서 모든 [math(s_i)]에 대하여 ①의 식의 양변을 더하면 다음과 같이 강부등호가 성립한다.
분류
그런데 이 식의 좌변은 다음과 같이 정리할 수 있다.
분류
두 번째 등호가 성립하는 이유는 모든 [math(s_i)]에 대한 확률의 총합은 표본공간의 확률이므로 1이기 때문이다. 그런데 우변도
분류
이므로 결국 [math(u_i(\sigma_{-i},\,\sigma_i^*)>u_i(\sigma_{-i},\,\sigma_i^*))]이라는 모순이 발생한다. 이 모순은 강우월전략 [math(\sigma_i^*)]가 순수전략이 아니라는 처음의 가정이 잘못되었기 때문이며, 결론적으로 강우월전략은 순수전략이다.
7.1.3. 성질 3[편집]
강우월전략은 존재하지 않을 수 있으나, 존재하면 유일하다. 귀류법으로 간단히 증명할 수 있다. 서로 다른 순수전략 [math(\sigma_i^0)]와 [math(\sigma_i^1)]이 모두 강우월전략이라면 정의에 의하여 [math(u_i(\sigma_{-i},\,s_i^0)>u_i(\sigma_{-i},\,s_i^1))]과 [math(u_i(\sigma_{-i},\,s_i^1)>u_i(\sigma_{-i},\,s_i^0))]이 동시에 성립하여야 하는데 이는 모순이다. 직관적으로도, 다른 어떤 전략보다도 가장 높은 보수를 가져다주는 전략은 당연히 유일할 수밖에 없다. '다른 어떤 사람보다도 키가 큰 사람'이 유일한 것과 같은 이치이다.
7.1.4. 성질 4[편집]
즉, 다루기 까다로운 혼합전략 [math(\sigma_i)]를 순수전략 [math(s_i)]로 한정하여 생각해도 충분하다는 것이다. 성질 4는 성질 1과 꽤 유사한데, 증명 역시 성질 1과 마찬가지로 보수함수의 성질을 이용하면 된다. 먼저, [math(s_i)]는 [math(\sigma_i)]의 특수한 경우이므로 1이 성립하면 2도 성립한다. 이제 역을 증명하자. 여기에서 혼합전략프로필에 대한 보수함수의 성질을 이용해야 한다. 그에 따르면
분류
이며, 우변은 결국 각 [math(u_i(s_{-i},\,s_i))]들에 그에 대응하는 1 이하의 값인 확률 [math(\sigma_i(s_i))]를 곱하여 더한 값이므로 2가 성립하면 1도 성립할 수밖에 없다.
7.1.5. 정리[편집]
위 네 개의 성질을 종합하면 다음의 정리가 도출된다.
즉, 위에서 살펴본 정의에서는 모든 경기자의 혼합전략을 고려하여 어떤 혼합전략이 강우월전략인지를 정의했지만, 여러 성질들에 의하여 사실은 강우월전략은 순수전략일 수밖에 없는 데다가 혼합전략 중에서도 순수전략만을 비교해도 충분함이 밝혀진 것이다. 순수전략의 개수가 둘 이상이면 곧바로 개수가 무수히 많아지는 혼합전략과는 달리, 순수전략은 자체로 개수가 유한하기만 하면 조사해야 하는 부등식 또한 유한하므로 이 정리를 사용하면 어떤 전략이 강우월전략인지 판단하는 것이 훨씬 쉬워진다.
7.2. 약우월전략[편집]
약우월전략(weakly dominant strategy)의 정의는 강우월전략의 정의에서 강부등호를 약부등호로 바꾼 것이다. 즉, 강우월전략은 다른 경기자의 전략에 관계없이 그 전략이 나의 다른 어떤 전략보다도 큰 보수를 주는 전략이라면, 약우월전략은 작지 않은 보수를 주는 전략인 것이다. 정의를 엄밀하게 다시 쓰면 다음과 같다.
단, 견해에 따라서는 적어도 하나의 [math(\sigma_{-i})]에 대해서만큼은 강부등호가 성립해야 한다는 조금 더 강한 조건을 요구하기도 한다.
강우월전략의 정의에서는 '다른 모든 혼합전략'이라고 했지만 여기에서는 '모든 혼합전략'이라고 한 이유는, 부등호가 약부등호로 바뀌었으므로 [math(\sigma_i=\sigma_i^*)]일 때 [math(u_i(\sigma_{-i},\,\sigma_i^*)\geq u_i(\sigma_{-i},\,\sigma_i))]가 항상 등호로 성립하기 때문이다. 또한 약우월전략도 강우월전략과 마찬가지로 이 정의보다는 다음의 정리를 사용하는 것이 편리하다. 역시 강부등호가 약부등호로 바뀌고 '다른'이라는 말이 빠진다.
단, 강우월전략의 정리와는 달리 약우월전략의 범위를 순수전략으로 한정하지 않았음에 유념하자. 강우월전략과는 달리, 약우월전략은 순수전략이 아닐 수도 있으며 여러 개가 존재할 수도 있다. 전략프로필에 관계없이 항상 보수가 동일한 게임이 극단적인 예시로서, 약우월전략의 정의가 항상 등호로만 성립하므로 모든 혼합전략이 약우월전략이 된다. 단, 적어도 하나의 [math(\sigma_{-i})]에 대해서 강부등호 조건을 요구한다면 이런 게임에서는 약우월전략이 존재하지 않게 된다.
또 주의할 점은 강우월전략과는 달리 합리적 경기자는 꼭 약우월전략을 선택한다는 보장이 없다는 사실이다. 다음 예를 보자.
경기자 2의 입장에서는 [math(d)]가 강우월전략이 아닌 약우월전략이다. 경기자 1이 [math(a)]를 선택할 때는 [math(d)]가 [math(c)]보다 확실히 더 높은 보수를 주지만, [math(b)]를 선택할 때는 보수가 [math(5)]로 동일하기 때문이다. 경기자 2가 약우월전략 [math(d)]를 선택한다고 하자. 그러면 경기자 1은 [math(a)]를 선택하면 [math(2)], [math(b)]를 선택하면 [math(1)]을 얻으므로 [math(a)]를 선택할 것이다. 그러면 두 경기자는 모두 [math(2)]를 얻는다. 그런데 경기자 2가 [math(d)]가 아닌 [math(c)]를 선택한다고 하면 경기자 1은 이번에는 [math(b)]를 선택하는 것이 유리하다. 그러면 두 경기자는 각각 [math((2,5))]를 얻는다. 결국 경기자 2가 약우월전략 [math(d)]보다는 [math(c)]를 선택하면 보수가 더 커지므로, 약우월전략이 합리적 선택이 아닐 수 있는 것이다.
7.3. 강열등전략[편집]
강우월전략과는 정반대로, 강열등전략(strictly dominated strategy)은 합리적 경기자가 절대로 선택하지 않는 전략이다. 정의는 다음과 같다.
이와 같이 다른 경기자들의 전략에 관계없이 [math(s_i^*)]보다는 [math(\sigma_i)]가 경기자 [math(i)]에게 더 높은 보수를 주는 것을 가리켜 [math(\sigma_i)]가 [math(s_i^*)]를 압도한다(dominate)고 한다. 즉, 모든 [math(s_{-i}\in S_{-i})]에 대하여
분류
가 성립하는 경우를 말한다. 이 경우 합리적 경기자는 [math(s_i^*)]를 결코 선택하지 않는다. 주의할 점은 그렇다고 해서 [math(\sigma_i)]가 꼭 선택된다는 뜻은 아니라는 것이다. [math(\sigma_i)]보다 더 나은 전략이 얼마든지 존재할 수 있으며, [math(\sigma_i)]의 역할은 단지 [math(s_i^*)]를 압도하여 [math(s_i^*)]를 합리적 경기자 [math(i)]의 고려 대상에서 배제하는 것일 뿐이다. 물론 [math(\sigma_i)]가 아예 강우월전략이라면 이보다 더 나은 전략이 없으므로 이 전략이 선택될 것이다. 강우월전략은 해당 경기자의 다른 모든 전략을 압도하는 전략이라고 할 수 있다.
한편, 강열등전략의 정의상 강열등전략은 순수전략에 한해 정의되는 개념이다. 이렇게 정의하는 이유에 대해서는 아래에서 '강열등전략의 반복적 제거'를 논한 뒤 설명한다.
7.3.1. 강열등전략 반복적 제거[편집]
각 경기자의 강열등전략이 발견되는 대로 차례로 제거해 나가는 과정을 강열등전략 반복적 제거(iterated elimination of strictly dominated strategies)라고 하며, 강열등전략 단계적 소거라고도 한다. 다음 예를 보자.
먼저, 경기자 1의 전략 중 [math(a)]와 [math(b)]를 비교하면, 경기자 2의 전략에 관계없이 [math(a)]는 [math(b)]보다 항상 낮은 보수를 경기자 1에게 주므로, [math(a)]는 경기자 1의 강열등전략이며 경기자 1은 절대로 [math(a)]를 선택하지 않는다.
이 사실을 아는 경기자 2 역시 [math(a)]라는 전략을 게임 자체에서 배제하여, 게임을 위와 같이 축소시켜 생각하게 된다. 이때 경기자 1의 전략에 관계없이 [math(d)]는 [math(e)]보다 항상 낮은 보수를 경기자 2에게 주므로, [math(d)]는 경기자 2의 강열등전략이며 경기자 2는 절대로 [math(d)]를 선택하지 않는다.
마찬가지로 이 사실을 아는 경기자 1은 위와 같이 게임을 축소시켜 생각한다. 이제 경기자 2의 전략은 [math(e)]로 확정되었으며, 이 가운데 경기자 1에게는 [math(b)]보다 [math(c)]가 유리하므로 이번에는 [math(b)]가 경기자 1의 강열등전략이 된다. 따라서 최종적으로 이 게임에서 경기자 1은 [math(c)]를, 경기자 2는 [math(e)]를 선택하여 두 경기자 모두 [math(4)]를 얻게 된다.
다시 원래의 게임을 보자. 위 과정에서는 [math(a)], [math(d)], [math(b)]가 차례대로 강열등전략으로서 제거되었지만, 처음 상태 자체에서는 총 다섯 개의 순수전략 중에서 오직 [math(a)]만이 강열등전략이다. [math(d)]의 경우, 경기자 1이 [math(a)]를 선택할 때는 오히려 [math(e)]보다 유리하므로 강열등전략이 아니다. 먼저 [math(a)]를 제거한 뒤에야 [math(d)]가 강열등전략이 되었음을 눈여겨 보자. 마찬가지로 [math(b)] 역시 [math(a)]와 [math(d)]가 먼저 제거된 뒤에야 강열등전략이 되었으며, 그렇지 않은 상태에서는 [math(b)]를 제거할 수 없었음을 이해해야 한다. 즉 원래 그렇지 않았던 전략이 새로이 강열등전략이 되는 원리가 강열등전략 반복적 제거의 위력이다. 이는 마치 스도쿠와 비슷하다. 처음에는 어떤 숫자가 들어갈지 알 수 없는 셀들이 많지만, 다른 셀의 숫자를 알게 됨으로써 추가된 새로운 단서를 통해 하나하나 셀을 채워가는 것이 스도쿠의 묘미이기 때문이다.
한편, 순수전략을 제거하기 위해 순수전략만으로는 충분하지 않아 혼합전략을 도입해야 할 때도 있다. 다음 예를 보자.
위 게임에서는 어떤 순수전략도 다른 순수전략을 압도하지 못한다. 그러나 혼합전략까지 확장한다면 이야기가 달라진다. [math(a)]와 [math(b)]를 각각 [math(1/2)]의 확률로 사용하는 혼합전략 [math(\sigma_1)]을 고려하자. [math(\sigma_1)]이 경기자 1에게 주는 보수는 경기자 2가 [math(d)]를 선택하면 [math(2\times1/2+1\times1/2=3/2)]이고, [math(e)]를 선택하면 [math(1\times1/2+2\times1/2=3/2)]이다. 즉 이 혼합전략은 경기자 2의 전략에 관계없이 [math(3/2)]의 보수를 준다. 그런데 [math(c)]는 경기자 2의 전략에 관계없이 [math(1)]의 보수를 주므로 [math(\sigma_1)]은 [math(c)]를 압도한다. 즉, [math(c)]는 강열등전략으로서 제거된다.
[math(c)]가 제거된 상태에서는 비로소 [math(e)]가 [math(d)]를 압도하므로 [math(d)]가 제거되며 경기자 2의 전략은 [math(e)]로 확정된다. 그 가운데 경기자 1은 [math(b)]가 [math(a)]보다 높은 보수를 주므로 [math(b)]를 선택한다. 따라서 이 게임은 경기자 1은 [math(b)], 경기자 2는 [math(e)]를 선택하여 각각 [math(2)]와 [math(4)]를 얻게 된다.
7.3.1.1. 연열등전략소거해[편집]
강열등전략 반복적 제거를 보다 수학적으로 나타내 보자. 어떤 전략형 게임 [math(G=\{I,\,\{S_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]에 대하여 매 기마다 강열등전략을 제거한다고 하자.
먼저, 모든 [math(i)]에 대하여 [math(S_i^0\equiv S_i)]로 정의하자. 강열등전략을 제거하기 전의 순수전략집합을 '0기'로 표현한 것이다. 이제 0 이상의 정수 [math(t)]에 대하여, 다음과 같이 정의하자.
분류
즉, [math(t)]기까지 강열등전략 반복적 제거를 총 [math(t)]회 실시하고 남은 순수전략의 집합을 [math(S_i^t)]로 쓰는 것이다. 그러면 강열등전략 반복적 제거를 끝까지 실시한 뒤에 최종적으로 남게 되는 순수전략의 집합은
분류
로 쓸 수 있다. 전략형 게임에서 합리적 경기자 [math(i)]가 선택하는 전략은 반드시 여기에 속해야 한다. [math(S_i^0-S_i^1)]에 속한 전략은 1기에서 제거된 강열등전략이며, [math(S_i^1-S_1^2)]에 속한 전략은 1기에는 그렇지 않았으나 2기에 강열등전략이 되어 제거된 전략이다. 1기에서부터 강열등전략이었다면 1기에 이미 제거되어 [math(S_i^0-S_i^1)]에 속했어야 하기 때문이다. 이러한 과정을 반복하면, 합리적 경기자는 모든 [math(t)]에 대하여 [math(S_i^t-S_i^{t+1})]에 속한 전략을 절대 선택하지 않음을 알 수 있다.
일반적으로 [math(\bigcap_{t=1}^\infty S_i^t)]의 원소의 개수는 게임마다, 경기자마다 다르다. 만약 모든 [math(i)]에 대하여 원소의 개수가 하나이면 그 게임은 연열등전략소거해를 갖는다(dominance solvable)고 한다. 정의는 다음과 같이 쓸 수 있다.
연열등전략소거해를 갖는 게임 [math(G)]가 모든 [math(i)]에 대하여 [math(\bigcap_{t=1}^\infty S_i^t=\{s_i^*\})]가 성립하면 [math(G)]의 합리적 경기자들이 순수전략프로필 [math(s^*=(s_1^*,\,\cdots,\,s_n^*))]을 선택할 것을 정확히 예측할 수 있다.
7.3.1.2. 강열등전략이 순수전략인 이유[편집]
눈여겨볼 점은 강열등전략은 정의상 항상 순수전략이라는 것이다. 더 정확히 말하면, 혼합전략으로 확장하여 정의하는 것도 불가능하지는 않으나, 그럴 필요성이 희박하다. 그 이유는 강열등전략 반복적 제거를 통해 설명할 수 있다. 다음 예를 보자.
위 게임에서 경기자 1은 [math(a)]와 [math(b)]를 일정 확률로 사용하는 무수히 많은 혼합전략을 갖고 있다. 이때, 논의의 편의를 위해 [math(c)]는 사용하지 않는다고 생각하자. 강열등전략의 정의를 혼합전략으로 확장하여 강열등전략 반복적 제거를 시행해 보자. [math(a)]를 [math(p_a)], [math(b)]를 [math(p_b)]의 확률로 사용하는 혼합전략 [math(\sigma_1)]에 대한 경기자 1의 보수는 다음과 같다.
분류
이때 [math(0\leq p_a\leq 1)]이므로 다음이 성립한다.
분류
즉, 경기자 1의 모든 [math(\sigma_1)] 중에서 가장 보수가 높은 전략은 [math(p_a)]의 값이 극대화되어 1이 되는 전략, 즉 순수전략 [math(a)]이다. 결국 [math(a)]는 다른 모든 혼합전략을 압도하여 강열등전략으로서 제거되도록 한다. 결국 [math(a)]를 제외한 모든 [math(\sigma_1)]들은 모두 경기자 1의 전략 선택에서 배제된다. 이를 일반적으로 말하면, 서로 다른 보수를 주는 두 순수전략에 대하여, 보수가 낮은 순수전략에 0의 확률을 부여하는 혼합전략, 즉 보수가 높은 순수전략은 보수가 낮은 순수전략에 0이 아닌 확률을 부여하는 모든 혼합전략을 압도한다. 결국 강열등전략 반복적 제거 이후에 살아남는 전략은 어차피 보수가 높은 '순수전략'뿐이다. 따라서 서로 다른 보수를 주는 두 순수전략이 있으면, 순수전략만을 고려하여 보수가 높은 순수전략이 보수가 낮은 순수전략을 압도함에 따라 보수가 높은 순수전략만이 살아남는다고 간주하더라도 무리가 없는 것이다.
7.4. 최적대응, 합리화가능전략[편집]
합리화가능전략이 무엇인지 이해하기 위해서는 우선 최적대응이라는 개념을 알아야 한다. 최적대응(best response; BR)이란 다른 경기자들의 전략프로필이 주어졌을 때 특정 경기자가 자신의 보수를 극대화하기 위해 선택하는 전략을 말한다. 엄밀한 정의는 다음과 같다.
단, 위 정의는 순수전략에 한정한 정의이다. 혼합전략까지 확장한 정의는 추후에 살펴보도록 하자. [math(s_i)]가 [math(\sigma_{-i})]에 대한 최적대응이 아니라면 다른 경기자들이 [math(\sigma_{-i})]를 선택할 때 합리적 경기자 [math(i)]는 [math(s_i)]를 양의 확률로 사용하지 않는다. 나아가, 모든 [math(\sigma_{-i}\in\Sigma_{-i})]에 대하여 [math(s_i)]가 [math(\sigma_{-i})]에 대한 최적대응이 아니라면 합리적 경기자 [math(i)]는 다른 경기자들의 전략에 관계없이 [math(s_i)]를 양의 확률로 선택하지 않는다. 따라서 강열등전략 반복적 제거와 마찬가지로 [math(s_i)]를 고려 대상에서 배제할 수 있는 것이다. 이러한 전략을 비최적대응(never a best response)이라고 한다.
이제 전략형 게임 [math(G=\{I,\,\{S_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]에서, 모든 [math(i)]에 대하여 [math(S_i^0\equiv S_i)], [math(\Sigma_i^0\equiv\Sigma_i)], [math(\Sigma_{-i}^0\equiv\Sigma_{-i})]로 정의하자. 그러면 강열등전략 반복적 제거와 마찬가지로 다음과 같이 정의할 수 있다.
분류
이와 같이 매 기마다 비최적대응을 소거한 뒤 최종적으로 남는 경기자 [math(i)]의 순수전략의 집합은
분류
로 정의되며, [math(R_i)]의 원소를 경기자 [math(i)]의 합리화가능전략(rationalizable strategy)이라고 한다. 강열등전략 반복적 제거와 동일한 이유로, 합리적인 경기자는 반드시 합리화가능전략을 선택한다.
7.4.1. 강열등전략과 비최적대응[편집]
강열등전략은 비최적대응이지만 역은 일반적으로 참이 아니다. 즉, 강열등전략이 더욱 강한 개념이다. 단, 2인 게임에 한해서는 역이 성립하여 강열등전략 반복적 제거와 합리화가능전략을 찾는 과정은 완벽하게 동일하다. 그러나 3인 이상의 게임에서는 강열등전략이 아닌 비최적대응전략이 존재할 수 있다.
7.5. 내시균형[편집]
사실 위에서 살펴본 여러 개념들을 적용할 수 없는 전략형 게임이 대부분이다. 강우월전략이 존재하지 않거나, 연열등전략소거해를 갖지 않거나, 합리화가능전략이 유일하지 않다는 것이다. 위의 방법들로 유일한 전략형 게임의 해를 얻을 수 있는 경우가 오히려 특수한 것이라고 할 수 있다. 실제로 합리화가능전략은 합리적 경기자의 전략에 대한 예측력이 많이 떨어진다. 그렇다면 모든 전략형 게임에 대하여 구체적인 해를 도출하게 해 주는 개념이 필요한데, 그것이 바로 내시균형(Nash equilibrium)으로, 표기에 따라서는 내쉬균형이라고도 한다. 미국의 수학자 존 내시(John Nash)의 이름을 딴 명칭이다.
내시균형에도 경기자들이 순수전략만을 사용하는 순수전략 내시균형(pure strategy Nash equilibrium)이 있고, 이를 혼합전략까지 확장한 혼합전략 내시균형(mixed strategy Nash equilibrium)이 있다. 순수전략 내시균형의 여러 성질은 혼합전략 내시균형에서도 동일하게 성립한다.
7.5.1. 순수전략 내시균형[편집]
즉, 내시균형은 개별 경기자의 전략이 아닌 모든 경기자에 대한 전략프로필이다. 경기자 [math(i)]의 어떤 전략 [math(s_i)]가 내쉬균형인지를 따질 수는 없다. 가령 [math((s_{-i},\,s_i))]가 내시균형이라고 하더라도 [math(({s_{-i}}',\,s_i))]는 내시균형이 아닐 수도 있기 때문이다. 내시균형은 항상 모든 경기자의 전략을 한데 모아놓은 전략프로필임을 명심하자.
또한, 위에서 알아본 최적대응의 정의와 종합하면, 이 내시균형의 정의는 결국 모든 [math(i)]에 대하여 [math(s_i^*)]가 [math(s_{-i}^*)]에 대한 최적대응이어야 한다는 뜻이다. 수학적으로 엄밀하게 쓰면 다음과 같다. [math(s_{-i})]에 대한 경기자 [math(i)]의 최적대응의 집합을 다음과 같이 [math(BR_i(s_{-i}))]로 표시하자.
분류
그러면 순수전략프로필 [math(s^*)]가 내시균형일 조건은 모든 [math(\boldsymbol i)]에 대하여 [math(\boldsymbol{s_i^*\in BR_i(s_{-i}^*)})]인 것이다. 즉 내시균형은 경기자들이 상호 최적대응을 하는 상태로 풀이된다.
7.5.2. 혼합전략 내시균형[편집]
이 정의는 순수전략 내시균형의 정의를 혼합전략으로 확장한 것에 불과하다. 최적대응의 정의와 종합하면 순수전략 내시균형과 동일한 결과를 얻을 수 있다.
[math(s_{-i})]에 대한 경기자 [math(i)]의 혼합전략 최적대응의 집합을 [math(BR_i(\sigma_{-i}))]로 표시하자.
분류
그러면 혼합전략프로필 [math(\sigma^*)]가 내시균형일 조건은 모든 [math(\boldsymbol i)]에 대하여 [math(\boldsymbol{\sigma_i^*\in BR_i(\sigma_{-i}^*)})]인 것이다. 또한, 사실 위 집합의 정의에서 실질적으로는 모든 [math(s_i'\in S_i)]에 대하여 [math(u_i(\sigma_{-i},\,\sigma_i)\geq u_i(\sigma_{-i},\,s_i'))]가 성립하기만 하면 된다.
7.5.3. 함의[편집]
이제 내시균형의 함의를 알아보자. 논의의 편의를 위하여 순수전략 내시균형을 고려하자. 혼합전략 내시균형의 경우 다루는 전략의 범위가 순수전략에서 혼합전략 전반으로 확장될 뿐 내시균형의 함의는 그대로이기 때문이다.
모든 [math(s_i\in S_i)]에 대하여 [math(u_i(s_{-i}^*,\,s_i^*)\geq u_i(s_{-i}^*,\,s_i))]라면, 경기자 [math(i)]는 다른 경기자들이 [math(s_i^*)]를 선택하는 가운데 [math(s_i^*)]를 선택하는 것이 자신의 보수를 극대화하는 길이다. 이는 위에서 살펴본 최적대응의 정의와 일맥상통한다. 이것이 모든 경기자에게 해당하기에, 내시균형이란 한 경기자의 전략이 다른 경기자들의 최적대응이 되는 전략프로필이라고 할 수 있다. 순수전략프로필 [math(s^*)]에서 이탈할 유인이 없다. 경기자 [math(i)]는 기존의 전략 [math(s_i^*)]에서 이탈해 보았자 더 높은 보수를 기대할 수 없기 때문이다. 따라서 모든 경기자는 자신의 전략을 그대로 유지하려 하므로 이런 점에서 균형이라는 표현을 사용하는 것이다.[1]
내시균형이 아닌 전략프로필에서는 적어도 한 경기자가 자신의 전략에서 이탈할 유인을 갖게 된다. 내시균형이 아닌 전략프로필 [math(s^0=(s_1^0,\,\cdots,\,s_n^0))]를 고려하자. 이 전략프로필이 실제로 선택된다고 경기자들이 믿는 순간, 자신의 보수를 극대화하는 데에만 관심이 있는 이기적인(selfish) 경기자들 중 적어도 한 명은 [math(s^0)]에서 이탈하고자 하므로, [math(s^0)]가 선택된다고 믿는 순간 실제로는 절대 선택될 수 없는 모순에 빠진다. 이러한 전략프로필을 두고 합리적 경기자의 전략 선택에 대한 예측이라고 할 수는 없을 것이다.
또한 내시균형만이 최적화(optimization)와 합리적 기대(rational expectation)를 만족시킨다. 이 두 개념의 정의를 이해하기 위해서 먼저 경기자 [math(i)]가 예상(expectation) 혹은 추측(conjecture)하는 다른 경기자들의 전략프로필을 [math(\hat\sigma_{-i})]로 표시하자. 내시균형 [math(\sigma^*=(\sigma_1^*,\,\cdots,\,\sigma_n^*))]는 다음 두 조건을 만족시킨다.
즉, 최적화란 합리적 경기자 [math(i)]는 자신이 예상하는 다른 경기자들의 순수전략프로필 [math(\hat\sigma_{-i})]에 대한 최적대응 [math(\sigma_i^*)]를 사용한다는 의미이다.
즉, 합리적 기대란 예상과 실제가 일치한다는 의미이다. 예상이 실제 게임의 결과와 어긋난다면 이를 합리적이라고 보기 힘들뿐더러, 그러한 예상에 입각하여 제시된 최적대응도 제대로 된 전략으로 보기 어려울 것이다.
이 두 조건을 종합하면 다름 아닌 모든 [math(i)]에 대하여 [math(\sigma_i^*\in BR_i(\sigma_{-i}^*))]라는 내시균형의 성질을 얻는다. 즉 이 두 조건을 만족시키는 전략프로필은 내시균형뿐이다.
합리화가능전략은 최적화는 요구하지만 합리적 기대를 요구하지 않는 개념이기 때문에 내시균형보다 예측력이 떨어진다. 한편, 이 합리적 기대는 비협조적 게임의 대전제인 게임의 구성 요소와 경기자들의 합리성이 공통 지식이라는 것으로부터 도출되지 않는, 별개의 새로운 전제이다. 즉, 내시균형은 게임의 구성 요소와 경기자들의 합리성이 공통 지식이라는 전제뿐만 아니라, 모든 경기자들이 합리적 기대를 갖는다는 것을 추가적으로 전제하는 더욱 강력한 개념인 것이다.
7.5.4. 정리 1[편집]
순수전략 내시균형은 [math(G=\{I,\,\{S_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]에서, 혼합전략 내시균형은 [math(G=\{I,\,\{\Sigma_i\}_{i\in I},\,\{u_i\}_{i\in I}\})]에서 정의되었다. [math(S_i\in\Sigma_i)]이므로 경기자 [math(i)]는 [math(\Sigma_i)]에서 선택의 폭이 더 크다. 그러나 순수전략 [math(s_i)]가 [math(S_i)] 안에서 [math(s_{-i})]에 대한 최적대응이면, 전략의 고려 범위를 [math(\Sigma_i)]로 확장하더라도 여전히 최적대응이다. 이를 증명하여 보자.
먼저 위에서 표기를 약속한 대로, [math(s_i\in BR_i(s_{-i}))]이면 모든 [math(s_i'\in S_i)]에 대하여 [math(u_i(s_{-i},\,s_i)\geq u_i(s_{-i},\,s_i'))]이다. 경기자 [math(i)]의 임의의 혼합전략 [math(\sigma_i)]에 대하여 [math(\sigma_i(s_i')\geq0)]이므로 다음이 성립한다.
분류
[1] 경제학에서 '균형(equilibrium)'의 종류는 실로 다양한데, 그 정의는 외부의 충격이 없는 한 그대로 기존의 상태가 유지되는 것, 또는 그 상태이다.
이 부등식의 양변을 모든 [math(s_i'\in S_i)]에 대하여 합하면 다음과 같다.
분류
[math(\displaystyle\sum_{s_i'\in S_i}\sigma_i(s_i')=1)]이므로 좌변은 다음과 같이 계산된다.
분류
한편 '보수함수의 성질' 문단에서 소개하고 '성질 4' 문단에서 더욱 유사하게 활용한 성질을 도입하면, 우변은 다음과 같이 계산된다.
분류
따라서 ①을 다시 쓰면
분류
이므로, 결론적으로 [math(s_i\in BR_i(s_{-i}))]이면 [math(s_i\in BR_i(\sigma_{-i}))]이다. 즉 순수전략의 범위 내에서 어떤 전략이 최적대응이면, 혼합전략의 범위에서도 최적대응이다. 이 결과는 순수전략 내시균형은 혼합전략 내시균형임을 암시한다. 이 정리는 다음과 같이 쓸 수 있다.
처음에는 순수전략 내시균형과 혼합전략 내시균형을 구별하여 정의했지만, 이 정리를 통하여 순수전략 내시균형이 혼합전략 내시균형의 일종임이 밝혀졌으므로 앞으로는 특별한 이유가 없으면 구별 없이 내시균형이라고만 부르기로 하자.
7.5.5. 정리 2[편집]
내시균형에서 양의 확률로 사용되는 순수전략은 최적대응이다. 즉 내시균형에서는 최적대응이 아닌 순수전략을 사용하는 경기자가 존재하지 않는다. 이를 증명하여 보자. 모든 [math(i)]에 대하여, [math(\sigma_i\in BR_i(\sigma_{-i}))]일 필요충분조건은 [math(\sigma_i(s_i)>0)]이면 [math(s_i\in PBR_i(\sigma_{-i}))]인 것을 증명하면 된다. 쌍조건문(if and only if)이므로 if 조건뿐만 아니라 그 역도 증명해야 하는데, if 조건까지는 귀류법을 사용하고 그 역은 직접증명법을 사용하면 된다.
증명에 앞서 한 가지 표시를 약속하자. [math(BR_i(\sigma_{-i}))]는 [math(\sigma_{-i})]에 대하여 혼합전략 범위에서의 최적대응의 집합이다. 이와는 별도로, [math(\sigma_{-i})]에 대한 순수전략 최적대응만을 모아놓은 집합을 [math(PBR_i(\sigma_{-i}))]로 표시하자.
먼저 if 조건을 증명하자. 증명하고자 하는 명제 자체가 이중 조건문의 복잡한 꼴이어서 명제의 부정을 알기 어려우므로, 우선 다음과 같이 기호화하자.
- [math({\rm A}:\,\sigma_i\in BR_i(\sigma_{-i}))]
- [math({\rm B}:\sigma_i(s_i)>0)]
- [math({\rm C}:s_i\in PBR_i(\sigma_{-i}))]
분류
따라서 우선 [math(\sigma_i\in BR_i(\sigma_{-i}))]에 대하여 [math(\sigma_i(s_i)>0)]이고 [math(s_i\notin PBR_i(\sigma_{-i}))]라고 가정하자. 그러면 최적대응의 정의에 의하여, 어떤 순수전략 [math(s_i^0\in PBR_i(\sigma_{-i}))]에 대하여 [math(u_i(\sigma_{-i},\,s_i^0)>u_i(\sigma_{-i},\,s_i))]이다. 그러나 [math(\sigma_{-i})]에 대하여 [math(\sigma_i)]보다 더 높은 보수를 경기자 [math(i)]에게 주는 혼합전략 [math({\sigma_i}')]을 다음과 같이 만들 수 있다.
- [math(\boldsymbol{{\sigma_i}'({s_i}')=\sigma_i({s_i}')})]
- [math(s_i)]와 [math(s_i^0)] 이외의 순수전략 [math({s_i}')]들은 [math(\sigma_i)]와 동일한 확률로 사용
- [math(\boldsymbol{{\sigma_i}'(s_i)=0})]
- [math(s_i)]는 사용하지 않음
- [math(\boldsymbol{{\sigma_i}'(s_i^0)=\sigma_i(s_i)+\sigma_i(s_i^0)})]
- 대신 원래 [math(\sigma_i)]에서 [math(s_i)]를 사용하는 확률을 [math({\sigma_i}')]에서는 [math(s_i^0)]를 사용하는 확률로 몰아줌
이를 알기 쉽게 표로 나타내면 다음과 같다. 이때, [math({s_i}')]들의 개수는 경기자마다 다를 수 있음에 유의하자.
이렇게 [math({\sigma_i}')]을 만들어 사용하면, 처음에 [math(\sigma_{-i})]에 대한 최적대응으로 가정했던 [math(\sigma_i)]보다도 더 큰 보수를 얻을 수 있다. 즉, 모순이 발생하는 것이다. 그 이유를 알아보자.
우선, 처음의 가정에 따라 [math(u_i(\sigma_{-i},\,s_i^0)>u_i(\sigma_{-i},\,s_i))]임을 앞서 보였다. 즉 [math(s_i^0)]이 [math(s_i)]보다 더 큰 보수를 준다. 그런데 [math({\sigma_i}')]은 [math(\sigma_i)]에 비하여 [math(s_i^0)] 쪽에 사용 확률이 편중되어 있으므로 기대 보수는 더욱 커질 수밖에 없다. 즉, [math(u_i(\sigma_{-i},\,{\sigma_i}')>u_i(\sigma_{-i},\,\sigma_i))]이다. 이는 [math(\sigma_i\in BR_i(\sigma_{-i}))]라는 처음의 가정에 모순된다. 따라서 처음의 가정이 잘못되었으며, 결론적으로 if 조건이 증명되었다.
이제 역을 직접증명법으로 증명하자. 즉, [math(\sigma_i(s_i))]이면 [math(s_i\in PBR_i(\sigma_{-i}))]로 가정하자. 최적대응의 정의에 의하여 [math(s_i\in PBR_i(\sigma_{-i}))]일 때 모든 [math({s_i}'\in S_i)]에 대하여 [math(u_i(\sigma_{-i},\,s_i)\geq u_i(\sigma_{-i},\,{s_i}'))]이다. 이 부등식의 양변에 [math(\sigma_i(s_i))]를 곱하고 모든 [math(s_i)]에 대하여 양변을 더하면 다음이 성립한다.
분류
여기에서 좌변은 위 '보수함수의 성질' 문단에서 밝힌 성질에 따라 다음이 성립한다.
분류
우변은 [math(\sum_{s_i\in S_i}\sigma_i(s_i)=1)]임을 이용하여 다음과 같이 정리할 수 있다.
분류
결국 ①을 다시 쓰면 [math(u_i(\sigma_{-i},\,\sigma_i)\geq\sigma_i(s_i)=u_i(\sigma_{-i},\,{s_i}'))]이므로, 최적대응의 정의에 의하여 [math(\sigma_i\in BR_i(\sigma_{-i}))]임이 증명되었다.
최종적으로 증명한 명제를 다시 밝히자.
앞서 혼합전략프로필 [math(\sigma^*=(\sigma_1^*,\,\cdots,\,\sigma_n^*))]가 내시균형일 조건은 모든 [math(i)]에 대하여 [math(\sigma_i^*\in BR_i(\sigma_{-i}^*))]인 것임을 밝힌 바 있다. 이 명제와 종합하면 다음 정리를 얻는다.
내시균형에서는 어떤 경기자도 최적대응이 아닌 전략을 사용하지 않는다는 이 정리를 이용하면 혼합전략 내시균형을 편리하게 찾을 수 있기 때문에 이 정리의 중요성은 매우 크다.
7.5.6. 정리 3: 내시균형의 존재 정리[편집]
내시균형의 존재 정리는 존 내시가 1951년에 증명한 게임이론에서 가장 중요한 정리로, 유한 전략형 게임은 적어도 하나의 내시균형을 갖는다는 내용이다. 즉, 경기자 수가 유한하고, 경기자들의 전략집합이 유한한 전략형 게임은 항상 내시균형이 존재한다는 뜻이다.
순수전략 내시균형은 존재하지 않을 수도 있지만, 혼합전략 내시균형은 모든 유한 전략형 게임에 대하여 반드시 존재한다. 다음 예를 보자.
순수전략만을 고려해 보면, 경기자 1의 최적대응은 [math(c)]에 대해서는 [math(b)], [math(d)]에 대해서는 [math(a)]이며, 경기자 2의 최적대응은 [math(a)]에 대해서는 [math(c)], [math(b)]에 대해서는 [math(d)]이다. 따라서 어떤 순수전략프로필도 내시균형이 되지 않는다.
그러나 혼합전략까지 고려하면 내시균형을 찾을 수 있다. 이 게임의 내시균형은 두 경기자 모두가 자신의 전략들을 각각 [math(1/2)]의 확률로 사용하는 것이다. 이것이 내시균형임을 보이자. 게임 상황이 대칭적이므로, 어느 한 경기자의 혼합전략이 다른 경기자의 혼합전략에 대한 최적대응임을 보이기만 하면 된다. 경기자 1이 [math(\sigma_1^*=(1/2,\,1/2))]을 선택하고 경기자 2가 [math(\sigma_2=(p,\,1-p))]를 선택한다고 하면 경기자 2의 보수는
분류
로서 [math(p)]의 값에 관계없이 보수가 동일하다. 따라서 경기자 2의 모든 혼합전략이 [math(\sigma_1^*)]에 대한 경기자 2의 최적대응이다. 이는 경기자 1의 최적대응의 경우에도 마찬가지이다. 이제 [math(\sigma_2^*=(1/2,\,1/2))]로 표시하면 내시균형은 [math(\sigma^*=(\sigma_1^*,\,\sigma_2^*))]이다.
또한 유한 전략형 게임이 아니면 내시균형이 존재하지 않을 수도 있다. 예를 들어 두 경기자 1, 2가 다음과 같이 무수히 많은 전략과 그에 따른 보수함수를 갖는다고 하자.
분류
[math(u_1(s_i,\,t_j)=u_2(s_i,\,t_j)=i+j)]
[math(i^0>i^1)]에 대하여 [math(u_1(s_i^0,\,t_j)=s_i^0+t_j>u_1(s_i^1,\,t_j)=s_i^1+t_j)]이므로 [math(s_i^1)]은 [math(s_i^0)]에 의해 압도되는 강열등전략이다. [math(i^1)]의 값을 무엇으로 잡더라도 그것보다 더 큰 [math(i^0)] 때문에 [math(s_i^1)]은 항상 강열등전략이다. 즉, 경기자 1의 모든 전략은 강열등전략이다. 보수함수가 동일한 경기자 2 역시 마찬가지이다. 합리적 경기자는 절대로 강열등전략을 선택하지 않는다. 따라서 내시균형은 존재하지 않는다. 그러나 이는 유한 전략형 게임이 아니므로 내시균형의 존재 정리에 반하는 결과가 아니다.
이 문서의 내용 중 전체 또는 일부는 2023-11-11 23:51:44에 나무위키 전략형 게임 문서에서 가져왔습니다.