페미위키:포크 프로젝트/리브레 위키/영합게임

정의

게임의 참여자들의 이득의 합이 항상 0이면 그 게임을 영합게임, 또는 제로섬 게임(zero-sum game)이라 한다.

2인 영합게임

영합게임에서 참여자의 수가 2명일 때, 참여자를 각각 $P_{1},P_{2}$라고 하자. 만약 $P_{1},P_{2}$가 택할 수 있는 전략의 수가 각각 m,n이면, 이 게임을 m×n직사각게임 또는 m×n게임이라 한다. $P_{1},P_{2}$가 택하는 전략을 각각 $i,j$라 하고, 이때 $P_{1}$의 이득을 $a_{ij}$라고 하면, 다음 표

	1	2	$\cdots$	n
1	$a_{11}$	$a_{12}$	$\cdots$	$a_{1n}$
2	$a_{21}$	$a_{22}$	$\cdots$	$a_{2n}$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
m	$a_{m1}$	$a_{m2}$	$\cdots$	$a_{mn}$

를 게임의 이득표(payoff table)이라고 한다. 그리고 행렬 $A=[a_{ij}]$를 게임의 이득행렬(payoff matrix)이라고 한다.

결정적 게임과 비결정적 게임

2인 영합게임에서 참여자들은 항상 최선의 전략을 사용하여 최대의 이득을 얻으려고 한다. 이때 각 참여자들은 상대방이 자신에게 가장 불리한 전략을 쓸 경우에 대비해 예상되는 손해를 줄이려고 행동한다고 가정한다. 그러면 $P_{1}$는 이득행렬의 행의 최솟값 중에서 최댓값을 얻는 전략을 선택할 것이고, 반대로 $P_{2}$는 이득행렬의 열의 최댓값 중에서 최솟값을 얻는 전략을 실행할 것이다. 따라서 미니맥스(minimax)와 맥시민(maximin)을 다음과 같이 정의할 수 있다: A의 i번째 행 $\mathbf {u} _{i}$의 최솟값을 $u_{i}$라 하고, j번째 열 $\mathbf {v} _{j}$의 최댓값을 $v_{j}$라고 하자. 그러면

$\operatorname {maximin} =\max\{u_{1},u_{2},\cdots ,u_{m}\}$

$\operatorname {minimax} =\min\{v_{1},v_{2},\cdots ,v_{n}\}$

이다.

결정적 게임

미니맥스와 맥시민이 같은 게임을 결정적 게임(strictly determined game)이라고 한다.

만약 참여자에게 전략 $a,b$가 주어졌을 때 상대방의 전략에 상관없이 전략 a를 선택했을 때 전략 b보다 더 많은 이익을 얻는다고 하자. 그러면 a를 우월한 전략(dominant strategy), b를 열등한 전략(dominated strategy)이라고 한다. m×n게임의 이득표에서 열등한 전략을 소거하는 것을 축약(contraction)이라고 한다. 만약 축약된 게임이 결정적 게임이라면, 원래 게임도 결정적 게임이다.

예를 들어, 어떤 2인 영합게임의 이득행렬이 다음과 같이 주어졌다고 가정하자.

${\begin{bmatrix}3&4&2\\1&2&-1\\2&5&-3\end{bmatrix}}$

그러면 $P_{2}$의 세 번째 전략은 첫 번째, 두 번째 전략보다 우월하다. 따라서 축약하면

${\begin{bmatrix}2\\-1\\-3\end{bmatrix}}$

이다. 따라서 이 게임은 $P_{1}$는 첫 번째 전략을 선택하고 $P_{2}$는 세 번째 전략을 선택하는 결정적 게임이다.

비결정적 게임

결정적 게임이 아닌 게임을 비결정적 게임(non-strictly determined game)이라고 한다. m×n게임에서 본래의 전략을 순수전략(pure strategy)이라 하고, 순수전략을 혼합하여 택하는 전략을 혼합전략(mixed strategy)이라고 하며, 혼합전략은 열벡터로 나타낼 수 있다. $P_{1}$이 전략 1,2,...,m을 확률 $x_{1},x_{2},\cdots ,x_{m}$으로 택하는 혼합전략을 행렬 $\mathbf {x}$, $P_{2}$가 전략 1,2,...,n을 확률 $y_{1},y_{2},\cdots ,y_{n}$으로 택하는 혼합전략을 행렬 $\mathbf {y}$라고 하자. 그러면

