반복 게임

게임 이론에서 반복 게임은 어떤 베이스 게임(스테이지 게임이라고 함)의 여러 반복으로 이루어진 광범위한 폼 게임이다. 무대 게임은 보통 2인칭 게임 중 하나이다. 반복된 게임은 플레이어가 자신의 현재 행동이 다른 플레이어의 향후 행동에 미치는 영향을 고려해야 한다는 생각을 포착한다. 이러한 영향을 때때로 명성이라고 부른다. 싱글 스테이지 게임이나 싱글 샷 게임은 반복되지 않는 게임의 이름이다.

반복된 게임의 실제 예를 위해, 서로 인접한 두 개의 주유소를 생각해 보라. 그들은 가격을 공개하여 경쟁하며, 동일하고 일정한 한계비용 c(휘발유의 도매 가격)을 가지고 있다. 둘 다 p = 10을 충전하면 공동이익이 극대화돼 모두에게 높은 이익을 가져다준다고 가정해보자. 이것이 그들에게 가장 좋은 결과라는 사실에도 불구하고, 그들은 일탈하려는 동기를 가지고 있다. 가격을 적당히 낮추면 누구나 경쟁사의 모든 소비자를 도용할 수 있어 수익(거의 두 배)을 높일 수 있다. 이들의 이익이 0인 P = c는 이 수익편차가 없는 유일한 가격이다. 즉, 가격 경쟁 게임에서 유일한 내시 평형은 (주유소의 경우) 양쪽 다 p = c를 충전하는 비효율적이다. 이것은 예외라기 보다는 규칙에 가깝다: 스테이지된 게임에서, 나시 평형은 에이전트가 상호작용에서 일관되게 획득할 수 있는 유일한 결과물이며, 보통 그들에게는 비효율적이다. 이는 대리인들이 단지 자신의 개인적인 이익에 관심을 갖고 그들의 행동이 경쟁자들에게 가져다주는 이익이나 비용에 대해 무관심하기 때문이다. 반면 주유소는 인접한 다른 주유소가 있어도 수익을 낸다. 가장 중요한 이유 중 하나는 그들의 상호작용이 일회성이 아니라는 것이다. 이 조건은 두 주유소가 무한정 시간 범위 t = 0, 1, 2, ...에서 가격(스테이지 게임)을 놓고 경쟁하는 반복적인 게임으로 묘사된다.

미세한 게임 vs 무한 반복 게임

반복된 게임은 게임이 얼마나 오랫동안 진행되느냐에 따라 크게 유한과 무한의 두 등급으로 나눌 수 있다.

• 유한양행은 양 플레이어가 특정(그리고 유한한) 라운드의 횟수를 경기하고 있다는 것을 알고, 그 많은 라운드가 진행된 후에 경기가 확실하게 종료되는 것을 말한다. 일반적으로 유한한 게임은 역유도 방식으로 해결할 수 있다.
• 무한 게임은 무한히 많은 횟수가 무한히 진행되는 게임이다. 라운드 수가 무한대인 게임도 게임 속 선수들이 몇 라운드를 하고 있는지 모르는 게임과 (게임 전략 면에서) 동등하다. 무한도전(혹은 몇 번이나 반복되고 있는 게임)은 역도전(역도전)에서 역도전을 시작할 '마지막 라운드'가 없기 때문에 역도전으로 해결할 수 없다.

각 라운드에서 플레이되는 게임이 동일하더라도, 유한하거나 무한정 게임을 반복하면, 일반적으로 매우 다른 결과(균형)와 매우 다른 최적 전략으로 이어질 수 있다.

무한 반복 게임

가장 널리 연구되고 있는 반복게임은 무한정 반복되는 게임이다. 반복된 죄수의 딜레마 게임에서는 스테이지 게임의 내시 전략을 구사하는 것이 아니라, 사회적으로 최적의 전략을 협력하고 구사하는 것이 선호되는 전략인 것으로 나타났다. 무한 반복 게임에서 전략의 필수적인 부분은 이러한 협력 전략에서 벗어나는 선수들을 처벌하는 것이다. 이번 처벌은 남은 경기 동안 두 선수 모두에게 보수가 줄어드는 전략(방아쇠 전략이라고 한다)일 수 있다. 일반적으로 플레이어는 사회적으로 최적의 전략을 구사하기보다는 자신의 보상을 높이기 위해 이기적으로 행동할 수 있다. 다만 상대 선수가 방아쇠 전략을 따른다는 사실이 알려지면 이 단계에서 이탈할 경우 향후 보수가 줄어들 것으로 예상한다. 효과적인 트리거 전략은 협력하는 것이 지금 이기적으로 행동하고 미래에 다른 플레이어의 처벌에 직면하는 것보다 플레이어에 더 많은 효용성을 보장한다.

