「게임이론: 전략과 정보의 경제학」 1장 - 게임의 형태와 해

1. 게임의 구성요소

게임은 '경기자', '경기의 순서', '게임 도중 각 경기자가 알고 있는 지식', '매 시점 각 경기자가 취할 수 있는 전략', '경기자들의 행위로 도출되는 결과', '결과의 실현으로 각 경기자에게 돌아가는 보수'의 여섯 가지 요소로 구성된다.

경기자는 의사결정의 주체로서, 합리성과 일관성을 갖고 사익 추구를 위한 의사결정을 한다. 또한, 경기자는 상대의 합리성을 알고 있으며, 상대가 내가 합리적이라는 사실을 알고 있다는 사실 또한 알고 있다. 이는 상대도 마찬가지이다. 이러한 명제는 무한히 추가되며, 이에 따라 모든 경기자의 합리성은 주지사실이다. 게임이론 내에서는 전략적 의사결정을 내리는 참가자가 아닌 비전략적 경기자의 존재도 가정한다. 자연법칙이 이에 해당한다.

의사결정이 순차적으로 이루어지는 게임은 순차게임이며, 모든 경기자의 의사결정이 동시에 이루어지는 게임은 동시게임이다. 둘을 구별하는 핵심은 경기자가 자신의 전략을 취하는 순간 상대가 어떤 전략을 선택하는 지 아는가의 여부에 있다. 즉, 동시게임은 상대방이 어떤 행동을 할지 모르는 상태에서 자신의 행동을 선택해야 하는 게임을 의미한다.

이 책에서 다루는 게임은 모두 완전회상 하의 게임이다. 모든 경기자들이 게임과 관련된 과거의 정보를 모두 기억하고 있다는 것이다. 게임이론에 있어서 지식 및 정보의 역할과 모형화는 아주 중요하다. 게임이론에서는 각 경기자가 자신의 전략을 선택할 때 상대방이 어떠한 행동을 취했는지 알고 있는지의 여부에 따라 정보를 완전정보와 불완전정보로 구분한다. 상대방 경기자의 특성을 알고 있는지의 여부에 따라 완비정보와 미비정보로 정보를 구분하기도 한다.

의사결정의 상황에서 경기자가 선택할 수 있는 대안들을 행동이라 부른다. 그리고 순수전략은 일어날 개연성이 있는 모든 경우에 대해서 해당 경기자가 취할 행동의 완전한 계획으로 설명된다. 나의 행동 A or B에 따른 상대의 행동 C or D, 그리고 이에 대한 E or F까지의 기승전결을 나타낸 것이다. 혼합전략이란 경기자가 여러 행동 중 하나를 선택하되 주어진 확률분포에 따라 임의로 그것을 선택하는 것을 의미한다.

게임의 결과는 모든 경기자들이 전략을 선택함으로써 나타나는 최종적인 상태이며, 보수란 경기자가 게임을 통해 얻고자 하는 효용이다. 게임이론에서 경기자의 선호체계는 폰 노이만과 모르겐슈테른에 의해 정립된 기대효용가설로 계산된다. 선택의 결과로 x 아니면 y를 얻게 되는 경우, x를 얻을 확률이 p이고 효용함수가 u(x)라면 해당 경기자가 선택을 통해 얻는 효용은 Eu = p × u(x) + (1 - p) × u(y)로 계산되며, 이렇게 계산된 효용을 기대효용이라 한다. 결국, 게임이론에서 보수는 곧 폰 노이만-모르겐슈테른 기대효용이다.

 

2. 게임의 형식

(1) 전개형

전개형게임은 게임의 여섯 가지 구성요소를 모두 명시한 게임나무로 정의된다. 게임나무는 마디와 가지로 이루어진 그래프의 일종인데, 경기자 중 누군가가 자신의 전략을 결정해야 하는 상태인 의사결정마디와, 게임의 최종결과가 실현되어 모든 경기자들에게 결과에 상응하는 보수가 지불되는 상태인 종결마디로 분류된다. 하나의 가지가 출발하는 마디는 도착하는 마디의 선도마디이며, 반대로 그 가지가 도착하는 마디는 출발하는 마디의 후계마디이다.

