반복 게임

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 반복 게임의 유형
- 2.1. 유한 반복 게임
- 2.2. 무한 반복 게임
3. 죄수의 딜레마 반복 게임
- 3.1. 전략
4. 불완전 정보 반복 게임
5. 현실에서의 응용
- 5.1. 산업 조직론
참조

1. 개요

반복 게임은 게임이 여러 번 반복되는 상황을 분석하는 게임 이론의 한 분야이다. 반복 횟수에 따라 유한 반복 게임과 무한 반복 게임으로 나뉘며, 유한 반복 게임은 종료 시점이 정해져 있고, 무한 반복 게임은 무한히 반복되거나 종료 시점을 알 수 없는 경우를 다룬다. 유한 반복 게임에서는 젤텐의 정리에 따라 1회 게임의 내시 균형이 반복되지만, 내시 균형이 여러 개 존재할 경우 협력적인 결과가 도출될 수도 있다. 무한 반복 게임에서는 죄수의 딜레마와 같은 상황에서 협력이 가능하며, 할인 인자가 충분히 클 경우 1회 게임 내시 균형보다 높은 보수 조합에 도달할 수 있다. 이러한 원리를 통해 담합과 카르텔의 지속 가능성을 설명하기도 하며, 민속 정리가 중요한 역할을 한다. 반복 게임은 죄수의 딜레마, 불완전 정보, 산업 조직론, 국제 관계, 정치 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

게임 이론 - 대연정
대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다.
게임 이론 - 완전 정보
완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다.
수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
경제학에 관한 - 노예제
노예제는 한 사람이 타인에게 소유되어 재산처럼 취급받으며 의지에 반해 노동을 강요당하고 보수 없이 사회적 이동이 제한되는 제도로, 고대부터 널리 존재했으나 18세기 이후 폐지 운동으로 대부분 국가에서 금지되었지만 현대에도 다양한 형태로 남아있다.
경제학에 관한 - 민간 부문
민간 부문은 이윤 추구를 목표로 하는 경제 주체들로 이루어진 영역으로, 국가 경제 체제에 따라 비중과 역할이 다르며, 고용 창출의 원천이 되지만 여러 문제점을 야기하여 국가의 규제를 받는다.

반복 게임
게임 정보
유형	게임 이론
하위 유형	반복 게임
관련 항목	죄수의 딜레마 민간재 공유지의 비극
개요
설명	반복 게임은 기본 게임이 여러 번 반복되는 게임 이론의 한 분야이다.
특징	각 플레이어는 기본 게임의 각 반복에서 상대방의 이전 행동을 어느 정도까지 "기억"할 수 있으며, 그에 따라 전략을 변경할 수 있다.
분석	반복은 협력에 대한 인센티브로 작용할 수 있으며, 이는 한 번의 게임에서는 불가능하다.
주요 개념
할인 인자 (δ)	미래 수익의 현재 가치를 나타내는 데 사용되며, 플레이어가 미래 보상보다 현재 보상을 얼마나 중시하는지를 반영한다.
방아쇠 전략	상대방이 협력하지 않으면 영원히 협력을 중단하는 전략이다.
민 포크 정리	할인 인자가 충분히 높으면, 반복 게임에서 합리적인 플레이어가 협력적인 결과를 포함한 광범위한 결과를 지원할 수 있다는 정리이다.
예시
죄수의 딜레마 반복	죄수의 딜레마를 반복적으로 플레이하면, 플레이어들이 상호 협력하는 전략을 개발할 수 있다.
민간재 반복 게임	민간재 공급 게임을 반복하면, 플레이어들이 공통의 이익을 위해 자발적으로 기여하는 전략을 개발할 수 있다.
공유지의 비극 반복 게임	공유지의 비극 상황을 반복하면, 플레이어들이 공유 자원을 지속 가능하게 관리하는 전략을 개발할 수 있다.
응용
경제학	기업 간의 경쟁, 국제 무역 협정 등을 분석하는 데 사용된다.
정치학	국가 간의 관계, 정치적 협상 등을 분석하는 데 사용된다.
진화 생물학	동물의 협력 행동, 사회성 곤충의 행동 등을 설명하는 데 사용된다.

2. 반복 게임의 유형

반복 게임은 반복 횟수에 따라 유한 반복 게임과 무한 반복 게임으로 나뉜다.

'''유한 반복 게임'''
'''무한 반복 게임'''

