죄수의 딜레마 Part 3: 다시 만난다면 — 반복 게임, 액설로드 대회, 팃포탯

이 글은 Claude Opus 5.5 를 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.

들어가며#

Part 1 의 두 죄수는 한 번 만나고 헤어집니다. 출소 뒤의 보복도 없고, 다음 범행도 없습니다. 그래서 배신이 언제나 낫습니다.

그런데 Part 1 의 6절에서 본 1950년 RAND 의 첫 실험에서, 같은 게임을 100번 이어 둔 두 사람은 자주 협력했습니다. 존 내쉬는 반복되는 게임에서는 합리적인 행동이 달라질 수 있다고 답했습니다. 이번 편은 그 말을 따라갑니다. 서바이벌은 한 번 만나고 헤어지는 게임이 아닙니다. 같은 사람들이 몇 주 동안 한 집에 살며 수십 번의 게임을 합니다. 반복이 무엇을 바꾸는지 알면, 서바이벌의 연합과 배신이 언제 일어나는지 보입니다.

1. 끝을 안다면 — 마지막 판부터 무너진다#

같은 상대와 죄수의 딜레마를 정확히 10번 한다고 합시다. 둘 다 10번이라는 것을 압니다.

10번째 판 을 생각해 봅니다. 이 판이 끝나면 다시는 만나지 않습니다. 보복도 보상도 없습니다. 그러니 10번째 판은 한 번짜리 죄수의 딜레마와 똑같고, 둘 다 배신합니다.

9번째 판 은 어떨까요. 10번째 판에서 둘 다 배신할 것이 이미 정해졌으니, 9번째 판에서 협력해도 10번째 판의 상대를 바꿀 수 없습니다. 그러면 9번째 판도 한 번짜리와 같고, 둘 다 배신합니다.

이렇게 거꾸로 올라가면 1번째 판부터 배신 입니다. 이 추론을 역진 귀납(backward induction)¹ 이라고 합니다. 끝이 정해진 반복 게임의 유일한 합리적 결말은 매번 배신입니다.

flowchart RL
    G10["10번째 판<br/>마지막이니 배신"] --> G9["9번째 판<br/>다음 판은 어차피 배신<br/>그러니 배신"]
    G9 --> G8["8번째 판<br/>배신"]
    G8 --> G0["…"]
    G0 --> G1["1번째 판<br/>처음부터 배신"]
    style G10 fill:#FF9999,color:#000000
    style G9 fill:#FF9999,color:#000000
    style G8 fill:#FF9999,color:#000000
    style G0 fill:#D3D3D3,color:#000000
    style G1 fill:#FF9999,color:#000000

1.1 사람은 그렇게 하지 않는다#

하지만 실험실의 사람은 그렇게 두지 않습니다. 독일의 경제학자 라인하르트 젤텐(Reinhard Selten)과 롤프 슈퇴커(Rolf Stoecker)는 1986년, 피실험자 35명에게 10판짜리 죄수의 딜레마를 상대를 바꿔 가며 25번 하게 했습니다. 경험이 쌓인 피실험자들은 끝 직전까지 협력하다가, 끝에 다다라 배신 했습니다. 한 사람이 배신하면 상대도 곧바로 배신으로 돌아서고, 협력은 다시 살아나지 않았습니다. 이것을 종반 효과(end effect) 라고 부릅니다. 그리고 경험이 쌓이면서 그 배신 시점이 옮겨 갔습니다.

이론은 “처음부터 배신” 이라고 하는데 사람은 “끝에서만 배신” 합니다. 이 차이가 서바이벌을 보는 첫 번째 열쇠입니다.

결승이 가까워질수록 배신이 늘어나는 것은 성격이 변해서가 아닙니다. 남은 판이 줄어드는 만큼 보복의 무게가 줄어드는 것입니다. 마지막 판에서는 그 무게가 0 이 됩니다.

2. 끝을 모른다면 — 미래의 그림자#

이번에는 몇 번 할지 모른다 고 합시다. 매 판이 끝날 때마다 다음 판이 있을 확률이 w 입니다. 예를 들어 w = 0.9 면, 평균 10판쯤 이어지지만 이번 판이 마지막인지는 아무도 모릅니다.

