환웅 데이터
[STAT155] Two-Person Zero-Sum Games 정리 본문
2인 제로섬 게임(two-person zero-sum)이란, 한 플레이어의 이익이 다른 플레이어의 손실로 이어지게끔 되어있습니다.
주식이랑 비슷하죠? 누군가 돈을 벌었다는건, 누군가 잃었다는 것과 마찬가지인 것 처럼!
두 플레이어가 서로 반대되는 목표를 가지고 있으며, 한 플레이어의 승리가 곧 다른 플레이어의 패배를 의미하는 게임입니다. 따라서, 게임에서의 총 이익(sum)은 항상 0이 됩니다. zero-sum이라는 이름으로부터 직관적으로 이해할 수 있죠?
V, 게임의 가치(value of the game): 각 플레이어가 해당 게임에서 보장할 수 있는 최소 이익 또는 최대 손실을 의미합니다.
이는 두 플레이어가 최적의 전략을 사용한다면 항상 동일한 값으로 나타납니다.
2인 제로섬 게임의 예시인 손 고르기(Pick-a-Hand) Chapter 2.1
Hider와 Chooser라는 두 플레이어가 존재합니다. Hider는 주머니에 들어있는 2개의 금화를 어느 손(오른손, 왼손)에 숨길지 결정하고, 몇개의 금화를 손에 쥘지 결정합니다. Chooser는 금화가 숨겨진 손을 선택하고자 하는 게임입니다.
Player1: Chooser, Player2: Hider
Strategy L1: Player2는 1개의 금화를 꺼내서 그의 왼손에 쥐기로 결정합니다.
Strategy R2: Player2는 2개의 금화를 모두 꺼내서 그의 오른손에 쥐기로 결정합니다.
물론, 이외에도 Hider는 더 많은 종류의 전략을 취할 수 있습니다. (1개의 금화를 꺼내서 오른손에 숨긴다는지 등등)
해당 예시에선, Player2가 2가지 전략만을 고려중이라고 가정하겠습니다.
Chooser는 이때 왼손이나 오른손을 고름으로써 최악의 경우엔 0개, 혹은 1개나 2개의 금화를 얻을 수 있습니다.
이걸 행렬로 표현해볼 수 있는데요.
| Hider | |||
| Chooser | L1 | R2 | |
| L | 1 | 0 | |
| R | 0 | 2 | |
Player2가 L1 전략을 고를 확률이 y1, R2를 고를 확률은 y2=1-y1 입니다.
이제 기대 손실 계산을 해보겠습니다. 기댓값(expected value)이니까, 계산법은 (확률) X (금화 개수)이겠죠.
Player2의 기대 손실은:
Player1이 왼쪽 손 L을 골랐을 때 1 X y1 = y1, Player1이 오른쪽 손인 R을 골랐을 때 2 X (1-y1)이 됩니다.
결론적으로, Player2의 최악의 기대 손실값은 max(y1, 2(1-y1))으로 나타낼 수 있습니다. 이를 이용하면 Player2가 두 전략중 어느 전략을 고르더라도, 최소환의 손실을 내고자 할 수 있습니다. Player2의 기대 손실값을 최소화하려면 y1 = 2/3라는 값을 넣으면 됩니다. 두 값 와 가 모두 작아지는 방향으로 전략을 설정하는 것이 중요합니다. max()는 두값중 더 큰 값을 고르는 수학 기호이기 때문이죠.
그래프로 나타내보았을 때, y축은 Chooser의 expected gain값을 나타냅니다. Chooser는 왼쪽 손을 고르는 전략인 x1의 확률이 0이라면, 오른손을 골랐단 뜻이겠죠? 빨간 줄을 보면 Hider가 R2 전략을 취했을 때를 의미하니, x1의 확률이 0일 경우 Chooser는 2개의 금화를 얻게 됩니다. Hider가 L1전략을 취했고, Chooser역시 x1을 고를 확률을 최대치로 놀 경우, 1개의 금화를 얻게 되어 expected gain의 값은 1이 되는거죠. 이를 그래프로 나타내보니까, x1은 2/3라는 값을 선택함으로써 어떤 경우에도 최소 2/3의 기대 이득을 보장 받을 수 있겠네요. Hider의 입장에서도 마찬가집니다. 같은 그래프 모양을 볼 수 있는데, 이는 payoff matrix(게임 이론에서 두 명 이상의 플레이어간의 전략 선택과 그 결과를 정량적으로 표현하는 도구) 가 대칭적이기 때문입니다.
Chapter 2.2 Definition 부분
2인 제로섬 게인은 m x n 보상 행렬로 표현됩니다. A = (aij)
Player1이 취할 수 있는 행동들은 row, Player2가 취할 수 있는 행동은 column으로 indexing됩니다.
Player1은 행동 i를 선택하고, Player2는 행동 j를 선택했다고하면, aij라고 표현할 수 있습니다.
<노트 필기 참고>
Player1 expected gain: Player1이 행동 i를 선택했을 때, Player1이 가질 수 있는 최악의 기대 이익값은 minj aij 입니다.
따라서 Player1이 보장할 수 있는 최대 이익은:
Player2 expected loss: Player2가 행동 j를 선택했을 때, Player2가 가질 수 있는 최악의 기대 손실값은 maxi aij 입니다.
따라서 Player2가 보장할 수 있는 최소 손실은:
불평등 관계:
부등호를 기준으로 왼쪽은 Player1의 이익, 오른쪽은 Player2의 손실을 보장하고 있습니다.
혼합 전략 (mixed strategy): 각 플레이어들이 취하는 행동이 특정 확률로 선택되는 전략을 의미합니다.
Each action is selected wtih some probability.
Player1의 혼합 전략:
여기서 xi는 행동 i를 선택할 확률을 나타냅니다.
전치행렬로 표현되어있는걸 보니, 세로로 쓰길 표현하는 것 같습니다.
플레이어의 혼합 전략 집합 (set of mixed strategy):
순수 전략 (Pure strategy): 혼합 전략중, 특정 행동이 확률 1로 선택되는 전략을 pure strategy라고 정의합니다. 다시 말해, 플레이어가 어떤 행동을 선택할지를 100% 확실하게 결정하는 것입니다.
A mixted strategy in which a particular action is played with probability 1.
표준 기저 벡터 (standard basis vector): Pure strategy는 표준 기저 벡터로 표현될 수 있습니다 (원소중 하나만 값이 1이고 다른 값은 0). ei는 i번째 행동을 나타나내는 basis vector이며, 각 요소는 해당 행동의 선택 확률을 나타냅니다. Pure strategy ei는 행동 i와 매칭된다고 볼 수 있죠.
기대 이익 계산법 (Expected gain of players)
Player1이 전략 x를 사용하고, Player2가 전략 y를 사용할 때:
Player1의 기대 이익 = Player2의 기대 손실
Player1의 행동 확률인 xi와 player2의 행동 확률인 yj에 대한 보상 aij의 곱을 모두 더한 값입니다.
x: player1의 mixted strategy를 나타내는 벡터.
y: player2의 mixted strategy를 나타내는 벡터.
A: 보상 행렬인 payoff matrix. mxn 크기의 행렬. aij란 player1이 행동i, player2가 행동j를 선택했을 때 player1이 받는 보상.
보장 기대 이익 (guarantee expected gain)
Player1이 전략x를 사용할 경우, player1은 스스로 보장된 기대 수익을 계산할 수 있습니다. 즉, Player1이 자신의 행동에 따른 최소 기대 보상을 구하는 과정인거죠. Player2가 최악의 경우에 최대 손실을 초래하는 행동을 취한다면, player1에 입장에서 보장할 수 있는 최소 기대 보상을 나타냅니다. 이게 게임 이론의 안전 전략(safety strategy)과도 연결됩니다.
(필기 참고) Player1은 잠재적인 모든 전략 y에 대해서 기대 이익의 최솟값을 제공합니다.
안전 전략 (safety strategy): Chapter 2.2.1
보수적인 플레이어의 경우, 최악의 상황에 대비하기 위해, 발생 가능한 최악의 결과에서 자신의 기대 보상을 최대화하려고 할겁니다. 따라서, 자신이 선택할 수 있는 전략 x를 고를 때, 최대 기대 보상을 받을 수 있도록 할 것입니다. 최악의 경우에서 자신의 보상을 최대화하려고 한다는 뜻입니다.
Player1의 입장에서, Player2의 전략에는 의존하지 않고, 자신이 선택할 수 있는 최대 기대 보상을 위한 x를 결정할겁니다.
즉, x*를 사용하면 Player1이 보장할 수 있는 최악의 기대 보상이 최대화된다는 뜻
x*에서 도출된 이 함수의 값은 player1의 안전 값(safety value)으로, Player2가 어떤 전략을 취하든 최소한 이만큼의 보상은 늘 보장 받을 수 있음.
John von Neumann's minimax theorem (폰 노이만의 최소 최대 정리) Chapter 2.3
각 플레이어는 최적의 전략을 선택할 수 있으며, 상대방의 전략을 알고 있어도 자신의 손실을 최소화하거나 이익을 극대화할 수 있는 방법을 찾아야 합니다.
2인 제로섬 게임에서 mxn 보상행렬 A가 있을 때, 게임의 가치를 나타내는 숫자 V가 존재합니다.
Player1이 사용하는 mixed strategy x* 는 Player2가 어떤 전략을 취하더라도 최소 V의 기대 수익을 보장받는다는 것.
Player2가 사용하는 mixed strategy y*는 자신의 최대 손실이 V를 초과하지 않는다는 것.
환 웅, Minor in Data Science & B.A. in Statistics at University of California, Berkeley
Works cited:
https://gazelle-and-cs.tistory.com/54