젤텐에 따르면, 반복 게임이 유한인지 무한인지에 따라 게임의 결과와 최적 전략은 매우 달라질 수 있다. 유한 게임은 역진 귀납법으로 풀 수 있지만, 무한 게임은 "마지막 라운드"가 없으므로 역진 귀납법으로 풀 수 없다.^[2]

2. 1. 유한 반복 게임

역진귀납법을 통해 부분게임 완전 균형을 구하는 방법으로 균형을 분석하는 유한 반복 게임은 게임의 종료 시점이 정해져 있는 경우이다. 유한 반복 게임의 균형은 1회 게임의 내시 균형 개수에 따라 결과가 달라진다.

1회 게임에 내시 균형이 하나만 존재할 경우, 유한 반복 게임의 균형은 매번 그 내시 균형이 반복되는 것이다. 이를 젤텐의 정리라고 한다.^[6] 마지막(T)기에는 게임이 종료되므로 경기자들은 서로 협력할 유인이 없고, T-1기에는 T기에 협력할 유인이 없다는 것을 알기 때문에 T-1기에 배신하더라도 보복으로 협력을 강제할 수 없다.^[7] 따라서 T-1기에도 협력하지 않는 것이 최선이며, 이 과정을 반복하면 1회 게임 내시 균형이 T회 반복되는 결과가 된다.

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

예시 2: 고유한 내쉬 균형이 있는 2단계 반복 게임

'''예시 2'''는 고유한 내쉬 균형이 있는 2단계 반복 게임을 보여준다. 균형이 하나뿐이므로, 두 플레이어 모두 게임의 두 번째 라운드에서 처벌을 위협하거나 보상을 약속할 수 없다. 따라서 유일한 전략은 게임의 고유한 내쉬 균형 전략 (D, N)을 매 라운드마다 플레이하는 것이다. 이는 알려진 유한 시간 지평선의 존재 자체가 게임의 모든 라운드에서 협력을 방해한다는 것을 의미한다.^[3]

내시 균형이 여러 개인 1회 게임을 유한 반복할 경우, 매 기에 나타날 수 있는 내시 균형의 조합은 유한 반복 게임의 부분 게임 완전 균형이 될 수 있다.^[8] 그 외에도 반복 게임의 각 단계에서 내시 균형이 아닌 전략 조합이 선택되는 것도 가능하다. 경기자가 원하는 행동을 상대방이 선택하면 정상 경로를 따르고, 그렇지 않으면 보복 경로를 따르는 전략을 공표하면, 각 단계에서 내시 균형이 아니지만 더 높은 보수를 얻을 수 있는 전략 조합이 선택될 수 있다.^[8]^[9]^[10]

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

예시 1: 다수의 내쉬 균형이 있는 2단계 반복 게임

'''예시 1'''은 여러 개의 순수 전략 내쉬 균형이 있는 2단계 반복 게임을 보여준다. 플레이어 2의 보상 측면에서 차이가 크므로, 플레이어 1은 플레이어 2에 대한 처벌 또는 보상 가능성을 포함하는 전략을 제안할 수 있다. 예를 들어, 플레이어 1은 첫 번째 라운드에서 (A, X)를 플레이하고, 플레이어 2가 동의하면 2라운드에서 균형 (A, Z)를 플레이하여 보상할 수 있다. 이는 두 라운드에 걸쳐 총 (7, 9)의 보상을 얻는다.

만약 플레이어 2가 (A, X) 대신 1라운드에서 (A, Z)로 벗어나는 경우, 플레이어 1은 2라운드에서 (B, Y) 균형을 플레이하여 처벌하겠다고 위협할 수 있다. 이는 보상 (5, 7)을 얻어 두 플레이어 모두에게 손해를 입힌다. 이처럼 미래 라운드에서의 처벌 위협은 첫 번째 라운드에서 협력적인 비균형 전략에 동기를 부여한다.

2. 2. 무한 반복 게임

무한 반복 게임은 게임이 무한히 반복되거나 언제 끝날지 알 수 없는 상황을 말한다.^[6]^[7] 이러한 게임에서는 협력적인 행동이 균형으로 나타날 수 있다.

죄수의 딜레마 게임이 무한히 반복되면, 참가자들은 서로 협력하여 1회성 게임의 내시 균형보다 더 큰 보상을 얻을 수 있다. 이는 상대방이 배신할 경우 보복하여 협력했을 때보다 낮은 보수를 받게 할 수 있기 때문이다. 예를 들어, 상대방이 한 번 배신하면 영원히 보복하는 무자비 전략을 사용한다고 가정해 보자. 이때, 협력으로 얻는 보수의 현재할인가치가 배신 후 보복 상황에서 얻는 보수의 기대 현재할인가치보다 크다면, 참가자들은 협력하는 것이 합리적이다.

