정보 집합

게임 이론에서 정보 집합(information set)은 플레이어가 이용할 수 있는 행동과 각 행동의 잠재적 결과를 포함하여 게임에서 의사 결정을 위한 기초이다. 이것은 이전 행동이나 게임의 현재 상태에 대한 불완전한 정보로 인해 플레이어가 움직일 때 구별할 수 없는 의사 결정 노드들의 모음으로 구성된다. 다시 말해, 플레이어의 차례가 오면, 플레이어는 게임 트리에서 자신이 현재 어느 노드에 있는지 불확실할 수 있으며, 정보 집합은 플레이어가 고려해야 하는 모든 가능성을 나타낸다. 정보 집합은 특히 불완전 정보가 있는 게임에서 중요한 기본적인 개념이다.
섬네일|그림 1: 각 의사 결정 정점에서 다른 가능한 움직임(플레이어 1의 경우 A, 플레이어 2의 경우 B)을 정보 집합으로 묘사한 게임 트리
완전 정보가 있는 게임(예: 체스 또는 바둑)에서는 각 플레이어가 이전의 모든 움직임을 관찰하고 정확한 게임 상태를 알기 때문에 모든 정보 집합에는 정확히 하나의 의사 결정 노드가 포함된다. 그러나 포커 또는 브리지와 같은 대부분의 카드 게임처럼 불완전 정보가 있는 게임에서는 정보 집합에 여러 노드가 포함될 수 있으며, 이는 게임의 실제 상태에 대한 플레이어의 불확실성을 반영한다. 이러한 불확실성은 플레이어가 최적 전략에 대해 추론하는 방식을 근본적으로 변화시킨다.

정보 집합의 개념은 존 폰 노이만이 포커 연구에서 영감을 받아 도입했으며, 이제 순차적 게임 분석과 부분게임 완전 균형 및 완전 베이즈 균형과 같은 해 개념 개발에 필수적이다.

 전개형 게임에서 
정보 집합은 주로 전개형 게임 표현에서 사용되며 일반적으로 게임 트리에 묘사된다. 게임 트리는 게임 시작부터 다양한 종료까지의 모든 가능한 경로를 보여주며, 가지는 각 의사 결정 지점에서 플레이어가 이용할 수 있는 선택을 나타낸다.

불완전 정보가 있는 게임의 경우, 플레이어가 게임에서 자신의 정확한 위치를 결정할 수 없는 상황을 표현하는 데 어려움이 있다. 예를 들어, 카드 게임에서 플레이어는 자신의 카드는 알지만 상대방의 카드는 모르므로 실제 게임 상태에 대한 불확실성이 발생한다. 이 불확실성은 정보 집합을 사용하여 모델링된다.

정보 집합은 일반적으로 점선으로 구별할 수 없는 노드를 연결하거나, 여러 노드를 둘러싸는 타원 또는 플레이어가 여러 위치 중 어느 위치에 있는지 알 수 없음을 나타내는 유사한 표기법을 사용하여 게임 트리에 표현된다. 이 시각적 표현은 불확실성이 최적 플레이에 어떤 영향을 미치는지 분석하는 데 도움이 된다.

 형식적 정의 
전개형 게임의 정보 집합은 다음 속성을 만족해야 한다.

 정보 집합의 모든 노드는 동일한 플레이어에 속한다.
 플레이어는 사용 가능한 정보에 따라 동일한 정보 집합 내의 어떤 노드도 구별할 수 없다.
 동일한 정보 집합의 모든 노드는 동일한 사용 가능한 행동을 가져야 한다.
 정보 집합의 어떤 노드도 동일한 집합 내의 다른 노드의 선조가 될 수 없다 (이것은 게임 시간표에서 논리적 불가능성을 초래한다).

 전략적 함의 
정보 집합의 구조는 전략적 추론에 깊이 영향을 미친다. 플레이어가 여러 노드를 가진 정보 집합에 직면할 때, 해당 정보 집합이 나타내는 모든 가능한 게임 상태에 걸쳐 최적인 전략을 공식화해야 한다.

