전개형 게임

3. 정보의 종류

전개형 게임은 정보의 완전성 여부에 따라 다음과 같이 분류할 수 있다.

• '''완전 정보 게임 (Game with Perfect Information)''' : 모든 플레이어가 게임의 모든 단계에서 게임 초기에 무슨 일이 일어났는지 정확히 알고 있는 게임이다. 모든 정보 집합은 홑원소 집합으로 구성된다.
• '''불완전 정보 게임 (Game with Imperfect Information)''' : 플레이어가 게임의 일부 정보를 모르는 경우이다. 정보 집합이 둘 이상의 노드를 포함할 수 있다.
• '''완비 정보 게임 (Game with Complete Information)''' : 모든 플레이어가 게임의 규칙(게임 트리)을 알고 있는 게임이다.
• '''불완비 정보 게임 (Game with Incomplete Information)''' : 플레이어가 게임의 규칙, 보수, 또는 상대방의 유형(type)을 정확히 모르는 경우이다.

3. 1. 완전 정보 게임 (Game with Perfect Information)

3. 2. 불완전 정보 게임 (Game with Imperfect Information)

3. 3. 완비 정보 게임 (Game with Complete Information)

3. 4. 불완비 정보 게임 (Game with Incomplete Information)

4. 완전성과 기억

게임의 완전성은 정보와 관련된 중요한 개념이다. 일부 교과서에서는 전개형 게임을 보상만 있는 게임 트리로 정의하고, 다른 요소들은 나중에 추가하기도 한다. 그러나 이 문서는 1953년 해럴드 W. 쿤이 소개한 일반적인 정의를 따르며, 이는 1928년 존 폰 노이만의 초기 정의를 확장한 것이다.

''n''명의 플레이어를 가진 전개형 게임은 다음과 같이 구성된다.

• 유한한 ''n''개의 플레이어 집합
• 게임 트리
• 게임 트리의 각 터미널(잎) 노드는 ''보상''의 ''n''-튜플을 가짐
• 게임 트리의 비터미널 노드는 ''n''+1개의 하위 집합으로 분할됨 (각 플레이어에 하나씩, 그리고 기회(또는 자연) 플레이어를 위한 특별한 하위 집합)
• 기회 플레이어의 각 노드는 나가는 간선에 대한 확률 분포를 가짐
• 합리적인 플레이어의 각 노드 집합은 정보 집합으로 분할됨
• 동일한 정보 집합의 두 노드의 나가는 간선 간에는 일대일 대응이 있음
• 트리에서 루트에서 터미널 노드까지의 모든 경로는 각 정보 집합을 최대 한 번만 통과
• 게임의 완전한 설명은 플레이어 간의 공통 지식

완전한 확장형 표현은 다음을 명시한다.

• 게임의 참가자
• 모든 참가자에 대해 그들이 움직일 수 있는 모든 기회
• 각 참가자가 각 움직임에서 할 수 있는 것
• 각 참가자가 모든 움직임에 대해 아는 것
• 모든 가능한 움직임 조합에 대해 각 참가자가 받는 보수

위 그림의 게임에는 두 명의 참가자, 1과 2가 있다. 비단말 노드의 숫자는 해당 결정 노드가 어떤 참가자에 속하는지 나타내고, 단말 노드의 숫자는 참가자에게 주어지는 보수를 나타낸다. 그래프의 각 변의 레이블은 해당 변이 나타내는 행동의 이름이다.

만약 참가자 1이 ''D''를 플레이한다면, 참가자 2는 자신의 보수를 극대화하기 위해 ''U''를 플레이할 것이고, 따라서 참가자 1은 1만 받게 된다. 하지만, 만약 참가자 1이 ''U''를 플레이한다면, 참가자 2는 ''D''를 플레이하여 자신의 보수를 극대화하고 참가자 1은 2를 받게 된다. 참가자 1은 1보다 2를 선호하므로 ''U''를 플레이하고 참가자 2는 ''D''를 플레이할 것이다. 이것이 부분 게임 완전 균형이다.