각 경기자가 미래의 보수를 충분히 중요하게 생각한다면 (즉, 할인 인자가 충분히 크다면),^[11] 1회성 게임의 내시 균형보다 더 높은 보수 조합에 도달할 수 있다.^[6] 이를 일반화한 것이 전래 정리(Folk theorem)인데, 사회적으로 실현 가능하고 개인 합리성 조건을 만족하는 어떤 보수 조합이라도 무한 반복 게임의 균형이 될 수 있도록 하는 할인 인자가 존재한다는 정리이다.^[12]^[9]

무한 반복 게임의 핵심은 개별 경기자가 미래의 보수를 고려하여 협력할 수 있다는 것이다. 이는 비협조적인 1회성 게임의 내시 균형보다 더 높은 보수를 얻을 수 있게 해준다. 산업조직론에서는 이러한 논리를 통해 담합과 카르텔의 지속 가능성을 설명한다.^[6]

반복 게임에서 협력에서 벗어나는 플레이어를 처벌하는 것은 협력을 유지하는 데 중요하다. 처벌은 게임의 나머지 기간 동안 두 플레이어 모두에게 보상이 감소하는 전략을 사용하는 것일 수 있다(트리거 전략). 효과적인 트리거 전략은 협력하는 것이 현재 이기적으로 행동하고 미래에 처벌받는 것보다 더 큰 효용을 보장한다.

반복 게임에서 사회적으로 최적의 균형을 달성하고 유지하는 방법에 대한 많은 정리가 있는데, 이를 통틀어 "민속 정리"라고 부른다.

무한 반복 게임에서 선호 관계를 나타내는 방법에는 여러 가지가 있지만, 주요한 두 가지 방법은 다음과 같다.

평균의 극한: 게임 결과의 경로가 $x_t$ 이고 플레이어 ''i''의 기본 게임 효용 함수가 $u_i$ 인 경우, 플레이어 ''i''의 효용은 다음과 같다.

:

U_i = \lim_{T\to \infty} \inf \frac{1}{T} \sum_{t=0}^{T} u_i(x_t)

할인: 플레이어 i의 게임 가치가 할인율 $\delta<1$ 에 따라 시간이 지남에 따라 감소하는 경우, 플레이어 ''i''의 효용은 다음과 같다.

:

U_i = \sum_{t \geq 0} \delta^t u_i(x_t)

충분히 인내심 있는 플레이어 (즉,

\delta

값이 충분히 높은 플레이어)의 경우, 미니맥스 보상보다 큰 보상을 갖는 모든 전략은 내쉬 균형이 될 수 있다.

3. 죄수의 딜레마 반복 게임

죄수의 딜레마는 반복 게임의 대표적인 예시이다. 1회성 죄수의 딜레마 게임에서는 상호 배신이 유일한 내쉬 균형이지만, 반복 게임에서는 다양한 전략이 나타날 수 있다.

무한 반복 게임에서는 상대방이 협력 관계에서 배신할 경우 보복하여 상호 협력할 때 얻을 수 있는 보수보다 낮은 보수를 얻게 할 수 있다. 예를 들어 상대방이 한 번 배신할 경우 영원히 보복하는 무자비 전략을 사용할 수 있다. 이때 상호 협력으로 얻을 수 있는 보수의 현재할인가치가 배신 후 보복 국면으로 진입하는 시나리오에서 얻을 보수의 기대 현재할인가치보다 높다면, 경기자들은 상호 협력하는 것이 합리적인 전략이 된다.^[6]^[7]

각 경기자에게 1회 게임 내쉬 균형보다 높은 수준의 할인 인자(discount factor)가 충분히 크다면, 즉 할인율이 작은 경우라면 1회 게임 내쉬 균형보다 높은 보수 조합에 도달할 수 있다.^[11]^[6] 이를 일반화한 것이 전래 정리(Folk theorem)이다.^[12]^[9]

산업조직론에서는 무한 반복 게임에서 경기자 간 협력을 통해 높은 보수를 얻을 수 있다는 논리를 통해 담합과 카르텔의 지속 가능성을 설명한다.^[6]

3. 1. 전략