그러면 역진 귀납이 시작할 “마지막 판” 이 없습니다. 오늘 배신하면 오늘 T(5점)를 얻지만, 상대가 그것을 기억하고 다음 판부터 배신하면 매번 R(3점) 대신 P(1점)를 받습니다. 다음 판이 있을 확률이 충분히 높으면, 오늘의 2점 이득보다 내일 이후의 손해가 큽니다.

정치학자 로버트 액설로드는 이 w 를 미래의 그림자(shadow of the future) 라고 불렀습니다. 그림자가 길수록, 즉 다시 만날 가능성이 클수록 협력이 버팁니다. 게임 이론에는 이것을 일반화한 포크 정리(folk theorem)² 가 있습니다. 미래를 충분히 중요하게 여기는 사람들 사이에서는, 무한히 반복되는 게임에서 협력을 포함한 아주 많은 결과가 균형으로 유지될 수 있다는 결과입니다.

여기까지는 “협력이 가능하다” 는 이야기입니다. 그렇다면 어떤 전략이 실제로 잘 하는가. 1980년, 액설로드는 그것을 직접 대회로 물었습니다.

3. 액설로드 대회#

3.1 1차 대회 — 열네 개의 프로그램#

1980년, 미시간대의 액설로드는 게임 이론가들에게 편지를 보냈습니다. 반복 죄수의 딜레마를 두는 컴퓨터 프로그램 을 보내 달라는 것이었습니다. 규칙은 이렇습니다.

• 모든 프로그램이 다른 모든 프로그램과 한 번씩 맞붙는다(리그전)³. 자기 복제본과도, 무작위로 협력·배신하는 RANDOM 과도.
• 한 경기는 200판.
• 점수는 Part 1 의 T=5, R=3, P=1, S=0. 상대를 이기는 것이 아니라 총점 이 높은 쪽이 이긴다.

심리학·경제학·정치학·수학·사회학에서 14개 가 들어왔습니다. 복잡한 것은 상대의 패턴을 통계로 추정했고, 교활한 것은 협력하는 척하다 몰래 배신을 섞었습니다.

우승은 가장 짧은 프로그램이었습니다. 토론토대의 수리심리학자 아나톨 라포포트(Anatol Rapoport) 가 낸 팃포탯(Tit for Tat)⁴ 입니다. 규칙은 두 줄입니다.

1. 첫 판은 협력한다.
2. 그 뒤로는 상대가 지난 판에 한 것을 그대로 따라 한다.

3.2 2차 대회 — 결과를 보고 다시 덤벼도#

액설로드는 1차 결과와 분석을 공개하고 2차 대회를 열었습니다. 이번에는 참가자들이 팃포탯이 이겼다는 것을 알고 프로그램을 짰습니다. 팃포탯을 이기려고 설계된 프로그램도 들어왔습니다. 여섯 나라에서 62개 가 모였고, 한 가지 규칙을 바꿨습니다. 경기 길이를 200판으로 정하지 않고 확률로 정했습니다. 1절의 “마지막 판 배신” 을 막기 위해서입니다.

라포포트는 같은 팃포탯을 다시 냈고, 또 이겼습니다. 액설로드는 이 결과를 생물학자 W. D. 해밀턴(W. D. Hamilton)과 함께 1981년 『사이언스』에 논문으로 냈고, 1984년 책 『협력의 진화(The Evolution of Cooperation)』로 펴냈습니다.

3.3 팃포탯은 한 경기도 이기지 못한다#

팃포탯에는 이상한 성질이 있습니다. 어떤 상대와 붙어도 상대보다 점수가 높을 수 없습니다. 먼저 배신하지 않으니 상대가 배신한 판에서는 S 를 받고, 그 뒤에 따라 배신해도 그만큼을 되찾을 뿐 앞설 수는 없습니다. 기껏해야 비깁니다.

