부분게임 완전 균형
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
부분게임 완전 균형은 게임 이론에서 사용되는 개념으로, 게임을 부분 게임으로 나누어 각 부분 게임에서 내쉬 균형을 만족하는 전략을 찾는 방법이다. 라인하르트 젤텐은 모든 게임이 혼합 전략을 포함하는 경우 부분 게임 완전 내시 균형점을 갖는다는 것을 증명했다. 부분 게임 완전 균형은 역진 귀납법을 통해 최종 결과에서부터 거꾸로 추론하여 결정하며, 틱택토와 같은 게임의 분석에 활용된다. 또한, "신뢰할 수 있는" 전략의 개념과 관련하여, 협박이 자신에게 해가 되어 실제로 실행되지 않는 경우를 설명한다. 부분 게임 완전 균형은 금융 옵션 거래, 반복 게임, 치킨 게임 등 다양한 분야에 응용된다.
더 읽어볼만한 페이지
- 게임 이론 - 대연정
대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다. - 게임 이론 - 완전 정보
완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다. - 수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다. - 수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다. - 경제학에 관한 - 노예제
노예제는 한 사람이 타인에게 소유되어 재산처럼 취급받으며 의지에 반해 노동을 강요당하고 보수 없이 사회적 이동이 제한되는 제도로, 고대부터 널리 존재했으나 18세기 이후 폐지 운동으로 대부분 국가에서 금지되었지만 현대에도 다양한 형태로 남아있다. - 경제학에 관한 - 민간 부문
민간 부문은 이윤 추구를 목표로 하는 경제 주체들로 이루어진 영역으로, 국가 경제 체제에 따라 비중과 역할이 다르며, 고용 창출의 원천이 되지만 여러 문제점을 야기하여 국가의 규제를 받는다.
| 부분게임 완전 균형 | |
|---|---|
| 게임 이론 | |
| 하위 개념 | 내시 균형 |
| 교차점 | 진화적으로 안정한 전략 |
| 일반 정보 | |
| 발견자 | 라인하르트 젤텐 |
| 사용 대상 | 확장형 게임 |
| 예시 | 최후통첩 게임 |
2. 부분 게임 완전 균형의 개념
부분 게임 완전 균형은 전개형 게임에서 신뢰성 있는 전략을 찾기 위한 개념이다. 라인하르트 젤텐은 주 게임에서 사용 가능한 모든 선택의 하위 집합을 포함하는 "부분 게임"으로 나눌 수 있는 모든 게임은 부분 게임 완전 내쉬 균형 전략을 가질 것이라고 증명했다.
부분 게임 완전 균형을 찾는 방법은 역진귀납법을 이용하는 것이다. 그림 1과 같이 행위자 1은 {Up, Uq, Dp, Dq}, 행위자 2는 {T, B, L, R}의 전략을 갖는 게임을 예시로 들어보자.
이 게임에는 4개의 부분 게임이 있으며, 진부분 게임은 3개이다. 역진귀납법을 통해 각 부분 게임에서 경기자는 다음과 같은 전략을 취한다.
- 전략 p와 q에 대한 부분 게임: 행위자 1은 (3, 3)의 보수를 얻는 전략 p를 선택한다.
- 전략 L과 R에 대한 부분 게임: 행위자 2는 3> 2이므로 전략 L을 선택한다.
- 전략 T와 B에 대한 부분 게임: 행위자 2는 자기의 보수를 극대화하기 위해 전략 T를 선택한다.
- 전략 U와 D에 대한 부분 게임: 행위자 1은 자기의 보수를 극대화하기 위해 전략 D를 선택한다.
따라서, 부분 게임 완전 균형은 보수 (3, 3)을 얻는 {Dp, L}이다.
불완전 정보를 가진 전개형 게임(그림 2)의 경우, (UA, X), (DA, Y), (DB, Y)가 모두 내쉬 균형이지만, (DA, Y)와 (DB, Y)는 부분 게임 완전 균형이 아니다. 이 중 (UA, X)만이 부분 게임 완전 균형이다.[8]
부분 게임 완전 내쉬 균형은 일반적으로 게임의 최종 귀결로부터 역진 귀납법으로 결정된다. 게임의 나무 상에서 "믿을 수 있는" 수가 아닌 수를 포함하는 가지를 노드에서 제거한다.
2. 1. 부분 게임
전개형 게임에서 부분 게임은 다음 조건을 만족하는 작은 게임을 의미한다.# 단일 노드로 시작한다.
# 원래 게임에서 해당 노드의 모든 후손 노드를 포함한다.
# 정보 집합을 분할하지 않는다. (즉, 어떤 노드가 부분 게임에 속하면, 그 노드와 같은 정보 집합에 있는 모든 노드도 그 부분 게임에 속해야 한다.)
그림 2에서, 행위자 1의 A, B를 나타내는 노드와 그 이후의 모든 전략을 나타낸 것은 하나의 부분 게임이다. 하지만 행위자 2의 노드는 같은 정보집합의 일부이기 때문에 부분 게임이 아니다.
부분 게임 완전 균형을 찾기 위해 역진귀납법을 사용할 수 있다. 역진귀납법은 게임 트리의 마지막 노드에서 시작하여, 각 노드에서 해당 플레이어가 자신의 보수를 최대화하는 전략을 선택하는 방식으로 진행된다.
2. 2. 신뢰성 있는 전략
어떤 전략이 모든 부분 게임에서 내쉬 균형을 이룰 때, 그 전략은 신뢰성 있다고 말한다. 즉, 플레이어가 실제로 그 전략을 따를 것이라고 상대방이 믿을 수 있는 경우이다.[8] 예를 들어, 치킨 게임에서 한 플레이어가 자신의 차에서 핸들을 뜯어낼 수 있는 선택권이 있다면 항상 그 선택을 해야 한다. 왜냐하면 그것은 합리적인 상대방이 똑같은 짓을 할 수 없는 (그리고 둘 다 죽일 수 있는) "부분 게임"으로 이어지기 때문이다. 핸들을 뜯어내는 사람은 항상 게임에서 승리하고 (상대방이 피하도록 만들고), 상대방이 자살적으로 따라 하겠다는 위협은 신뢰할 수 없다.[3]2. 3. 비신뢰적인 위협
부분 게임 완전 균형은 비신뢰적인 위협(non-credible threat)을 제거한다. 비신뢰적인 위협은 특정 플레이어가 실제로 그 위협을 실행하는 것이 자신에게 불리하기 때문에, 상대방이 믿지 않을 위협을 말한다. 예를 들어, 치킨 게임에서 한 플레이어가 자신의 차에서 핸들을 뜯어낼 수 있다면 항상 그렇게 해야 한다. 왜냐하면 그렇게 하면 합리적인 상대방은 같은 행동을 할 수 없고(그러면 둘 다 죽게 된다), 결국 상대방은 핸들을 뜯어낸 플레이어에게 양보하게 되기 때문이다. 즉, 핸들을 뜯어내는 플레이어는 항상 게임에서 승리하며, 상대방이 자살 행위를 따라 하겠다는 위협은 신뢰할 수 없다.3. 부분 게임 완전 균형 탐색 방법
부분 게임 완전 균형은 주로 역진 귀납법을 사용하여 찾는다. 역진 귀납법은 게임의 마지막 부분 게임부터 시작하여, 각 경기자가 최적의 전략을 선택한다고 가정하고, 이를 바탕으로 이전 단계의 최적 전략을 순차적으로 찾아나가는 방법이다.
라인하르트 젤텐은 사용 가능한 모든 선택의 하위 집합을 포함하는 "부분 게임"으로 나눌 수 있는 모든 게임은 부분 게임 완전 내쉬 균형 전략(혼합 전략일 수 있음)을 가질 것이라고 증명했다. 부분 게임 완전성은 완전 정보 게임에만 사용된다. 부분 게임 완전성은 완전하지만 불완전 정보의 전개형 게임에 사용할 수 있다.
부분 게임 완전 내쉬 균형은 일반적으로 게임의 다양한 최종 결과를 "뒤로 귀납법"으로 추론하여, 해당 노드에서 최적이 아닌 비신뢰적 위협을 가하는 경기자가 참여하는 분기를 제거하는 방식으로 찾는다. 역진 귀납법 해법이 잘 알려진 게임 중 하나는 틱택토이지만, 이론적으로는 바둑조차도 모든 경기자에게 최적의 전략이 존재한다.
"신뢰할 수 있는"이라는 단어는 (부분 게임에 도달하는 비가역성을 무시하고) 부분 게임 완전 전략보다 우수한 전략이 존재하지만, 그러한 전략을 수행하겠다는 위협이 위협을 가하는 경기자에게 해를 끼치고 전략의 조합을 방지한다는 점에서 신뢰할 수 없다는 것을 의미한다. 예를 들어 "치킨 게임"에서 한 경기자가 자신의 차에서 핸들을 뜯어낼 수 있다면 항상 그 선택을 해야 한다. 왜냐하면 그것은 합리적인 상대방이 똑같은 짓을 할 수 없는 (그리고 둘 다 죽일 수 있는) "부분 게임"으로 이어지기 때문이다. 핸들을 뜯어내는 사람은 항상 게임에서 승리하고(상대방이 피하도록 만들고), 상대방이 자살적으로 따라 하겠다는 위협은 신뢰할 수 없다.
3. 1. 역진 귀납법
역진 귀납법은 게임의 마지막 부분 게임부터 시작하여, 각 플레이어가 최적의 전략을 선택한다고 가정하고, 이를 바탕으로 이전 단계의 최적 전략을 순차적으로 찾아나가는 방법이다.그림 1과 같은 게임에서 역진 귀납법을 사용하면 다음과 같다.
- p와 q에 대한 부분 게임: 행위자 1은 (3, 3)의 보수를 얻는 전략 p를 선택한다.
- L과 R에 대한 부분 게임: 행위자 2는 3 > 2이므로 전략 L을 선택한다. 따라서 전략 D를 선택했을 때의 보수는 (3, 3)이다.
- T와 B에 대한 부분 게임: 행위자 2는 자신의 보수를 극대화하기 위해 전략 T를 선택한다. 따라서 전략 U를 선택했을 때의 보수는 (1, 4)이다.
- U와 D에 대한 부분 게임: 행위자 1은 자신의 보수를 극대화하기 위해 전략 D를 선택한다.
따라서 부분게임 완전 균형은 {Dp, L}이며, 보수는 (3, 3)이다.
불완전 정보를 가진 게임(그림 2)에서 행위자 1의 전략 A, B를 나타내는 노드와 그 이후의 모든 전략은 하나의 부분게임이다. 행위자 2의 노드는 같은 정보집합의 일부이므로 부분게임이 아니다.
이 게임을 풀기 위해서는 부분게임 1에서 상호 간의 최적 반응을 구하여 내쉬 균형을 찾고, 역진 귀납법을 통해 부분게임 2에서 (A, X) 전략을 대입한다.[8]
따라서 부분게임 완전 균형은 (UA, X)이다.[8]
라인하르트 젤텐은 부분 게임으로 나눌 수 있는 모든 게임은 부분 게임 완전 내쉬 균형 전략을 가질 것이라고 증명했다. 역진 귀납법 해법이 잘 알려진 게임 중 하나는 틱택토이다.
3. 2. 예시
역진귀납법으로 부분게임 완전 균형을 찾는 방법은 그림 1과 같다. 행위자 1의 전략은 {Up, Uq, Dp, Dq}, 행위자 2의 전략은 {T, B, L, R}이다. 이 예시에서 부분게임은 4개, 진부분게임은 3개이다. 각 부분게임에서 경기자는 역진귀납법을 이용해 다음 전략을 취한다.
- 전략 p와 q에 대한 부분게임: 행위자 1은 (3, 3)의 보수를 얻는 전략 p를 선택한다. 전략 L을 선택했을 때 보수는 (3, 3)이다.
- 전략 L과 R에 대한 부분게임: 행위자 2는 3>2이므로 전략 L을 선택하고, 따라서 전략 D를 선택했을 때 보수는 (3, 3)이다.
- 전략 T와 B에 대한 부분게임: 행위자 2는 자기 보수를 극대화하기 위해 전략 T를 선택한다. 따라서 전략 U를 선택했을 때 보수는 (1, 4)이다.
- 전략 U와 D에 대한 부분게임: 행위자 1은 자기 보수를 극대화하기 위해 전략 D를 선택한다.
따라서 부분게임 완전 균형은 보수 (3, 3)을 얻는 {Dp, TL}이다.
불완전 정보를 가진 전개형 게임은 그림 2와 같다. 행위자 1의 전략 A, B를 나타내는 노드와 그 이후의 모든 전략을 나타낸 것이 하나의 부분게임이다. 행위자 2의 노드는 같은 정보집합의 일부이기 때문에 부분게임이 아니다.
첫 번째 보수행렬은 전개형 게임 전체를 정규형으로 나타낸 것이다. 주어진 정보에 따르면 (UA, X), (DA, Y), (DB, Y)가 모두 내쉬 균형이다.
두 번째 보수행렬은 행위자 1의 두 번째 노드부터 시작하는 부분게임을 정규형으로 나타낸 것이다. 여기서 부분게임의 내쉬 균형은 (A, X)이다.
전체 게임의 내쉬 균형 (DA, Y)와 (DB, Y)는 부분게임 완전 균형이 아니다. 내쉬 균형 중 (UA, X)가 부분게임 완전 균형이다.[8]
이 게임을 풀기 위해서는 부분게임 1에서 상호 간 최적 반응을 구하여 내쉬 균형을 찾고, 역진귀납법을 통해 부분게임 2에서 (A, X) 전략을 대입한다.[8]
여기서 점선은 행위자 2는 행위자 1이 A와 B 중 어느 것을 택할지 모른다는 것을 의미한다.
따라서, 부분게임 완전 균형은 (UA, X)이다.
4. 반복 게임에서의 부분 게임 완전 균형
유한 반복 게임에서 단계 게임이 유일한 내쉬 균형만을 갖는다면, 부분 게임 완전 균형은 과거의 행동을 고려하지 않고 현재 부분 게임을 일회성 게임처럼 취급하여 플레이하는 것이다. 대표적인 예시로 유한 반복되는 죄수의 딜레마 게임이 있다. 죄수의 딜레마는 두 명의 유죄 용의자가 심문을 받을 때 침묵하거나 배신할 수 있는 상황을 말한다. 두 용의자가 모두 침묵하면 둘 다 짧은 형을 받는다. 둘 다 배신하면 둘 다 중간 형을 받는다. 만약 서로 반대되는 선택을 한다면, 배신한 용의자는 자유의 몸이 되고 침묵을 지킨 용의자는 긴 형을 받는다. 궁극적으로, 역진 귀납법을 사용하면 유한 반복 죄수의 딜레마의 마지막 부분 게임에서는 플레이어들이 유일한 내쉬 균형(두 플레이어 모두 배신)을 플레이해야 한다. 이 때문에 마지막 부분 게임 이전의 모든 게임도 단기 보수를 최대화하기 위해 내쉬 균형을 플레이하게 된다.[4]
단계 게임이 여러 개의 내쉬 균형을 가지는 유한 반복 게임에서는 "당근과 채찍" 구조를 통해 비 단계 게임 내쉬 균형 행동을 플레이하도록 부분 게임 완전 균형을 구성할 수 있다. 한 플레이어는 비 내쉬 균형 행동을 장려하기 위해 한 단계 게임 내쉬 균형을 사용하고, 다른 플레이어가 배신을 선택할 경우 더 낮은 보수를 가진 단계 게임 내쉬 균형을 사용할 수 있다.[5]
5. 부분 게임 완전 균형의 응용
부분 게임 완전 균형은 여러 분야에서 활용된다.
라인하르트 젤텐은 원래 게임에서 선택할 수 있는 모든 수를 선택할 수 있는 부분 게임으로 분할할 수 있는 모든 게임은 혼합 전략을 포함한 경우 부분 게임 완전 내쉬 균형점을 갖는다는 것을 증명했다. 부분 게임 완전 내시 균형점은 일반적으로 게임의 최종 귀결로부터의 역진 귀납법으로 결정된다. 게임의 나무 상에서 "믿을 수 있는" 수가 아닌 수를 포함하는 가지를 노드에서 제거하는 것이다. 역진 귀납법의 가장 광범위한 응용은 금융에서의 초기 옵션 거래의 수치적 근사이다.
"믿을 수 있는"이라는 용어의 흥미로운 측면은 (부분 게임에 도달하는 과정의 비가역성을 무시하면) 부분 게임 완전 전략보다 우수한 전략이 존재하지만, 그 전략을 실시한다는 협박은 그 협박자 자신에게 유해하며, 그 때문에 그 전략은 실시되지 않을 것이라는 것이다. 예를 들어 치킨 게임의 경우, 한쪽이 먼저 자신의 차의 핸들을 버리는 선택을 할 수 있다면, 그는 버려야 한다. 왜냐하면, 그가 제거했기 때문에, 합리적인 상대방은 같은 것(핸들을 버리고 같이 죽는 것)을 할 수 없게 되기 때문이다. 제거한 쪽이 반드시 이긴다. 상대방은 꺾을 것이기 때문이다. 상대방의 "직진하겠어"라는 협박은 "믿을 수 있는" 것이 아니다. 사실, 한쪽 플레이어가 핸들을 버렸을 때, 상대방의 합리적인 선택지는 '핸들을 버린다'와 '핸들을 둔 채로 간다'에서 '핸들을 둔 채로 간다'라는 부분 게임 완전 내시 균형으로 좁혀진 것이다.
5. 1. 틱택토
뒤로 귀납법 해법이 잘 알려진 게임 중 하나는 틱택토이다. 라인하르트 젤텐은 주 게임에서 사용 가능한 모든 선택의 하위 집합을 포함하는 "부분 게임"으로 나눌 수 있는 모든 게임은 부분 게임 완전 내쉬 균형 전략(비결정적 부분 게임 결정을 제공하는 혼합 전략일 수 있음)을 가질 것이라고 증명했다. 틱택토는 이러한 게임의 예시이다.[2]5. 2. 기타 응용
라인하르트 젤텐은 원래 게임에서 선택할 수 있는 모든 수를 선택할 수 있는 부분 게임으로 분할할 수 있는 모든 게임은 혼합 전략을 포함한 경우 부분 게임 완전 내시 균형점을 갖는다는 것을 증명했다. 부분 게임 완전 내시 균형점은 일반적으로 게임의 최종 귀결로부터의 역진 귀납법으로 결정된다. 게임의 나무 상에서 "믿을 수 있는" 수가 아닌 수를 포함하는 가지를 노드에서 제거함으로써이다. 이 유형의 게임의 예는 틱택토이다. 역진 귀납법의 가장 광범위한 응용은 금융에서의 초기 옵션 거래의 수치적 근사이다."믿을 수 있는"이라는 용어의 흥미로운 측면은 (부분 게임에 도달하는 과정의 비가역성을 무시하면,) 부분 게임 완전 전략보다 우수한 전략이 존재하지만, 그 전략을 실시한다는 협박은 그 협박자 자신에게 유해하며, 그 때문에 그 전략은 실시되지 않을 것이라는 것이다. 예를 들어 치킨 게임의 경우, 한쪽이 먼저 자신의 차의 핸들을 버리는 선택을 할 수 있다면, 그는 버려야 한다. 왜냐하면, 그가 제거했기 때문에, 합리적인 상대방은 같은 것(핸들을 버리고 같이 죽는 것)을 할 수 없게 되기 때문이다. 제거한 쪽이 반드시 이긴다. 상대방은 꺾을 것이기 때문이다. 상대방의 "직진하겠어"라는 협박은 "믿을 수 있는" 것이 아니다. 사실, 한쪽 플레이어가 핸들을 버렸을 때, 상대방의 합리적인 선택지는 '「핸들을 버린다」, 「핸들을 둔 채로 간다」'에서 '「핸들을 둔 채로 간다」'라는 부분 게임 완전 내시 균형으로 좁혀진 것이다.
참조
[1]
서적
An Introduction to Game Theory
Oxford University Press
[2]
서적
Contributions to the Theory of Games (AM-28), Volume II
https://books.google[...]
Princeton University Press
2016-03-02
[3]
서적
Strategy : an introduction to game theory
2013-05-09
[4]
서적
14.12 Economic Applications of Game Theory
Massachusetts Institute of Technology: MIT OpenCourseWare
2012
[5]
서적
Non-cooperative game theory
2015-06-27
[6]
서적
An Introduction to Game Theory
https://archive.org/[...]
Oxford University Press
[7]
서적
An Introduction to Game Theory
https://archive.org/[...]
Oxford University Press
[8]
서적
Strategy : an introduction to game theory
https://www.worldcat[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com