반복 게임에서 가장 널리 연구되는 것은 무한히 반복되는 게임이다. 반복 죄수의 딜레마 게임에서 선호되는 전략은 단계 게임의 내쉬 균형 전략을 사용하는 것이 아니라 협력하여 사회적으로 최적의 전략을 사용하는 것이다. 무한 반복 게임에서 전략의 필수적인 부분은 이러한 협력 전략에서 벗어나는 플레이어를 처벌하는 것이다. 처벌은 게임의 나머지 기간 동안 두 플레이어 모두에게 보상이 감소하는 전략을 사용하는 것일 수 있다(트리거 전략).^[1] 플레이어는 일반적으로 사회적으로 최적의 전략을 사용하는 것보다 자신의 보상을 증가시키기 위해 이기적으로 행동하도록 선택할 수 있다. 그러나 다른 플레이어가 트리거 전략을 따르고 있다는 것을 알게 되면, 이 단계에서 벗어나는 경우 미래에 보상이 감소할 것으로 예상한다. 효과적인 트리거 전략은 협력하는 것이 현재 이기적으로 행동하고 미래에 다른 플레이어의 처벌에 직면하는 것보다 플레이어에게 더 많은 효용을 보장한다.

반복 게임에서 사회적으로 최적의 균형을 달성하고 유지하는 방법에 대한 많은 정리 결과가 있다. 이러한 결과는 통틀어 "민속 정리"라고 불린다.

죄수의 딜레마에서 자신의 이득은 상대가 협력적이든 비협력적이든 자신이 비협력적인 경우 더 커지기 때문에, 1회성 게임에서는 이기적인 개인은 비협력을 선택하고 상대방도 그렇게 하기 때문에 함께 비협력하는 것이 유일한 내쉬 균형이 된다.

그러나 이 죄수의 딜레마 게임을 여러 번 반복할 수 있다면, 전략은 한 번의 행동 선택이 아니라 과거의 자신과 상대방의 행동에 따라 행동을 바꾸거나 바꾸지 않는 프로그램이 된다. 예를 들어, 처음에는 협력하고 상대방이 협력하는 한 협력을 계속하지만, 상대방이 한 번 비협력적인 태도를 보이면 비협력으로 전환하고 이후 영구적으로 비협력을 취하는 트리거 전략이나, 처음에는 협력하고, 상대방이 협력하면 협력, 상대방이 비협력하면 비협력으로 대응하는 눈에는 눈 전략이 등장한다.^[1]

반복 게임에서의 이득은 시간을 통해 나타나므로, 미래의 예상 이득은 할인된다. 할인율이 충분히 작으면, 지금 상대를 배신하여 비협력적인 태도를 취함으로써 얻는 일시적인 이익을 상대방의 보복으로 인해 미래에 입을 손실이 상회하므로, 눈에는 눈 전략이나 트리거 전략이 내쉬 균형이 되고, 그 결과 함께 협력하는 상태가 지속된다. 이 사실을 일반화한 것이 포크 정리이다.

4. 불완전 정보 반복 게임

불완전 정보를 가진 반복 게임은 아우만과 매슐러에 의해 처음 연구되었다.^[4] 한쪽 플레이어는 정보를 가지고 다른 쪽은 그렇지 않은 상황, 그리고 각 플레이어가 받는 정보가 독립적인 상황을 다루는 것이 더 쉽지만, 양쪽에 불완전 정보가 있고 신호가 독립적이지 않은 제로섬 게임도 다룰 수 있다.^[5]

5. 현실에서의 응용

반복 게임 이론은 현실의 다양한 문제에 적용될 수 있다. 산업조직론에서는 기업 간의 담합과 카르텔의 지속 가능성을 설명하는 데 사용된다.^[6]

5. 1. 산업 조직론

산업조직론에서는 무한반복게임에서 경기자 간 협력을 통해 높은 보수를 얻을 수 있다는 논리를 통해 담합과 카르텔의 지속 가능성을 설명한다.^[6] 기업들이 장기적인 관계를 맺고 미래의 이익을 고려한다면, 단기적인 이익을 위해 배신하기보다는 서로 협력하여 담합을 유지할 유인이 생긴다는 것이다.

참조

_[1] 웹사이트 Finitely Repeated Games https://vknight.org/[...] 2017-12-06
_[2] 논문 Finitely Repeated Games 1985
_[3] 웹사이트 "Repeated Games I: Perfect Monitoring" https://web.stanford[...] 2017-12-12
_[4] 서적 Repeated Games with Incomplete Information https://books.google[...] MIT Press
_[5] 서적 Proceedings of the International Congress of Mathematicians, Berkeley 1986 American Mathematical Society
_[6] 서적 https://archive.org/[...]
_[7] 서적
_[8] 서적 https://archive.org/[...]
_[9] 서적
_[10] 저널 https://archive.org/[...]
_[11] 문서
_[12] 문서

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com