$\mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{m}\end{bmatrix}},\;\mathbf {y} ={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{bmatrix}}$

으로 나타낼 수 있으며, 이때 $P_{1}$이 얻을 것으로 기대되는 이득, 즉 기대이득(expected payoff)은 이중선형형식(bilinear form)

$E(\mathbf {x} ,\mathbf {y} )=\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}x_{i}y_{j}=\mathbf {x} ^{T}A\mathbf {y}$

으로 나타낼 수 있다.

$P_{1}$의 혼합전략 $\mathbf {x}$에 대해 $E_{1}(\mathbf {x} ),M$를 다음과 같이 정의하자.

$E_{1}(\mathbf {x} )=\min _{\mathbf {y} }E(\mathbf {x} ,\mathbf {y} )$

$M=\max _{\mathbf {x} }E_{1}(\mathbf {x} )=\max _{\mathbf {x} }\min _{\mathbf {y} }E(\mathbf {x} ,\mathbf {y} )$

그리고 $E_{1}({\bar {\mathbf {x} }})=M$이 되는 $\mathbf {x}$를 ${\bar {\mathbf {x} }}$라고 하자. 이때 ${\bar {\mathbf {x} }}$를 $P_{1}$의 맥시민 전략(maximin strategy)이라고 한다.

$P_{2}$의 혼합전략 $\mathbf {y}$에 대해 $E_{2}(\mathbf {y} ),m$를 다음과 같이 정의하자.

$E_{2}(\mathbf {y} )=\max _{\mathbf {x} }E(\mathbf {x} ,\mathbf {y} )$

$m=\min _{\mathbf {y} }E_{2}(\mathbf {y} )=\min _{\mathbf {y} }\max _{\mathbf {x} }E(\mathbf {x} ,\mathbf {y} )$

그리고 $E_{2}({\bar {\mathbf {y} }})=m$이 되는 $\mathbf {y}$를 ${\bar {\mathbf {y} }}$라고 하자. 이때 ${\bar {\mathbf {y} }}$를 $P_{2}$의 미니맥스 전략(minimax strategy)이라고 한다.

그러면 $M=m$이고, 다음 식이 성립한다.

$\max _{\mathbf {x} }\min _{\mathbf {y} }E(\mathbf {x} ,\mathbf {y} )=E({\bar {\mathbf {x} }},{\bar {\mathbf {y} }})=\min _{\mathbf {y} }\max _{\mathbf {x} }E(\mathbf {x} ,\mathbf {y} )$

$P_{1},P_{2}$의 i,j번째 순수전략 $\mathbf {x} _{i},\mathbf {y} _{j}$를 다음과 같이 정의할 수 있다.

$\mathbf {x} _{i}=[\delta _{ik}]_{m\times 1},\;\mathbf {y} _{j}=[\delta _{kj}]_{n\times 1}$

이때 $\delta _{ij}$는 크로네커 델타다. 그러면 다음 식이 성립한다.

$\max _{\mathbf {x} }\min _{\mathbf {y} }E(\mathbf {x} ,\mathbf {y} )=\max _{\mathbf {x} }\min\{E(\mathbf {x} ,\mathbf {y} _{1}),E(\mathbf {x} ,\mathbf {y} _{2}),\cdots ,E(\mathbf {x} ,\mathbf {y} _{n})\}$

$\min _{\mathbf {y} }\max _{\mathbf {x} }E(\mathbf {x} ,\mathbf {y} )=\min _{\mathbf {y} }\max\{E(\mathbf {x} _{1},\mathbf {y} ),E(\mathbf {x} _{2},\mathbf {y} ),\cdots ,E(\mathbf {x} _{n},\mathbf {y} )\}$

같이 보기

• 비영합게임