반복된 게임에서 사회적으로 최적의 평형을 이루고 유지하는 방법을 다루는 이론에는 많은 결과가 있다. 이러한 결과를 총칭하여 "국민적 이론"이라고 한다. 반복된 게임의 중요한 특징은 플레이어의 선호도를 모델링하는 방법이다. 무한히 반복되는 게임에서 선호 관계를 모델링할 수 있는 방법은 여러 가지가 있지만, 두 가지 핵심 관계는 다음과 같다.

• 수단 제한 - 게임이 결과 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$의 경로로 귀결되고 플레이어$$ i가 기본 게임 유틸리티 기능 ${\displaystyle u_{}}$ i$${\$displaystyle u_{i}}$을$$갖는 경우, 플레이어 i의 유틸리티는 다음과 같다.

${\displaystyle U_{i}=\lim _{T\to \inflt}\inf{\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})}$

• 할인 - <1 {\$displaystyle \delta <1}$에 따라 게임에 대한 플레이어의 평가가 시간이 지남에 따라 감소하는 경우 플레이어 i의 유틸리티는 다음과 같다.

${\displaystyle U_{i}=\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t})}$

충분히 참을 수 있는 플레이어(예: $\Delta {\displaystyle }$ ${\displaystyle \delta }$의 충분한 값을 가진 플레이어)$$의 경우, 미니맥스 지불액보다 큰 보상이 있는 모든 전략은 내시 평형일 수 있다는 것을 증명할 수 있다. - 매우 큰 전략 집합이다.

정밀하게 반복된 게임

반복적인 게임은 즉각적인 이득과 장기적인 인센티브 사이의 상호작용을 연구할 수 있게 한다. 미세하게 반복되는 게임은 같은 원샷 스테이지 게임을 여러 개별 시간, 즉 라운드에 걸쳐 반복적으로 하는 게임이다. 각 시간 주기는 0 < t ≤ T로 지수화된다. 여기서 T는 총 기간 수입니다. 선수의 최종 보수는 각 라운드에서 얻은 보상의 합계다.^[1]

정해진 횟수와 알려진 시간의 반복된 게임의 경우, 스테이지 게임이 독특한 나시 평형을 가지고 있다면, 반복된 게임은 각 라운드에서 스테이지 게임 평형을 플레이하는 독특한 서브게임 퍼펙트 나시 평형 전략 프로필을 가지고 있다. 이것은 역유도를 통해 추론할 수 있다. 독특한 스테이지 게임인 내쉬 평형은 앞선 라운드에서 어떤 일이 벌어졌든 상관없이 마지막 라운드에서 치러야 한다. 이를 알고 있는 선수들은 2차전에서 특유의 스테이지 게임인 내쉬 평형에서 이탈할 동기가 없어 이 논리가 다시 1차전에 적용된다.^[2] 엔드포인트에서 게임의 이러한 '비공개'는 체인스토어의 역설에서 관찰할 수 있다.

스테이지 게임이 하나 이상의 나시 평형을 가지고 있다면, 반복된 게임은 복수의 서브게임 퍼펙트 나시 평형을 가지고 있을 수 있다. 마지막 라운드에서 내시 평형을 유지해야 하는 반면, 다중 평형식의 존재는 이전 라운드에서 스테이지 게임인 내시 평형과의 편차를 지원하는 데 사용할 수 있는 보상과 처벌 전략의 가능성을 소개한다.^[2]

반면에 알 수 없거나 불확실한 기간으로 미세하게 반복된 게임은 무한 반복된 게임인 것처럼 간주된다. 이러한 게임에는 역유도를 적용할 수 없다.

정밀하게 반복되는 게임에서의 협력 사례

	X	Y	Z
A	5 , 4	1, 1	2 , 5
B	1, 1	3 , 2	1, 1

예 1: 여러 개의 나시 평형을 가진 2단계 반복 게임