'''정보 집합'''은 다음과 같은 결정 노드의 집합이다.

• 집합의 모든 노드는 하나의 플레이어에 속한다.
• 게임이 정보 집합에 도달하면, 움직이려는 플레이어는 정보 집합 내의 노드를 구별할 수 없다.

확장형에서는 정보 집합이 해당 집합의 모든 노드를 연결하는 점선 또는 때로는 해당 집합의 모든 노드 주위에 그려진 루프로 표시된다.

게임이 둘 이상의 멤버를 가진 정보 집합을 갖는 경우, 해당 게임은 '''불완전 정보'''를 갖는다고 한다. '''완전 정보'''를 가진 게임은 게임의 어떤 단계에서든, 모든 플레이어가 게임 초기에 무슨 일이 일어났는지 정확히 알고 있는 게임이다. 즉, 모든 정보 집합은 싱글톤 집합이다.^[1][2] 완전 정보가 없는 모든 게임은 불완전 정보를 갖는다.

위 그림의 게임은 첫번째 게임과 동일하지만, 플레이어 2는 플레이어 1이 무엇을 하는지 알지 못한다.

두 번째 게임에서는 플레이어 1이 ''D''를 플레이하고 플레이어 2가 ''U''를 플레이하며, 플레이어 2는 플레이어 1이 반드시 ''D''를 플레이할 것이라는 믿음을 갖는 완전 베이즈 균형이 존재한다.

이 게임을 '''내시 균형'''^[3]을 더 쉽게 풀기 위해, '''정규형'''으로 변환할 수 있다.^[4] 이는 '''동시/순차''' 게임이므로, 플레이어 1과 플레이어 2는 각각 두 개의 '''전략'''을 갖는다.^[5]

	Up (U)	Down (D)
Up (U)	(0,0)	(2,1)
Down (D)	(1,2)	(3,1)

각 움직임 조합에 대한 고유한 보상이 있는 2x2 행렬을 갖게 된다. 정규형 게임을 사용하여 게임을 풀고 두 플레이어 모두에게 지배 전략을 식별할 수 있다.

