한 형사가 강도 사건을 조사하고 있습니다. 꼼꼼한 수사와 끈질긴 추적을 통해 그는 피의자를 두 명으로 좁히는데 성공하였습니다. 현재까지 얻은 증거로는 각각에게 일 년의 징역형을 줄 수 있는 수준입니다. 그렇지만 드러난 피해로 보건데 이는 두 피의자에게 각각 오 년의 징역형을 줄 수 있는 매우 중대한 범죄였습니다. 다만 아직 이 혐의를 완벽히 입증할 증거를 발견하지 못한 상태였습니다. 자백을 얻기 위해 형사는 피의자를 모두 불러 심문하였습니다. 때로는 무섭게 겁을 주기도 하고, 또 때로는 어르고 달래도 봤지만, 서로 말을 잘 맞추었는지 두 피의자 모두 모르쇠로 일관하였습니다. 이대로면 둘 다 일 년 형만 받고 끝날 것이었습니다.
별다른 진전 없이 시간만 흘러 형사의 속이 타들어 가던 중 그는 문득 묘안을 떠올립니다. 형사가 피의자 A를 따로 불러 다음과 같이 얘기합니다.
너희 둘 다 지금 오 년 형의 범죄로 입건된 것은 알고 있지? 여기서 제안을 하나 하지. 만약에 네가 자백을 한다면 지금의 일 년 형은 없던 것으로 쳐 줄게. 근데 만약 네가 끝까지 함구하는데 B가 자백을 한다면 넌 그의 형량까지 받아서 총 십 년의 징역을 살아야 될 거야.
형사는 같은 제안을 피의자 B에게도 합니다. 과연 피의자 A와 B는 각각 어떤 선택을 하게 될까요?
피의자들이 받은 제안을 표로 나타내면 다음과 같습니다. 괄호 안에서 왼쪽의 값은 A가 받게 될 형량이고, 오른쪽의 값은 B가 받게 될 형량입니다.
| A 함구 | A 자백 | |
| B 함구 | (-1, -1) | (0, -10) |
| B 자백 | (-10, 0) | (-5, -5) |
A의 입장에서 먼저 생각해 봅시다. 만약 B가 함구한다면, 무엇이 A에게 유리할까요? A가 똑같이 함구한다면 A는 일 년 형에 처해질 것입니다. 반대로 자백을 한다면 A는 곧장 풀려날 것입니다. 그러므로 B가 묵비하는 경우 A는 자백하는 것이 그에게 이득입니다. 반대로 B가 자백을 하는 경우는 어떻게 될까요? 이때 A가 함구한다면 A는 십 년 형을 살아야 합니다. 반대로 A도 자백을 한다면 오 년의 형량을 받겠죠. 따라서 이때도 A는 자백하는 것이 이득입니다. 그러므로 A는 B가 어떤 선택을 하든지 자백을 하는 것이 그에게 이득이 됩니다.
B의 입장에서도 생각해 보면, A가 어떤 선택을 하든지 자백을 하는 것이 그에게 이득이 되는 것을 쉽게 알 수 있습니다. 따라서 두 피의자가 모두 합리적(혹은 이기적)이라면, 둘 다 모두 자백을 할 것입니다. 둘 다 함구한다면 각자 일 년씩만 갔다올 텐데 결국 오 년씩 갔다오게 되었으니 어찌 보면 매우 비합리적인 결과라고 할 수 있겠습니다.
위 예시는 게임 이론의 대표격인 문제 중 하나인 죄수의 딜레마(prisoner's dillema)를 나타낸 것입니다. 여기서 우리는 각 피의자의 입장에서 자백을 하는 것이 상대가 어떤 전략을 사용하든지 간에 최대의 효용(즉, 최소의 형량)을 준다는 것을 알 수 있었습니다. 이 개념을 좀더 확장해 보도록 하겠습니다.
총 \(n\) 명의 사람이 참가하는 게임을 하나 생각해 봅시다. 각 참가자 \(i\)는 자신이 사용할 수 있는 전략의 집합 \(S_i\)와 모든 참가자들이 전략을 정했을 때 자신이 얻는 효용 \(u_i : S_1 \times S_2 \times \cdots \times S_n \to \mathbb{R}\)을 갖습니다. 즉, 참가자 1이 \(x_1 \in S_1\), 참가자 2가 \(x_2 \in S_2\), …, 참가자 \(n\)이 \(x_n \in S_n\)을 선정했다면, 각 참가자 \(i\)가 얻는 이득은 \(u_i (x_1, x_2, \cdots, x_n) \)이 됩니다. 모든 참가자는 서로의 전략 집합과 효용 함수가 무엇인지 잘 알고 있습니다. 게임은 각 참가자가 자신의 전략을 공개하는 단판 형식으로 진행됩니다. 이때 참가자들은 모두 개인적이고 합리적(혹은 이기적)입니다. 다시 말하면 참가자들은 서로 독립적으로 행동하며 자신의 효용을 최대로 만드는 전략을 추구한다는 뜻입니다.
어떤 참가자 \(i\)를 고정하겠습니다. 만약 다른 참가자들이 어떤 전략을 취하든지 자신의 효용을 최대로 만드는 전략이 있다면, 참가자 \(i\)는 분명 해당 전략을 채택할 것입니다. 이 상황을 좀더 엄밀히 설명해 보겠습니다. 다른 참가자들이 각자 \(x_1, \cdots, x_{i - 1}, x_{i + 1}, \cdots, x_n\)을 각자의 전략으로 제출했다고 가정합시다. 만약 참가자 \(i\)에게 자신의 다른 어떤 전략 \(x_i \in S_i\)에 대해서도 \[ u_i(x_1, \cdots, x_{i - 1}, x^*_i, x_{i + 1}, \cdots, x_n) \geq u_i(x_1, \cdots, x_{i - 1}, x_i, x_{i + 1}, \cdots, x_n) \] 을 만족하는 전략 \(x^*_i\)가 존재한다면, 참가자 \(i\)는 분명 \(x^*_i\)를 자신의 전략으로 채택한다는 뜻입니다. 이러한 전략을 우리는 참가자 \(i\)의 우월 전략(dominant strategy)이라고 부릅니다.
이제 모든 참가자에게 각자의 우월 전략이 존재한다고 하겠습니다. 그러면 모든 참가자들은 각자 자신의 우월 전략을 채택할 것입니다. 이 상황에서는 어느 누구도 자신의 전략을 수정하려고 하지 않을 것입니다. 다시 말해 균형(equilibrium)의 상태에 들었다고 말할 수 있습니다. 이렇게 참가자들의 전략과 각자가 얻는 효용이 모두 공개된 게임에서 각 참가자에게 모두 자신의 우월 전략이 존재하여 모두 우월 전략을 제출하여 균형을 이루는 상태를 우월 전략 균형(dominant strategy equilibrium)이라고 부릅니다.
위 죄수의 딜레마에서 우리는 각 피의자의 입장에서 자백을 하는 것이 다른 피의자가 어떻게 행동하든지 자신의 효용을 최대로 만드는 행동이라는 사실을 보였습니다. 다시 말해, 두 피의자는 각자 자백을 하는 것이 자신의 우월 전략이라는 뜻이죠. 따라서 모두 자백을 하여 각자 오 년 형을 받는 것이 우월 전략 균형이 됩니다. 아이러니하게도 게임 이론의 입장에서 죄수의 딜레마는 우월 전략 균형이 존재하므로 전혀 딜레마가 아닙니다.
모든 게임에 우월 전략 균형이 존재한다면 각 참가자는 그다지 머리 아플 일이 없습니다. 다시 말해, 어떤 방식으로든 우월 전략을 찾기만 한다면 그 전략을 제출하면 되기 때문이죠. 하지만 세상은 그다지 단순하게 동작하지 않습니다. 다음의 예시를 살펴 보겠습니다. 이 예시는 죄수의 딜레마와 마찬가지로 매우 유명한 게임 이론 문제인 치킨 게임(chicken game)을 설명한 것입니다.
앞에서 피의자로 입건된 A와 B는 사실 오랜 라이벌 관계였나 봅니다. 언젠가 그들은 누가 더 대담하고 용감한지를 겨루기 위하여 다음의 멍청한 대결을 펼치기로 합니다. 어떤 직선 도로의 양 끝에서 A와 B는 각자의 자동차를 타고 서로 마주보며 대기합니다. 출발 신호가 떨어지면 둘은 서로를 향해 전속력으로 돌진합니다. 여기서 두 사람에게는 각자 두 가지 선택지가 있습니다. 하나는 그대로 밀고 나가는 것이고, 다른 하나는 피하는 것이죠. 만약 두 사람 중 한 사람은 그대로 돌진하고 다른 사람은 피한다면, 돌진한 사람은 승리하고 피한 사람은 패배합니다. 반대로 둘 다 피한다면 서로 비기게 되지요. 만약 둘 다 그대로 돌진하면 어떻게 될까요? 그러면 큰 사고가 날 것이고 두 사람 모두 치명적인 부상을 입게 될 것입니다. 과연 이 상황에서 두 사람의 전략은 각자 어떻게 될까요?
이전에 죄수의 딜레마를 소개할 때 했던 것처럼 위 상황에 대해 각자의 전략에 따라 두 사람이 얻게 될 효용을 표로 나타내면 다음과 같습니다.
| A 돌진 | A 회피 | |
| B 돌진 | (-10, -10) | (-1, 1) |
| B 회피 | (1, -1) | (0, 0) |
A의 입장에서 먼저 생각해 보겠습니다. 만약 B가 그대로 돌진한다면 A는 똑같이 돌진해서 큰 부상을 입어 -10의 효용을 얻기 보다는 순간의 굴욕으로 -1의 효용을 얻을지언정 회피를 하는 것이 현명한 선택입니다. 반대로 B가 회피한다면 A는 같이 회피하여 0의 효용을 얻을 바에 돌진하여 승리의 영광을 차지하는 것이 옳은 선택이 되겠죠. B의 입장에서도 동일하게 A가 돌진하면 회피하는 것이, A가 회피하면 돌진하는 것이 자신에게 이득이 되는 행동입니다. 따라서 두 사람 모두 상대가 무슨 전략을 취하든 상관 없이 최대의 효용을 주는 전략은 존재하지 않습니다. 즉, 이 게임에서는 우월 전략 균형이 존재하지 않습니다.
대신 이 게임의 진행 방식을 다음과 같이 약간 바꾸어 보겠습니다. 두 사람은 자동차에 탑승하기에 앞서 각자 서로의 전략이 무엇인지 알려 줍니다. 각자 자동차에 탑승한 후 그들은 앞서 말한 전략을 바꾸는 것이 좋을지 생각합니다. 예를 들어 보죠. 탑승 전에 A와 B가 모두 돌진하겠다고 호언장담했다고 합시다. A의 입장을 고려해 보면, 만약 B가 자신의 전략을 바꾸지 않는다면, A는 회피를 하는 것이 자신에게 이득이 됩니다. 똑같이 B의 입장에서도, 만약 A가 전략을 바꾸지 않는다면, B는 전략을 바꾸어 회피를 하는 것이 이득이 되는 상황입니다. 따라서 A와 B가 탑승 전에 돌진하겠다고 얘기했다면 (상대의 말을 믿었을 때) 자신의 전략을 바꾸는 것이 서로에게 이득이 됩니다. 그러므로 이는 균형의 상태라고 말할 수 없습니다. 비슷한 이치로 A와 B가 모두 회피하겠다고 말한 상황도 자신의 전략을 바꿀 유인이 있으므로 균형이 깨집니다.
이번에는 A는 돌진하겠다고 하고 B는 회피하겠다고 말한 경우를 생각해 봅시다. A의 입장에서 만약 B의 말을 그대로 믿는다면 A는 그대로 자신의 전략을 밀어 붙이는 게 이득이 됩니다. 반대로 B의 입장에서도 만약 B가 A의 말을 그대로 믿는다면 B 또한 자신이 예고한 대로 회피를 하는 것이 이득입니다. 따라서 이 상황에서는 혼자서는 자신이 예고한 전략을 바꿀 유인이 없으므로 균형 상태에 들었다고 얘기할 수 있겠습니다. 비슷한 이유로 A가 회피하겠다고 말하고 B가 돌진하겠다고 말한 경우에도 혼자서는 전략을 바꿀 인센티브가 없으므로 균형에 들었다고 볼 수 있습니다.
이 논의를 일반화하면 다음과 같습니다. 앞에서 본 일반적인 게임을 다시 고려해 봅시다. 대신 이번에는 게임의 룰을 약간 바꾸어 각 참가자 \(i\)가 동시에 자신의 전략 \(x^*_i \in S_i\)를 공개했다고 합시다. 그 후, 게임의 진행자가 참가자들에게 한 명씩 개인적으로 전략을 바꿀 것인지를 묻습니다. 이때 만약, 어떤 참가자 \(i\)의 입장에서 자신의 임의의 전략 \(x_i \in S_i\)에 대해 \[ v_i (x^*_1, \cdots, x^*_{i - 1}, x^*_i, x^*_{i + 1}, \cdots, x^*_n) \geq v_i (x^*_1, \cdots, x^*_{i - 1}, x_i, x^*_{i + 1}, \cdots, x^*_n) \]을 만족한다면 이 참가자는 자신의 전략을 굳이 바꿀 이유가 없습니다. 따라서 모든 참가자에 대해 위 조건이 만족한다면 누구도 자신의 전략을 바꿀 유인이 없으므로 균형에 이르렀다고 말할 수 있습니다. 이렇게 각 참가자의 전략이 공개되었을 때 어떤 참가자도 혼자서는 전략을 바꿀 유인이 없는 상태를 우리는 내쉬 균형(Nash equilibrium)이라고 부릅니다.
얼핏 보기에는 우월 전략 균형과 내쉬 균형이 서로 비슷해 보입니다. 하지만 두 개념에는 큰 차이점이 하나 있습니다. 바로 특정 상황의 가정 여부입니다. 쉽게 말해, 우월 전략 균형에서 각 참가자는 다른 참가자들이 어떻게 행동하는지 알 필요가 없습니다. 그들이 어떤 전략을 취하든지 간에 자신의 전략이 우월 전략이라면 항상 최대의 효용을 제공할 것이기 때문입니다. 반면 내쉬 균형에서 각 참가자는 자신의 전략을 포함해 다른 참가자들의 전략이 무엇인지 알아야 합니다. 모든 참가자들의 전략을 알았을 때 본인의 전략만을 수정해서는 더 좋은 효용을 얻을 수 없을 때가 곧 내쉬 균형이 됩니다.
이제까지는 각 참가자들이 하나의 전략을 결정론적으로(deterministically) 정하는 경우만을 생각했습니다. 이러한 전략을 게임 이론에서는 순수 전략(pure strategy)이라고 부릅니다. 하지만 어떤 참가자가 자신의 수를 정해진 대로만 고른다면 이 참가자는 게임에서 좋은 결과를 얻기 어려울 것입니다. 따라서 어떤 확률 분포에 따라 자신의 전략을 고르는 방법을 생각해 볼 수 있습니다. 이러한 전략을 게임 이론에서는 혼합 전략(mixed strategy)이라고 부릅니다.
앞에서 본 균형 개념들을 혼합 전략에 대해서도 쉽게 확장할 수 있습니다. 이제는 각 참가자 \(i\)가 전략의 집합 \(S_i\) 위에서 정의된 어떤 확률 분포 \(D_i\)에 따라 자신의 전략을 정합니다. 이때 \(D_i\)가 곧 참가자 \(i\)의 혼합 전략이 되겠습니다. 따라서 각 참가자 \(i\)가 선정하는 전략 \(X_i \sim D_i\)는 확률 변수입니다.
이때 참가자 \(i\)의 우월 전략 \(X^*_i \sim D^*_i\)는 다음과 같이 정의가 됩니다. 이 참가자를 제외한 다른 참가자 \(j \neq i\)가 어떠한 분포 \(X_j \sim D_j\)을 갖든지 간에 자신이 취할 수 있는 임의의 혼합 전략 \(X_i \sim D_i\)에 대해 \[ \mathbb{E}[ u_i (X_1, \cdots, X_{i-1}, X^*_{i}, X_{i + 1}, \cdots, X_n) ] \geq \mathbb{E} [ u_i(X_1, \cdots, X_{i - 1}, X_i, X_{i + 1}, \cdots, X_n) ] \]를 만족한다면 \(D^*_i\)는 우월 전략이 됩니다.
반대로 모든 참가자 \(j\)가 \(X^*_j \sim D^*_j\)를 각자가 채택한 혼합 전략이라는 것을 알았을 때, 어느 한 참가자 \(i\)가 혼자서 전략을 \(X_i \sim D_i\)로 바꿔서는 항상 \[ \mathbb{E} [ u_i (X^*_1, \cdots, X^*_{i - 1}, X^*_i, X^*_{i + 1}, \cdot, X^*_n) ] \geq \mathbb{E} [ u_i (X^*_1, \cdots, X^*_{i - 1}, X_i, X^*_{i + 1}, \cdots, X^*_n) ] \]을 얻게 된다면 우리는 \( (D^*_1, \cdots, D^*_n) \)을 내쉬 균형이라고 부릅니다.
예시로 치킨 게임에서 A와 B가 각각 \(\frac{1}{10}\)의 확률로는 돌진하고 \(\frac{9}{10}\)의 확률로는 회피한다고 해 보겠습니다. 서로의 전략을 들은 후 A가 \(x\)의 확률로 돌진하고 \(1 - x\)의 확률로 회피하는 전략을 혼자서 세웠다고 합시다. B가 자신의 전략을 바꾸지 않는다면, A의 기대 효용은 \[ \mathbb{E}[u_A] = \frac{x}{10} \cdot (-10) + \frac{9x}{10} \cdot (1) + \frac{1- x}{10} \cdot (-1) + \frac{9(1-x)}{10} \cdot (0) = - \frac{1}{10} \]이 됨을 알 수 있습니다. 이는 \(x\)가 무슨 값을 가지든 항상 동일하므로 A가 혼자서 굳이 전략을 바꿀 필요가 없다는 뜻이 됩니다. 같은 이치로 B도 혼자서는 전략을 굳이 바꿀 이유가 없습니다. 따라서 A와 B가 각각 \(\frac{1}{10}\)의 확률로 돌진하고 \(\frac{9}{10}\)의 확률로 회피하는 전략을 택한 상태는 내쉬 균형을 이룹니다.
이것으로 우월 전략 균형과 내쉬 균형에 대한 정리를 마칩니다. 예전부터 개인적으로 헷갈렸던 개념이었는데, 이번에 좀더 확실히 알게 되어 개인적으로 정리할 겸해서 포스팅을 하였습니다. 게임 이론이 컴퓨터 과학과 밀접한 연관이 있음을 알게 된 후 차근히 공부하고 있습니다. 이 글을 필두로 하여 새롭게 알게 된 내용 중 공유할 만한 내용이 있다면 포스팅해 보도록 하겠습니다.
고맙습니다.
추신. 기존에 "equilibrium"의 번역으로 "평형"을 사용했는데, 인터넷에서 찾아 보니 "균형"이 널리 사용되는 번역인 것 같더군요. 후자로 모두 바꾸었습니다.
참고 문헌
[1] Jason D. Hartline. Mechanism design and approximation. Link: http://jasonhartline.com/MDnA/
'알고리즘 & 게임 이론 > Game theory' 카테고리의 다른 글
| 2인 제로섬 게임 (Two-Player Zero-Sum Game) (0) | 2020.07.12 |
|---|