이는 여러 중요한 게임 이론적 개념으로 이어진다.

 혼합 전략은 불확실성에 직면할 때 종종 필요하게 된다. 순수 전략은 예측할 수 있는 상대방에 의해 악용될 수 있기 때문이다.
 베이즈 게임은 플레이어가 관찰된 행동을 기반으로 정보 집합에서 자신이 어느 노드에 있는지에 대한 믿음을 업데이트할 때 발생한다.
 신호 게임과 정보 공개는 플레이어가 정보를 공개하거나 숨기기 위해 특정 행동을 취할 수 있으므로 전략적 고려 사항이 된다.

 동적 게임과 역진 귀납 
여러 정보 집합이 있는 게임에서 전략적 상호 작용은 정적인 것이 아니라 동적이 된다. 플레이어는 현재 결정뿐만 아니라 발생할 수 있는 미래 정보 집합에 대해서도 추론해야 한다.

이러한 게임의 표준 해법은 역진 귀납으로, 플레이어는 게임의 끝에서 시작으로 추론한다. 예를 들어, 플레이어 A가 먼저 선택할 때, 플레이어 B는 A의 선택과 그 시점의 자신의 정보 집합을 기반으로 자신에게 최선의 결정을 내린다. 플레이어 A는 이러한 반응을 예측하여 자신의 보상을 최대화하기 위해 초기 선택을 한다.

이 순차적 추론 과정은 불완전 정보가 있는 게임에서 복잡해지며, 플레이어가 실제로 정보 집합의 어느 노드에 있는지에 대한 믿음을 고려하는 순차 균형과 같은 보다 정교한 해법 개념이 필요하다.
예시
320 px|right|성 대결 1
320 px|right|성 대결 2

오른쪽에는 성 대결 (게임 이론) 게임의 두 가지 버전이 전개형 게임으로 표시되어 있다. 아래에는 이 두 게임의 일반형 게임도 표시되어 있다.

첫 번째 게임은 단순히 순차적이다. 플레이어 2가 선택할 때, 양쪽 당사자는 이미 플레이어 1이 O(페라) 또는 F(축구)를 선택했는지 알고 있다.

두 번째 게임도 순차적이지만, 점선은 플레이어 2의 정보 집합을 보여준다. 이것은 플레이어 2가 움직일 때 플레이어 1이 무엇을 했는지 모른다는 것을 보여주는 일반적인 방법이다.

이러한 차이는 두 게임에 대해 다른 예측으로 이어진다. 첫 번째 게임에서는 플레이어 1이 우위를 점한다. 플레이어 1은 O(페라)를 안전하게 선택할 수 있다는 것을 알고 있다. 왜냐하면 플레이어 2가 플레이어 1이 오페라를 선택했다는 것을 알게 되면, 플레이어 2는 f(축구)를 선택하여 0을 얻는 것보다 o(페라)에 동참하여 2를 얻는 것을 선호할 것이기 때문이다. 공식적으로는 부분게임 완전 균형을 적용하여 게임을 해결하는 것이다.

두 번째 게임에서는 플레이어 2가 플레이어 1이 무엇을 했는지 관찰할 수 없으므로, 동시적 게임과 마찬가지일 수 있다. 따라서 부분게임 완전 균형은 내시 균형이 얻을 수 없는 것을 제공하지 않으며, 다음과 같은 3가지 표준 가능한 균형이 있다.
 둘 다 오페라를 선택한다.
 둘 다 축구를 선택한다.
 또는 둘 다 혼합 전략을 사용한다. 플레이어 1은 3/5의 확률로 O(페라)를 선택하고 2/5의 확률로 축구를 선택하며, 플레이어 2는 3/5의 확률로 f(축구)를 선택하고 2/5의 확률로 오페라를 선택한다.

플레이어 2가 플레이어 1의 움직임을 아는 일반형 width="90px"  Oo, Fo Oo, Ff Of, Fo Of, FfOF

플레이어 2가 플레이어 1의 움직임을 모르는 일반형 width="90px"  o fOF

 같이 보기 
 자기확인 균형

 각주 

 더 읽어보기 


분류:게임 이론