유한반복게임과 무한반복게임 (Prisoners' Dilemma 죄수의 딜레마)

반복 게임?

동일한 전략적 상황이 계속 반복되는 게임

 

Stage game (스테이지 게임) ?

반복 게임을 하며 매기마다 발생하는 일회성 전략적 상황

 

게임이 반복 될 때, 어떤 경기자의 보수를 차례대로 u₁, u₂... 이라고 할 때

할인계수 σ를 써서 미래가치를 할인한다 (0<σ<1)

 

그러면 player의 현재 가치는 u₁+σu₂+u^2σ₃

 

 

---

죄수의 딜레마(prisoners' dilemma)에서 player들이 상호작용이 여러번 가능하고 상대방이 배신하더라도 다음 게임에서 응징할 수 있게 된다면 결과가 어떻게 바뀔까?

 

 

- 유한 반복(T번 반복, T < ∞)

만약 T가 2인 경우를 보게 되면, 두 player는 첫번째 stage에 어떤 일이 일어나든 history와 관계 없이

마지막 게임에서 player들은 모두 D를 택할 것이다.

2가 아니더라도 T회 반복되는 상황일 때 T기(마지막 stage game)에서는 모두가 D를 택한다. 

그러므로 T-1기를 생각했을 때, 마지막 stage에서는 어차피 history와 상관 없이 D를 택하게 되므로 T-1기에서도 D를 택하게 될 것이다. 마찬가지로 T-2, T-3기에서도 같은 선택이 발생하게 된다. (=no conditioning possible in periods T-1, T-2...)

 

- 무한 반복 Infinitely repeated Prisoners' Dilemma

그렇다면 죄수의 딜레마가 무한 반복되는 상황에서는 어떻게 될까? (T = ∞인 상황, Intuition: There's always a future)

무한반복되는 상황에서는 게임트리를 그리기도 어렵고 역진귀납을 사용하는 것이 불가능하다.

 

만약 t = 1에서부터 서로 협조하여 (C,C)를 택한다고 하자.

이 때, 둘 중 한 명이라고 deviate하고 자백하기를 택한다면 그 이후부터는 계속해서 처벌(D를 선택)한다.

이를 방아쇠 전략, "Grim Trigger" 라고 한다.

 

만약 아무도 배신하지 않는 (C,C)가 이어진다면, player는 매 기마다 2라는 payoff를 얻는다. 따라서

2+2σ+2σ^2+2σ^3 ... = 2/1-σ 이다.

공비수열의 합 공식을 사용해 나온 결과이다.

공비수열의 합 공식 :
(a : 초항/ r : 공비 / n : 더하는 것의 개수)

a(r^n-1) / r-1

a / 1-r ( -1 < 공비(r) < 1 이고 n이 무한대일때)

그러나 만약 D로 이탈하고, 그 다음 기부터 계속해서 D를 선택하게 된다면

 

3 + σ/1-σ*1 = 3 + σ/1-σ 이다.

 

2/1-σ (compliance) >= 3 + σ/1-σ (deviation)

 

-> σ >= 1/2, (C,C) can be sustained in an SPE by Grim Trigger