(2) 전략형

전략형게임은 경기자, 전략, 보수의 세 가지 구성요소만을 갖춘 형태인 게임으로, 이 경우에는 선택의 순서나 정보의 완전성 여부를 알 수 없다. 일반적으로 전략형 게임은 보수행렬의 형태로 표현한다. n인전략형게임에서 경기자i가 선택할 수 있는 순수전략은 si로 표기하며, 경기자i가 선택할 수 있는 순수전략을 전부 모은 순수전략의 집합은 Si로 표기한다. 이 경우 모든 경기자의 순수전략조합을 전부 모은 순수전략조합집합은 S = S1 × S2 × … × Sn이다. 경기자 i의 보수함수 ui: S → R는 특정한 순수전략조합이 실현되었을 때 경기가 i가 얻는 효용을 나타낸다. 이때, 전술한 것은 타인의 선택과 무관한 상황에서의 함수이고, 타인의 선택에 의해 영향을 받는 경우 개인 i의 보수함수는 ui: Si × S-i → R이다. 여기서 -i는 경기자 i를 제외한 나머지 n - 1명의 참가자를 뜻한다. 또한, 보수벡터는주어진 순수전략조합 s에 대하여 경기자들의 보수를 배열해 놓은 벡터 u(s) = (u1(s), u2(s), …, un(s))이다.

 

3. 게임의 해

합리적인 경기자가 어떠한 전략을 선택할 것인가를 예상하는 것은 게임 분석의 핵심이다. 주어진 게임에서 해란 그 게임에 참여하는 합리적 경기자가 선택할 것으로 예상되는 전략조합 혹은 결과를 의미한다. 경기자가 합리적이라면 반드시 선택할 것으로 예상되는 전략을 우월전략이라 한다. 반면 절대로 선택하지 않을 전략은 열등전략이라 한다. 

 

4. 우월전략과 열등전략

죄수의 딜레마 게임은 다음과 같은 상황으로 구성된다. A와 B 두 명의 죄수가 취조당하는 상황에서, 둘 모두 범행을 부인하면 둘 다 2년의 형기를 받고, 둘 모두 자백을 하면 둘 다 4년 동안 수감된다. 만약 B가 자백했는데 A가 범행을 부인할 경우 B는 집행유예, A는 5년 동안 수감된다. 반대의 경우도 같다. 즉, 죄수의 딜레마는 타인을 희생시켜 자신이 이익을 보는 구조로 설명이 가능하다. 아래 표에는 A, B 두 경기자가 취할 수 있는 행동의 선택지가 주어져 있고, 각각이 선택한 전략에 따른 이익이 나타나 있다.

	B:부인	B: 자백
A: 부인	A:3 / B:3	A:0 / B:5
A: 자백	A:5 / B:0	A:1 / B:1

 

위 상황에서, B가 부인할 경우 A는 자백하는 것이 최선이다. B가 자백할 경우에도 A는 함께 자백하는 것이 최선의 전략이다. 즉, 이 상황에서 두 용의자는 언제나 자백하는 것이 최적 행동이다. 이처럼 상대가 어떤 전략을 취하든 나의 전략 중에서 가장 높은 보수를 주는 전략을 강우월전략이라고 한다. 반면 강열등전략은 상대가 어떤 전략을 취하든 그것보다 더 높은 보수를 주는 대안전략이 있음을 의미한다. 결론적으로, 죄수의 딜레마 게임의 유일한 해는 (자백, 자백)일 것이다. 물론 (부인, 부인)은 둘 모두에게 더 높은 보수를 가져다주지만, 상대가 합리적인 한 상대방을 믿을 수 없기에 이는 달성될 수 없는 조합이다. 이러한 점에서, 죄수의 딜레마는 사적 이익의 극대화와 사회적 최적 간의 괴리로 설명된다. 