예 1은 복수의 순수 전략인 나시 평형(Nash)의 2단계 반복 게임을 보여준다. 이러한 평형성은 플레이어 2에 대한 보상에 있어 현저한 차이가 있기 때문에 플레이어 1은 플레이어 2에 대한 처벌이나 보상의 가능성을 포함하는 게임의 여러 단계에 걸쳐 전략을 제안할 수 있다. 예를 들어 플레이어 1은 1라운드에서 플레이(A, X)를 하자고 제안할 수 있다. 플레이어 2가 1라운드를 준수할 경우 플레이어 1은 2라운드에서 평형(A, Z)을 재생하여 보상하며, 2라운드(7, 9)에 걸쳐 총 보상이 주어진다.

2번 선수가 합의된 경기(A, X) 대신 1라운드에서 (A, Z)로 이탈하면 1번 선수가 2라운드에서 (B, Y) 평형을 플레이해 응징하겠다고 위협할 수 있다. 이 후자의 상황은 두 선수 모두 더 안 좋은 결과를 낳게 된다. 7).

이런 식으로, 향후 라운드에서의 처벌 위협은 1라운드에서 협력적이고 평형하지 않은 전략을 유도한다. 어떤 미세하게 반복되는 게임의 최종 라운드는 본질적으로 미래의 처벌의 위협을 제거하기 때문에, 마지막 라운드에서 최적의 전략은 항상 게임의 평형성 중 하나가 될 것이다. 사례 1에서 대표되는 게임 내 평형 간 차이에 따라 처벌/보상 전략이 유효하게 된다(게임 전략에 대한 처벌 및 보상의 영향에 대한 자세한 내용은 '처벌과 보상이 있는 공공재 게임'을 참조).

	M	N	O
C	5 , 4	1, 1	0, 5
D	1, 1	3 , 2	1, 1

예 2: 독특한 나시 밸런스가 있는 2단계 반복 게임

사례 2는 독특한 내시 평형 상태에서 2단계의 반복 게임을 보여준다. 여기에는 평형이 하나뿐이기 때문에 경기 2라운드에서 어느 한 선수가 처벌을 위협하거나 보상을 약속할 수 있는 메커니즘은 없다. 이처럼 서브게임 퍼펙트 나시 평형으로서 뒷받침할 수 있는 전략은 게임 특유의 나시 평형 전략(D, N)을 매 라운드마다 구사하는 것뿐이다. 이 경우, 즉 2단계(n=2)에 대해 각 스테이지별로 플레이(D, N)하는 것을 의미하지만, 이는 스테이지 n의 한정된 수에 대해 진실일 것이다.^[3] 해석하기: 이 결과는 알려진 유한한 시간 지평선의 존재는 게임의 모든 라운드에서 협력을 방해한다는 것을 의미한다. 반복된 게임에서의 협력은 라운드 수가 무한하거나 알 수 없는 경우에만 가능하다.

반복된 게임 해결

일반적으로 반복된 게임은 민속적 이론이 제공하는 전략을 사용하여 쉽게 해결된다. 복잡한 반복 게임은 대부분 선형대수법과 가상의 놀이로 표현된 개념에 크게 의존하는 다양한 기법을 사용하여 해결할 수 있다. 무한 반복 게임에서 평형 보상의 특성화를 결정할 수 있다는 점이 공제될 수 있다. 예를 들어 a와 f와 같은 두 가지 보상의 교체를 통해 평균 보상의 프로파일은 a와 f 사이의 가중 평균이 될 수 있다.

불완전한 정보

반복된 게임은 불완전한 정보를 포함할 수 있다. 불완전한 정보를 가진 반복된 게임은 아우만과 매슐러가 개척했다.^[4] 한 플레이어가 정보를 받고 다른 플레이어가 정보를 받지 못하는 상황을 다루기가 더 쉬운 반면, 각 플레이어가 수신한 정보가 독립적일 때 양쪽에 불완전한 정보와 독립적이지 않은 신호를 가진 제로섬 게임도 처리할 수 있다.^[5]

참조

• Fudenberg, Drew; Tirole, Jean (1991). Game Theory. Cambridge: MIT Press. ISBN 0-262-06141-4.
• Mailath, G. & Samuelson, L. (2006). Repeated games and reputations: long-run relationships. New York: Oxford University Press. ISBN 0-19-530079-3.
• Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. Cambridge: MIT Press. ISBN 0-262-15041-7.
• Sorin, Sylvain (2002). A First Course on Zero-Sum Repeated Games. Berlin: Springer. ISBN 3-540-43028-8.

외부 링크

• 가상 플레이를 사용한 포커에 대한 게임-이론적 솔루션
• 반복된 게임에 대한 게임 이론 노트
• 반복된 게임과 체인 스토어 패러독스에 대해