그런데도 리그전 총점은 1등이었습니다. 개별 경기에서 이기지 않고, 모든 경기에서 높은 점수를 함께 만들어 냈기 때문입니다. 협력하는 상대와는 매번 3점씩, 배신하는 상대에게는 크게 당하지 않고. 교활한 프로그램들은 개별 경기에서 상대보다 앞섰지만, 그 과정에서 서로를 끌어내려 총점이 낮았습니다.

대회는 상대보다 많이 가 아니라 스스로 많이 를 쟀습니다. 이 기준에서는 상대를 이기려는 욕심이 오히려 손해였습니다.

3.4 무엇이 팃포탯을 이기게 했나#

액설로드는 상위 프로그램의 공통점을 네 가지로 정리했습니다.

1차 대회에서 상위 여덟 개는 모두 “착한” 프로그램이었고, 하위 일곱 개 가운데 착한 것은 하나도 없었습니다.

네 번째 성질이 서바이벌에서 특히 흥미롭습니다. 팃포탯이 강한 이유 가운데 하나는 속을 알 수 있다 는 것입니다. 상대는 몇 판 만에 “이 녀석은 내가 협력하면 협력하고, 배신하면 배신한다” 를 알아채고, 그러면 협력하는 것이 자기에게도 최선이라는 결론에 이릅니다. 속을 알 수 없는 영리한 전략은 상대를 불안하게 만들고, 불안한 상대는 배신합니다.

4. 실수 한 번 — 끝없는 보복#

4.1 메아리#

팃포탯에도 약점이 있습니다. 실수 입니다. 현실에서는 협력하려다 잘못 누르거나, 상대의 협력을 배신으로 잘못 읽는 일이 생깁니다. 팃포탯끼리 붙었는데 한쪽이 한 번 실수로 배신하면 어떻게 될까요.

flowchart LR
    T1["1판<br/>A 협력 · B 협력"] --> T2["2판<br/>A <b>실수로 배신</b> · B 협력"]
    T2 --> T3["3판<br/>A 협력 · B 배신<br/>(B 가 따라 함)"]
    T3 --> T4["4판<br/>A 배신 · B 협력<br/>(A 가 따라 함)"]
    T4 --> T5["5판<br/>A 협력 · B 배신"]
    T5 --> T6["…<br/>엇갈린 보복이<br/>끝없이 메아리친다"]
    style T1 fill:#90EE90,color:#000000
    style T2 fill:#FF9999,color:#000000
    style T3 fill:#FFD700,color:#000000
    style T4 fill:#FFD700,color:#000000
    style T5 fill:#FFD700,color:#000000
    style T6 fill:#D3D3D3,color:#000000

둘이 서로의 지난 판을 따라 하니, 배신 한 번이 엇갈리며 영원히 메아리칩니다. 한 번 더 실수가 나면 둘 다 배신하는 상태로 굳어 버립니다. Part 1 의 보수로 계산하면 엇갈린 상태의 평균은 판당 2.5점(5 와 0 의 평균)으로, 함께 협력할 때의 3점보다 낮습니다. Part 1 의 조건 2R > T + S 가 바로 이 손해를 보장합니다.

4.2 관대함과 파블로프#

실수가 있는 세계를 위해 두 가지 처방이 나왔습니다.

관대한 팃포탯(Generous Tit for Tat). 상대가 배신해도 작은 확률로 그냥 협력 합니다. 영문 위키백과는 상대 구성에 따라 대략 1~5% 를 듭니다. 메아리가 생겨도 언젠가 누군가 먼저 용서해 끊어집니다. 대신 그만큼 늘 배신하는 상대에게는 조금 더 당합니다.

파블로프(Pavlov), 또는 이기면 그대로·지면 바꾸기(win-stay, lose-shift). 지난 판 결과가 좋았으면(R 이나 T) 같은 선택을 그대로 하고, 나빴으면(P 나 S) 선택을 바꿉니다. 마틴 노박(Martin Nowak)과 카를 지그문트(Karl Sigmund)가 1993년 『네이처』에서 실수가 있는 진화 모의실험⁵에서 팃포탯을 앞설 수 있다고 보인 전략입니다. 둘 다 실수로 배신해 P 를 받으면, 둘 다 “졌다” 고 보고 함께 협력으로 바꿉니다. 메아리가 한 판 만에 멈춥니다.