강우월전략과 강열등전략의 정확한 정의는 다음과 같다. 또한, 정의 1.1의 부등호  ＞와 ＜를 ≥와 ≤로 대체하면 각각 약우월전략과 약열등전략의 정의가 된다. 이를테면, 위 그림에서 A가 광고를 하지 않고 B가 광고를 하는 경우의 A의 보수가 30이라면, A에게 광고를 하는 것은 약우월전략이다.

정의 1.1
① 경기자1의 어떠한 전략 s₁ (≠ s₁*)과 경기자2의 어떠한 전략s₂에 대해서도 u1(s₁*, s₂) ＞ u₁(s₁, s₂)을 만족하는 전략 s₁*가 존재한다면, 그러한 s₁*를 경기자1의 강우월전략이라 정의한다.
② 경기자2의 어떠한 전략 s₂에 대해서도 u₁(s₁",s₂) ＜ u₁(s₁', s₂)을 만족하는 s₁'가 존재한다면, 전략 s₁"을 경기자1의 강열등전략이라 정의한다.

5. 열등전략의 단계적 소거

합리적 경기자는 강열등전략을 택하지 않을 것이다. 죄수의 딜레마 게임을 고려해보자. 부인은 강열등전략이므로 용의자 A는 이를 선택하지 않을것이다. 또한, 용의자 B도 부인 전략을 선택하지 않을 것이다. 결국 남는 것은 둘 모두 자백 전략을 선택하는 조합이다. 이렇게 강열등전략을 하나씩 제거해 나가는 과정을 강열등전략의 단계적 소거라고 부른다. 이를 단계적으로 소거한 후 최후까지 남는 전략을 합리화전략이라고 부르기도 한다. 만약, 강열등전략을 끝까지 소거했을 때 최후에 남는 순수전략조합이 단 하나밖에 없다면 그러한 게임을 우월전략해가 존재하는 게임이라 부르며, 죄수의 딜레마도 이에 속한다. 이러한 과정을 약열등전략에도 도입할 수 있겠지만, 경기자들이 보수 구조에 대해 불확실성을 갖는 경우에는 이를 적용할 수 없다. 또한, 약열등전략의 단계적 소거는 소거 순서에 따라 최종 결과가 달라질 수도 있으므로 일관성있는 예측이 어렵다.

 

6. 순수전략 내쉬균형

대부분의 게임에는 우월전략이나 열등전략이 존재하지 않기에, 어떠한 게임이 주어지든 보편적으로 적용할 수 있는 개념인 내쉬균형이 필요하다. 열등전략이 존재하지 않는 게임(e.g. 사슴사냥게임)에서 다른 경기자들이 현재의 전략을 고수한다고 가정할 때, 주어진 전략조합하에서는 어느 누구도 현재의 전략으로부터 이탈할 유인이 없고, 이러한 안정적 상태를 내쉬균형이라 부른다. 내쉬균형에 대한 엄밀한 정의는 아래와 같다. 상대방의 전략에 대한 최선의 응수, 즉 상호최선응수라는 것이다. 사슴사냥게임과 같이 내쉬균형이 둘일 수도 있고, 우월전략해가 존재하는 죄수의 딜레마 게임에서는 우월전략해가 유일한 내쉬균형이 된다.

정의 1.2
[2인게임] 다음 조건을 만족하는 순수전략조합 (s₁*,s₂*)을 순수전략 내쉬균형이라고 한다. 
어떠한 s₁ ∈ S₁에 대하여도 u1(s₁*, s₂*) ≥ u1(s₁, s₂*)이면서, 동시에
어떠한 s₂ ∈ S₂에 대하여도 u₂(s₁*, s₂*) ≥ u2(s₁*, s₂)임.

정의 1.3
[n인게임] 다음 조건을 만족하는 순수전략조합 s* = s₁*,s₂*, …, sn*)을 순수전략 내쉬균형이라고 한다. 
모든 i = 1, 2, …, n과 어떠한 si ∈ Si에 대해서도 ui (si*, S-i*) ≥ ui (si, S-i*)

7. 여러 2×2 전략형게임