반복게임과 방아쇠 전략

죄수의 딜레마

죄수의 딜레마는 우월전략이 존재하는 게임으로 범인1,2 자백을 선택하여 내쉬 균형을 이루게 되는 게임이다.

해당 균형(자백,자백)은 각 경기자들에게는 우월전략이지만 경기자1,2의 보수가 제일 큰 전략 (부인,부인)을 선택하지 않음으로서

사회적 효용 측면에서 봤을 때는 비효율성이 발생한다. 

만약에 위의 게임이 반복적으로 이루어진다면 '상호협조'를 통해 사회적 효율성을 극대화 할 수 있을까?

 

---

반복 게임

 

1. 매 스테이지에서 동일한 게임이 반복되는 상황이다.

2. 스테이지 게임 자체는 동시게임 또는 순차게임이 될 수 있다.

3. 게임이 반복적으로 이어져 전체적으로는 순차게임의 형태를 가지기 때문에 SPNE을 적용하여 균형을 도출한다.

4. 과거에 각 경기자들이 어떠한 선택을 하였는지 알 수 있다.

5. 각 스테이지 게임의 결과로서 얻은 보수들을 서로 비교하기 위해 할인계수 $\delta$를 사용한다.

 

---

유한 반복 게임

죄수의 딜레마 게임을 2회 반복하여 실시시 게임 트리는 아래와 같이 주어진다. 

 

(N-비협조, C-협조)

(트리 끝의 보수들은 각 스테이지들에서 경기자들이 얻은 보수들을 합계한것이다.)

(각 스테이지가 끝나면 플레이어들은 자신이 어느 node에 위치해 있는지 안다. )

 

 

1. 경기자 2는 node 2-2, 2-3, 2-4, 2-5에서 모두 C보다 N을 선택했을 때의 보수가 더 크므로 N을 선택한다.

 

2. 경기자 1은 2가 모두 N을 선택할것을 알고 있다. 이때 node 1-2, 1-3, 1-4, 1-5에서 C보다 N을 선택하는 것이

보수가 더크므로 모두 N을 선택한다. 

예를 들어 node 1-2에서 N을 선택시 보수가 2, C를 선택시 보수가 1이 된다. 

 

3. 경기자 2는 1이 모두 N을 선택할것을 알고 있다. 이때 node 2-1에서 N을 선택하는 것이 보수가 더크므로

N을 선택한다.

예를 들어 node 2-1의 왼쪽게임을 보면 N선택시 2, C를 선택시 보수가  1이된다.

 

4. 경기자 1은 2가 node 2-1에서 N을 선택할것을 알고 있다. 이때 N선택시 보수가 2, C 선택시 보수가 1이므로

N을 선택한다.

 

결과적으로 경기자 1,2는 모든 노드에서 N을 선택한다.

다시말해 죄수의 딜레마 게임을 2회 반복하여도 모두 협조하는 상황이 균형이 될 수는 없다. 

 

 

유일한 내쉬균형을 가지는 스테이지 게임이 유한번 반복되는 경우,

이 유한반복게임은 해당 내쉬균형이 매 스테이지마다 반복적으로 나타나는 SPNE를 갖는다. 

 

유한반복게임에서는 상호간의 협력이 달성될 수 없다.

---

무한 반복 게임과 방아쇠 전략

 

무한반복게임

동일한 게임을 매 스테이지 반복하는 반복게임에서 게임의 종료시점에 대한 불확실성이 있는 경우를 말한다.

즉 각 경기자들은 게임이 언제 끝날 줄 모른다.

 

방아쇠 전략

방아쇠 전략이란 방아쇠에 손을 올려놓고 있다는 의미로서 상대가 합의된 균형에서 벋어날 경우 즉시 보복을 하는 전략이다.

 

무한반복게임에서 방아쇠 전략을 통해서 게임의 균형을 도출하기 위해서는 마지막 기가 없어서 역진귀납법을 이용해 SPNE을 찾기는 불가

따라서 SPNE의 정의에 입각한 분석이 필요하다.

SPNE(부분게임완전내쉬균형)은 모든 부분게임에서 각 경기자들이 합리적인 선택을 하는 균형을 의미한다.

부분게임을 협조가 유지되는 경우와 협조가 깨진경우로 나누어서 두 가지 경우에서 모두 합리적인 균형을 도출한다.

 

 

위와 같이 (C,C)로 균형을 유지하다가 한명이 균형에서 이탈시 즉시 전략을 N으로 수정하여 보복하는 전략이다.

각 경기자들에게 이탈할 유인이 존재하는지를 따지기 위해서는 이탈발생이전은 몇기가 반복되었건

이탈유인에 영향을 주지 않으므로

이탈이 발생한 이후 시점부터 이탈유인이 존재하는지 따져본다. 

 

균형이 계속 유지되었을 때의 보수보다 이탈시 보수가 더 컸을  때 균형에서 이탈할 유인이 존재한다.

 

 

 

방아쇠전략을 통해서 무한 반복게임의 협조-균형이 이루어질 조건은 협조유지시 보상이 이탈시 보상보다 더 커야한다.

 

방아쇠전략 협조-균형 유지 조건

균형이 유지될 조건 

1. 이탈시 받는 보상 d가 작다.

2. 균형 유지시 받는 보상 c가 크다.

3. 이탈 이후 보복으로 받는 보상 n이 작다. 

4. $\delta$가 클수록 이탈유인이 작다. 

($\delta$가 크다는 것은 할인계수가 크다는 것이고 할인계수가 클수록 미래의 보상이 현재가치화 했을 때 보상의 감소가 적다.)

 

할인계수는 미래의 보상에 대한 위험성이 작을수록 커진다.

방아쇠 전략에서 균형이 유지되기 위해서는 각 경기자들에게 미래보상의 확실성이 보장되어야한다. 

 

---

일회 이탈 원리

반복게임에서 1회의 이탈로 이득을 볼 수 없다면 2회 이상의 이탈로도 이득을 볼 수 없다. 

 

 

무한게임과 무기한 게임

무한게임: 스테이지가 끝없이 반복

무기한게임: 스테이지의 끝이 있으나 언제 끝날지에 대해서 모름 ( p를 통해 게임이 계속될 확률을 보상에 결부시킨다.)

 

 

대중 정리 (Folk Theorm)

 

어느 스테이지 게임이 무한히 반복되며, 이 스테이지 게임의 내쉬균형에서 1과 2가 얻는 균형보수가 각각 $u_1^*,u_2^*$라 하자.

이 게임에서 평균적으로 달성 가능한 임의의 보수조합 $(u_1,u_2)$가 있고 이것이 $u_1>u_1^*$와 $u_2>u_2^*$를 만족한다면

할인계수 $\delta$가 충분히 클 경우 1과 2가 매기 평균적으로 각각 $u_1$과 $u_2$를 얻는 SPNE가 존재한다.

 

방아쇠 전략에서 보았던 무한히 반복되는 죄수의 딜레마 게임과 같이

각 스테이지에서 모든 경기자들에게 내쉬균형보다 더 좋은 보수를 주는 균형이 존재하고

할인계수 $\delta$가 충분히 큰 (미래의 보상이 확실성이 높은) 상황에서는 더 좋은 보수를 주는 균형이 SPNE가 될 수 있다. 

---