4.3 협박하는 전략#

2012년에는 물리학자 윌리엄 프레스(William Press)와 프리먼 다이슨(Freeman Dyson)이 제로 행렬식(zero-determinant) 전략 이라는 새 부류를 발표했습니다. 이 가운데에는 상대가 무엇을 하든 상대의 장기 점수를 내가 정해 버리거나, 상대가 협력할수록 내가 더 많이 가져가도록 만드는 “협박(extortion)” 전략이 있습니다. 상대가 협박에 맞서 배신하면 자기 점수도 떨어지니, 울며 겨자 먹기로 협력하게 됩니다. 반복 죄수의 딜레마가 일종의 최후통첩 게임⁶처럼 변합니다.

다만 이 협박 전략은 협박자끼리 만나면 서로를 깎아 먹어 큰 집단에서는 오래가지 못한다는 후속 연구가 이어졌습니다. 대신 같은 부류 안의 관대한(generous) 전략이 큰 집단에서 안정적이고 강하다는 결과가 2013년에 나왔습니다. 30년이 지나도 결론은 비슷했습니다. 길게 보면 관대한 쪽이 남는다.

5. 2004년, 연합이 대회를 깨다#

액설로드 대회 20주년을 기념한 2004년 대회에서, 영국 사우샘프턴대 팀이 1~3위를 휩쓸었습니다. 방법은 이랬습니다.

• 한 팀이 60개 의 프로그램을 냈다(이 대회는 여러 개 출품을 허용했다).
• 프로그램들은 경기 초반 5~10판 동안 미리 약속한 협력·배신 순서 를 둔다. 상대가 그 순서로 답하면 같은 팀이다.
• 같은 팀을 만나면 한쪽은 계속 협력, 다른 쪽은 계속 배신 한다. 배신하는 쪽이 매번 T(5점)를 받아 총점을 끌어올린다.
• 같은 팀이 아니면 계속 배신 해 상대의 점수를 깎는다.

그 결과 팀의 “주인” 프로그램들이 1~3위를 차지했고, 희생한 “종” 프로그램들은 바닥에 깔렸습니다. 영문 위키백과는 이 결과가 단일 전략의 강도를 말해 주는 것은 아니지만, 여러 행위자가 서로를 알아보고 짜는 상황에서 소통이 얼마나 큰 힘을 갖는지를 보여 준다고 평합니다. 리처드 도킨스(Richard Dawkins)는 이런 전략이 나올 수 있다는 것을 『이기적 유전자』에서 이미 짚었다고도 덧붙입니다.

서바이벌을 보는 사람에게는 익숙한 그림입니다.

신호로 서로를 알아보고, 같은 편끼리는 한 사람에게 몰아주고, 바깥 사람에게는 배신한다. 연합 입니다. 1:1 의 죄수의 딜레마를 다인 게임 위에 올리면, 가장 강한 전략은 “착한 전략” 이 아니라 “편을 짜는 전략” 이 될 수 있습니다.

「살아남은 자들」 Part 3 과 Part 6 에서 본 『더 지니어스』의 연합, 『데블스 플랜』의 “공리주의” 가 이 구조였습니다. 다수가 한 사람에게 몰아주고, 바깥 사람을 배제합니다.

6. 참호 속의 팃포탯 — 1차 세계대전#

액설로드가 책에서 가장 공들인 사례는 실험실이 아니라 전쟁터였습니다. 영국의 사회학자 토니 애시워스(Tony Ashworth)가 정리한 “살고 살게 하라(live and let live)” 체계입니다.

1차 세계대전 서부전선의 참호에서는 같은 부대끼리 몇 주, 몇 달씩 마주 보고 있었습니다. 그러자 명령에도 없는 암묵적 휴전 이 생겨났습니다. 식사 시간에는 서로 쏘지 않고, 포격은 정해진 시간에 정해진 곳으로만 해서 상대가 피할 수 있게 했습니다. 한쪽이 그 규칙을 어기면 다른 쪽은 정확히 그만큼 되갚았고, 다시 조용해졌습니다. 1914년 크리스마스 휴전이 가장 유명한 예이지만, 이런 행동은 작은 부대 단위에서 훨씬 넓고 오래 퍼져 있었습니다.