• 플레이어 1이 Up (U)을 플레이하면, 플레이어 2는 Down (D')을 플레이하는 것을 선호한다 (보상 1>0).
• 플레이어 1이 Down (D)을 플레이하면, 플레이어 2는 Up (U')을 플레이하는 것을 선호한다 (보상 2>1).
• 플레이어 2가 Up (U')을 플레이하면, 플레이어 1은 Down (D)을 플레이하는 것을 선호합니다 (보상 1>0).
• 플레이어 2가 Down (D')을 플레이하면, 플레이어 1은 Down (D)을 플레이하는 것을 선호합니다 (3>2).

이러한 선호도는 행렬 내에 표시될 수 있으며, 두 플레이어 모두 선호도가 있는 상자는 내시 균형을 제공한다. 이 특정 게임은 (D,U')의 단일 해를 가지며 (1,2)의 보상을 갖는다.

플레이어가 게임의 정확한 보수가 무엇인지 또는 상대방의 '''유형'''이 무엇인지 정확히 모를 수도 있다. 이러한 종류의 게임은 '''불완전 정보'''를 가지고 있다. 확장형에서는 소위 '''하사니 변환'''을 사용하여 완전하지만 불완전한 정보를 가진 게임으로 표현된다. 이 변환은 게임에 ''자연의 선택'' 또는 ''신의 선택''이라는 개념을 도입한다.

왼쪽 그림의 게임은 완전 정보(모든 플레이어와 보수가 모든 사람에게 알려짐)이지만 불완전 정보(고용주는 자연의 움직임이 무엇인지 모름)의 게임이다.

4. 1. 완전 기억 게임 (Game with Perfect Recall)

Game with perfect recall^영어은 한국어로 완전 기억 게임이라고 번역되며, 모든 플레이어가 자신의 과거 선택지를 모두 기억하는 게임을 의미한다.^{[1] [2]} 완전 정보 게임은 항상 완전 기억 게임이다.

4. 2. 불완전 기억 게임 (Game with Imperfect Recall)

모든 플레이어가 자신의 과거 선택지를 모두 기억하는 게임을 완전 기억 게임이라고 부른다. 완전 정보 게임은 완전 기억 게임이다. 완전 기억이며 불완전 정보인 게임 트리의 예는 그림 3과 같다. 불완전 기억 게임 트리의 예는 그림 4와 같다. 그림 4의 플레이어 A처럼 한 수 전의 기억을 상실하는 플레이어는 상상하기 어렵지만, 예를 들어 플레이어 A를 2명의 팀으로 생각하고, 턴과 턴 사이에는 다른 팀원이 지시하며 팀원끼리는 정보 교환이 불가능하다고 하면, 현실적인 한 예가 된다.

5. 한국 정치에서의 응용

전개형 게임은 한국 정치의 다양한 상황을 분석하는 데 유용하게 활용될 수 있다.

6. 전개형 게임과 표준형 게임

일부 입문 교과서에서는 전개형 게임을 게임 트리에 보상만 있는 것으로 정의하고(불완전하거나 불완전한 정보 없음), 다른 요소들을 세분화하여 다음 장에서 추가하기도 한다. 그러나 이 문서는 1953년 해럴드 W. 쿤이 소개하고 1928년 폰 노이만의 초기 정의를 확장한 일반적인 정의를 따른다. ''n''명의 플레이어를 가진 전개형 게임은 다음과 같이 구성된다.

• 유한한 ''n''개의 (합리적인) 플레이어 집합
• 게임 트리
• 게임 트리의 각 터미널(잎) 노드는 모든 가능한 플레이의 끝에서 각 플레이어에 대한 보상을 나타내는 ''보상''의 ''n''-튜플을 갖는다.
• 게임 트리의 비터미널 노드는 ''n''+1개의 하위 집합으로 분할된다. 각 (합리적인) 플레이어에 대해 하나씩, 그리고 기회(또는 자연)라고 하는 가상의 플레이어를 위한 특별한 하위 집합이 있다. 각 플레이어의 노드 하위 집합을 "플레이어의 노드"라고 한다. (완전한 정보 게임은 기회 노드의 빈 집합을 갖는다.)
• 기회 플레이어의 각 노드는 나가는 간선에 대한 확률 분포를 갖는다.
• 합리적인 플레이어의 각 노드 집합은 정보 집합으로 더 분할되는데, 이는 플레이어가 이동할 때 특정 선택을 구별할 수 없도록 만든다.
• * 동일한 정보 집합의 두 노드의 나가는 간선 간에는 일대일 대응이 있으며, 따라서 정보 집합의 모든 나가는 간선의 집합은 동치류로 분할되며, 각 클래스는 플레이어의 움직임에 대한 가능한 선택을 나타낸다.
• * 트리에서 루트에서 터미널 노드까지의 모든 (유향) 경로는 각 정보 집합을 최대 한 번만 통과할 수 있다.
• 위 매개변수로 지정된 게임의 완전한 설명은 플레이어 간의 공통 지식이다.

6. 1. 표준형 게임 (Normal-form game)

6. 2. 전개형 게임과 표준형 게임의 관계

참조

_[1] 기타 Infinite Games, Yurii Khomskii (2010) https://www.math.uni[...]
_[2] Youtube Infinite Chess, PBS Infinite Series https://www.youtube.[...]
_[3] 서적 Strategy : an introduction to game theory 2013-05-09
_[4] 서적 Strategy : an introduction to game theory 2013-05-09
_[5] 서적 Strategy : an introduction to game theory 2013-05-09
_[6] 서적 岩波数学辞典-第3版 岩波書店 1985-12
_[7] 서적 ゲーム理論 有斐閣 1997-01
_[8] 서적 入門ゲーム理論―戦略的思考の科学 日本評論社 2003-03
_[9] 서적 ゲーム理論入門 日本経済新聞社 2001-01