3부의 제목은 '죄수의 딜레마 게임'입니다. 요즘 일 한다고 진도가 늦었네요. 그리고 1부와 2부에 비해 더 구체적으로 들어가기도 하고 어려운 부분도 있습니다. 수식도 많아져서 가능하면 제 손으로 풀어보려 했으나 그냥 지나쳐버린 곳도 있네요. 읽은 거야 읽은 거지만 막상 정리를 하려니 막막합니다.
δ의 확률로 무한히 반복되는 죄수의 딜레마(PD) 게임을 생각합니다. PD 게임을 한 번만 한다면 서로 배반(D)하는 게 내쉬균형이죠. 하지만 반복되는 PD 게임에서는 그렇지 않을 수도 있습니다. 이를테면 두 경기자가 모두 다음 전략에 따라 게임한다고 합시다.
- 첫 회에는 C를 한다.
- 상대방이 한 번이라도 D를 하면 영원히 D만 한다.
- 상대방이 D를 한 적이 없다면 C를 한다.
이걸 trigger 또는 grim trigger 전략이라고 합니다. 책에서는 "가차없는 보복 전략"(283쪽)으로 옮기고도 계속 "Trigger 전략"으로 쓰는데 저는 직역하여 "(잔혹한) 방아쇠 전략"으로 쓰겠습니다. 한 번 방아쇠(상대방의 D)가 당겨지면 돌이킬 수 없기 때문에 이런 이름이 붙은 것 같습니다. 한 번의 잘못이나 실수를 용서하지 않고 '영원히' D로 대응하기 때문에 '가차없는/잔혹한'이라는 수식어가 또 붙었겠죠.
δ가 충분히 크다면(즉 c/b보다 크다면) 방아쇠 전략에 대한 최적대응은 계속 C만 하는 겁니다. 그리고 c/b는 PD의 정의에 의해 1보다 작고 δ도 0과 1 사이이므로 c/b < δ < 1인 δ는 반드시 존재합니다.
방아쇠 전략을 "서로 C를 하기로 약속"하고 이를 "어기면" 영원한 보복(D)으로 대응한다는 식으로 이해할 수 있습니다. 여기서 '약속'을 혼합전략으로 확장할 수도 있는데요, 경기자 1은 α의 확률로 C를 1-α의 확률로 D를 하기로 약속하고 경기자 2는 매 회 C를 하기로 약속한다고 합시다. 둘 중 약속을 어기는 쪽은 상대방으로부터 영원한 보복을 당하게 됩니다. 위 약속이 내쉬균형이 되는 조건은 δ > c/(αb)이며, α가 c/b보다 큰 경우 이 조건을 만족하는 δ는 반드시 존재합니다. 두 경기자 모두에게 혼합전략을 부여하는 경우는 넘어가겠습니다. 중요한 건, 반복되는 PD에서는 게임이 반복될 확률이 충분히 크다면 둘 다 배반하는 전략보다 더 많은 보수를 얻는 전략쌍이 내쉬균형이 될 수 있다는 점입니다.
이제 반복되는 PD 게임을 게임트리를 이용해서 보겠습니다. PD와 같은 동시 게임도 전개형, 즉 게임트리로 표현할 수 있습니다. (게임트리 그려놓은 건 구글링해서 찾아보세요;;;) 한 노드(이걸 I0이라 부릅시다)에서 경기자 1의 선택(C 또는 D)에 따라 두 개의 가지가 나옵니다. 각 가지의 끝에서는 경기자 2의 선택(C 또는 D)에 따라 각각 두 개의 가지가 나옵니다. 한 번 게임을 했다면 두 경기자가 어떤 전략을 냈는지 서로 알 수 있겠죠. 모두 4가지 경우가 가능한데 이 각 경우는 I0에서 뻗어나온 총 4개의 가지의 각 끝 노드(ICC, ICD, IDC, IDD로 부릅시다)에 해당합니다. 각 노드에서는 '다음 회'의 PD 게임이 펼쳐집니다. 두 번 게임을 한 후의 노드들은 ICCCC부터 IDDDD까지 모두 16개가 되겠죠. 무한히 반복되는 게임에서는 게임트리의 크기도 무한히 커집니다. 이 전체 게임트리 중, 예를 들어 노드 ICC에서 시작되는 게임만을 가리켜 '부분게임(subgame)'이라고 부릅니다. 어떤 부분게임에서도 내쉬균형이 되는 전략쌍을 "부분게임 완전 내쉬균형(subgame perfect Nash equilibrium; SPNE)"이라 부릅니다.
첫 게임부터 t번째 게임까지 두 경기자의 실제 행동을 나열한 것을 '역사' h(t)라고 부릅시다. 예를 들면 다음과 같습니다.
$$h(t)=\{(C,C)_1,(C,D)_2,\cdots,(D,C)_t\}$$
t번째 게임까지 두 경기자 모두 C만 한 경우를 다음처럼 씁니다.
$$h^*(t)=\{(C,C)_1,(C,C)_2,\cdots,(C,C)_t\}$$
순수전략만을 고려하는 경우의 방아쇠 전략이란 위의 h*(t)인 역사를 따라 도달된 노드에서만 C를 하고 그렇지 않은 경우에는 영원히 D를 하겠다는 말입니다. 부분게임에서 방아쇠 전략을 쓰는 상대방에 대한 최적대응이 뭘지를 살펴봅시다. 먼저 h*(t)에 의해 도달한 노드에서 시작되는 부분게임을 봅니다. 아직 둘 중 누구도 D를 하지 않았으므로 상대는 계속 C를 하려고 할 것이고 이에 대한 나의 최적대응은 역시 계속 C를 하는 것입니다. 다음으로 h*(t)에 의한 노드가 아닌 노드에서 시작되는 부분게임을 봅니다. 예를 들어 바로 이전 게임에서 내가 D를 한 경우를 봅시다. 방아쇠 전략을 쓰는 상대는 앞으로 영원히 D를 할테고, 그에 대한 나의 최적대응은 계속 D를 하는 것입니다. 즉 어떤 부분게임에서도 나의 최적대응은 바로 방아쇠 전략임을 알 수 있습니다. 다시 말하면, 방아쇠 전략은 부분게임 완전 내쉬균형입니다.
사실 책에 있는 내용을 있는 그대로 이해하기 힘들어서 제 나름대로 살짝 재구성했는데 논리적인 허점이 있을지도 모르겠습니다. 여튼 이런 내용을 전래정리(Folk Theorem)라 부릅니다.
TFT는 부분게임 완전 내쉬균형이 아니라고 합니다. 여기서도 역시 위의 h*(t)라는 역사를 따라 도달된 노드에서 시작되는 부분게임에서는 서로 C를 하는 게 내쉬균형이 됩니다. 그런데 그렇지 않은 경우, 예를 들어 바로 이전 게임에서 내가 D를 하고 상대방은 C를 한 경우를 봅시다. 이번 게임에서 상대는 TFT에 따라 D를 할 것이고 이에 대한 나의 최적대응은 D입니다. 만일 이번 게임에서 내가 TFT를 따라 C를 한다면 최적대응이 될 수 없습니다. 이렇게 TFT가 내쉬균형이 될 수 없는 노드가 있으므로 TFT는 부분게임 완전 내쉬균형이 아닙니다. (맞나요? 어쨌든 넘어가겠습니다;;;)
이제 9장(277쪽부터)으로 넘어옵니다. 방아쇠 전략도 조건부 협조전략 중 하나인데요, 조건부 협조전략들의 협조적 균형이 진화적으로 안정한지, 그렇다면 얼마나 쉽게 그 균형에 도달할 수 있는지, 좀더 일반적인 상황에서 동태적으로는 어떻게 될지 등이 논의되어야 한다고 합니다.
다양한 전략들이 골고루 섞인 집단에서 어떤 전략이 살아남을지를 보기 위해 유전자 알고리듬을 이용하는데요, 이를 통해 어떠한 상태도 영원히 지속되지 않는다는 걸 보여줍니다. 제대로(?) 하려면 복제자 동학 방정식을 써서 정확히 풀어야 합니다. 하지만 반복 게임에서 가능한 전략의 수는 이전 게임을 몇 회까지 기억하여 구성하느냐에 따라 기하급수적으로 늘어납니다. 다시 말해서 방정식의 수가 굉장히 많아져서 정확히 푸는 일이 불가능해집니다. 통계물리 모형을 몬테카를로 방법으로 풀듯이 복제자 동학 대신 유전자 알고리듬을 쓰는 것으로 보입니다.
다음으로, 조건부 협조전략은 무조건 협조전략(all C)과 만났을 때 서로 계속 C만 하므로 같은 보수를 얻습니다. 겉으로는 구분되지 않으므로 무조건 협조전략이 집단에 퍼질 가능성이 있습니다. 그런데 무임승차를 허용하는 무조건 협조전략을 착취하는 무조건 배반전략(all D)이 나타난다면 이들은 다른 전략보다 더 큰 보수를 얻음으로써 쉽게 집단에 퍼지겠죠.
이 상황을 좀더 구체적으로 나타내기 위해 조건부 협조전략으로 방아쇠 전략(T)만 있다고 합시다. 만일 all D가 없다면 T와 all C는 공존합니다. 이를 '협조 균형'이라 부릅니다. 그런데 유전자 표류와 같은 메커니즘으로 all C가 많아질 수 있다고 합니다. 제가 이해한 바로, 표류는 개체의 수가 유한할 때에만 나타나는 유한크기 효과입니다. 여튼 all C의 인구비중이 일정한 값보다 작은 경우에는 all D가 돌연변이에 의해 나타난다고 해도 T들이 잘 막아줘서 all D는 사라져버릴 수 있습니다. 그런데 all C의 비중이 일정한 값보다 클 때 all D가 나타나면 T들이 있다고 해도 그 수가 적어서 all D의 확산을 막기에는 역부족이 됩니다. 결국 all D들만의 세상이 되어 끝날 가능성이 있습니다. all D가 없을 때 all C와 T가 구별되지 않기 때문에 생길 수 있는 일입니다.
이를 해결하는 방법 중 첫째로, 무임승차자들이 집단 내에 적지만 일정한 비율로 늘 존재하게 하는 것입니다. 예방주사를 맞는 거죠. 다만 무임승차자가 너무 많아서도 안된다는 것도 자명하죠. 책에서 세팅한 상황에서는 약 2% 정도가 적절한 선입니다. 또는 그 비율을 고정시키는 대신 돌연변이로 무임승차자가 나타날 확률을 조절할 수도 있습니다. 이 비율이 너무 커도 문제일텐데 책에서는 '너무 큰 경우'는 현실적이지 않다고 생각하여 다루지 않는 것 같습니다.
다음으로는 행위자들의 '실수'가 협조 균형의 안정성에 어떤 역할을 하는지를 봅니다. 기존 연구들은 실수의 부정적 측면만을 강조하여 이에 맞서는 조건부 협조전략을 찾아내는데 중점을 두었다고 합니다. 방아쇠 전략만 하더라도 상대방이 C를 하려고 했는데 실수로 D를 하면 '영원한 보복'을 당할테고 둘의 관계(?)는 파국으로 치닫겠죠. 반면에 이 책에서는 실수가 오히려 특정한 조건부 협조전략의 경우 안정성을 강화시켜준다는 결과를 소개합니다. (최정규 교수의 2007년 논문을 정리한 것이라고 합니다.)
역시 all C, T, all D 세 전략만 고려합니다. 협조 행위를 하려고 하는 경우에만 일정한 확률(ε)로 실수가 일어나서 D를 한다고 합시다. ε이 충분히 0에 가깝고, δ가 충분히 1에 가까우면, c < b < 2c일 때 T는 진화적으로 안정하다고 합니다. 실수가 없는 경우(ε = 0)에는 all C와 T의 보수가 똑같아서 T는 중립적으로만 안정했는데 실수에 의해 all C의 보수보다 T의 보수가 높아집니다. 이로 인해 앞서 말한 표류가 일어나지 못하므로 만일 all C와 T가 공존하는 집단에 돌연변이에 의해 all D가 나타난다고 해도 이 집단이 all D로만 이루어진 집단으로 진화할 가능성은 사라집니다.
3부는 이 정도로 접습니다.
