합리적 분배와 게임이론 (1/3)
해적들의 금화 나누기
5명의 해적(서열에 따라 A, B, C, D, E)이 노략질한 금화 100개를 나누기로 합니다. 어떻게 나눌지 분배 방법이 필요하겠죠? 그 방법을 정할 규칙을 이렇게 정했습니다.
제일 먼저 A가 분배 방법을 제안하고, 제안자를 포함한 5명이 그 방법을 채택할지 찬반 투표를 합니다. 찬성표가 절반보다 많으면 그 방법대로 분배하고 끝이지만, 그렇지 않다면 A를 바다에 던져버리고(...) 추방하고, 나머지 4명이서 똑같은 절차를 진행합니다. 이번에는 B가 제안하고, 또 채택되지 않으면 C, D 순서로 제안하게 됩니다.
어떤가요? 합리적인 규칙인가요? 만약 내가 A라면 어떻게 분배하자고 제안할까요?
(A=30, B=25, C=20, D=15, E=10)?
아니면 모두 똑같이 (20, 20, 20, 20, 20)?
게임이론의 해법
다른 요인은 모두 배제하고, 경제학에서 가정하는 "합리적인 인간"이 되어 나의 이익을 최대화하는 방법을 찾아봅시다. 하는 김에, 나뿐만 아니라 다른 4명도 모두 합리적이고 이기적이라고 가정하겠습니다. 바로 게임이론에서 다루는 방식입니다. 『n분의 1의 함정』을 쓴 게임이론 전문가 하임 샤피로에 따르면, A의 최적 전략은 (97, 0, 1, 0, 2)로 분배하는 것입니다. 직관과는 많이 다르죠.
이런 결과가 도출되는 논리는 다음과 같습니다.
제일 뒤에서부터 시작합니다. 만약에 D와 E만 남은 상황이 되면, D는 모든 금화를 E에게 줘야 합니다. 규칙에 따라 E가 찬성하지 않으면 D가 추방되고 남은 E가 모든 금화를 차지하기 때문이죠. 그러므로 이 단계까지 오면 D는 금화를 얻을 수 없으므로 앞 단계에서 1개라도 얻을 수 있으면 찬성해야 합니다. 이제 더 앞으로 갑시다.
C, D, E만 남은 상황이라면, C는 D에게 1개만 줘도 된다는 걸 알고 있습니다. D가 찬성한다면 E가 반대해도 상관없죠. 그러니 C는 (99, 1, 0)으로 분배를 제안합니다. E는 여기까지 오면 금화를 하나도 못 얻는다는 걸 기억하고, 한 단계 더 앞으로 갑니다.
B, C, D, E가 남은 상황. 위의 사실을 알고 있는 B는 어떻게 제안할까요? C를 만족시킬 방법은 사실상 없습니다 (100개를 다 줘야 하니까요) D와 E에게는 각각 2개, 1개만 줘도 찬성할 겁니다. 따라서 (97, 0, 2, 1)
이런 식으로 마지막 장면에서부터 역행해서 추론하면(backward induction, 역진귀납법), A의 "최적" 제안을 찾을 수 있습니다. 하나의 표로 정리하면 아래와 같습니다. 각 행이 제안을 나타내고, 그 제안에 찬성하는 사람을 초록색으로 표시했습니다.
게임 AI
그런데 인간적인 요소(해적도 사람이니까요)나 분배라는 상황에 감정을 이입해서 그렇지, 순수하게 전략적인 논리로만 따지면 위의 결론을 반박하기는 쉽지 않습니다. 실제로 이런 방식은 "고전 시대"에 게임 AI를 구현하는 방법으로 많이 사용되었습니다. 순차적으로 액션을 취하는 게임에서, 내가 이번 턴에 어떤 선택을 하면 상대도 최선의 방법으로 대응하겠죠. 그렇다면 항상 상대방의 최대 보상을 최소화(minimax)하는 선택을 하도록 게임 AI를 만들면 꽤 지능적으로 동작하게 됩니다.
위의 경우, 최적 전략이 내놓은 첫 수(97, 0, 1, 0, 2)는 정말 이상해 보였지만, 게임이 끝나가는 시점에 돌아보면 신의 한 수로 평가받을 수도 있겠죠. 해적의 금화 분배는 잠시 잊고, 오목/오델로/체스/바둑 같은 게임에 대입해서 생각해 보세요 :)
그렇다고 해도 현실에서 해적 A가 정말로 (97, 0, 1, 0, 2)을 제안했다가는 그 즉시 1:4 표결로 고래밥이 되고 말 것입니다. 당연하죠. 그런데 왜일까요? 여러 요인을 꼽을 수 있겠지만, 저는 D와 E만 남으면 D는 한 개도 얻지 못하니 C가 1개라도 주면 D는 찬성할 것이라는 류의 가정이 현실과 동떨어져 있기 때문이 아닐까 합니다. 일반적인 상황에서 사람은 그렇게 행동하지 않으니까요. (그렇죠...?)
제로섬 게임은 일단 여기까지 하고, 다음 글에서는 협력 게임을 한 번 다뤄보겠습니다.
참고 자료
하임 샤피라, 『n분의 1의 함정』, 이재경 옮김, 반니(2017)