액설로드는 이것을 반복 죄수의 딜레마로 읽었습니다. 같은 상대를 오래 마주하고(미래의 그림자), 배신에는 곧바로 정확히 되갚고(보복), 상대가 멈추면 나도 멈춘다(용서). 서로 죽이는 것이 일인 사람들 사이에서도 팃포탯의 조건이 갖춰지면 협력이 생겼습니다. 이 휴전을 깬 것은 병사들이 아니라 사령부였습니다. 부대를 자주 교대시키고, 습격을 명령해 반복의 조건을 없앴습니다.

7. 서바이벌에 대입하면#

이 편의 내용을 서바이벌의 언어로 옮기면 이렇습니다.

그리고 여기에 Part 1·2 에서 미뤄 둔 열쇠가 하나 더 붙습니다. 남이 본다 는 것입니다. 1:1 반복 게임에서는 “그 사람이 나에게 한 일” 만 기억하지만, 서바이벌에서는 “그 사람이 다른 사람에게 한 일” 도 모두가 봅니다. 게임 이론은 이것을 간접 상호성(indirect reciprocity)⁷ 이라고 부르고, 평판이 협력을 지탱하는 또 하나의 길로 연구합니다. 배신자가 다음 판에서 아무와도 짝을 짓지 못하는 장면이 그것입니다.

마치며#

이번 편을 한 문장으로 줄이면 “다시 만날 가능성이 협력을 만들고, 그 가능성이 줄어드는 곳에서 배신이 돌아온다” 입니다. 끝을 아는 게임은 마지막 판부터 무너지고, 끝을 모르는 게임에서는 착하고, 갚고, 용서하고, 속이 보이는 팃포탯이 강합니다. 실수가 있으면 조금 더 관대한 쪽이 낫고, 여럿이 편을 짤 수 있으면 연합이 착한 전략을 이깁니다.

여기까지가 이론입니다. 다음 편부터는 실제 장면입니다. 먼저 텔레비전이 이 게임을 가장 정직하게 가져다 쓴 곳, 영국과 미국의 게임쇼입니다. 상금이 수천만 원일 때 사람들은 실제로 얼마나 나누었는지, 그리고 한 참가자가 “나는 무조건 훔친다” 고 선언했을 때 무슨 일이 일어났는지를 봅니다.

References#

• Prisoner’s dilemma — Wikipedia, “The iterated prisoner’s dilemma” — 역진 귀납, 액설로드 대회와 상위 전략의 조건, 관대한 팃포탯, 파블로프, 제로 행렬식 전략, 2004년 사우샘프턴
• R. Axelrod & W. D. Hamilton, The Evolution of Cooperation, Science 211 (1981) — 대회의 점수, 팃포탯
• R. Axelrod, “More Effective Choice in the Prisoner’s Dilemma”, Journal of Conflict Resolution 24(3) (1980) — 2차 대회: 여섯 나라 62개 출품, 확률로 정한 경기 길이
• The Evolution of Cooperation — Wikipedia — 1차 대회 200판 리그전, 2차 대회
• Tit for tat — Wikipedia — 라포포트, 두 대회 모두에서 가장 단순하고 가장 성공한 전략
• R. Selten & R. Stoecker, “End behavior in sequences of finite Prisoner’s Dilemma supergames”, Journal of Economic Behavior & Organization 7 (1986) — 종반 효과
• M. Nowak & K. Sigmund, “A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s Dilemma game”, Nature 364 (1993) — 파블로프
• W. H. Press & F. J. Dyson, “Iterated Prisoner’s Dilemma contains strategies that dominate any evolutionary opponent”, PNAS 109 (2012) — 제로 행렬식 전략
• Live and let live (World War I) — Wikipedia — 참호전의 암묵적 휴전, 애시워스