영합게임과 미니맥스

한 사람의 이득이 정확히 다른 사람의 손실인 게임을 본다. 보수표의 숫자를 직접 바꿔본다.

나는 최악의 경우를 최대한 좋게 만들려 한다. 상대는 내 이득을 최대한 작게 만들려 한다. 두 계산이 일치하면 안장점이 생기고 순수전략 균형이 된다. 어긋나면 둘 다 전략을 섞어야 하고, 그때 게임의 값이 아래 식처럼 정해진다.

예를 들면, 🍬 사탕 한 개를 걸고 동전의 앞면과 뒷면을 맞힌다고 하자. 내가 맞히면 사탕은 내 것이 된다. 틀리면 🧑 친구가 가져간다. 내가 얻는 만큼 친구가 잃는 게임이다. 그래서 둘 다 속을 읽히지 않게 섞는다.

max⁡rmin⁡curc≤min⁡cmax⁡rurc\max_r \min_c u_{rc} \le \min_c \max_r u_{rc}
v=ad−bca−b−c+d,p∗=d−ca−b−c+dv = \frac{ad-bc}{a-b-c+d}, \quad p^* = \frac{d-c}{a-b-c+d}

예제

Matching Pennies를 영합게임으로 보고 maximin과 minimax를 구한 뒤, 안장점이 없음을 확인하고 혼합균형과 게임의 값을 계산하라.

max⁡rmin⁡curc=max⁡(−1,−1)=−1,min⁡cmax⁡rurc=min⁡(1,1)=1\max_r \min_c u_{rc} = \max(-1, -1) = -1, \qquad \min_c \max_r u_{rc} = \min(1, 1) = 1
Matching Pennies — maximin −1<1=-1 < 1 = minimax, 안장점 없음.
증명 보기

  1. 행 최소값은 둘 다 −1-1이므로 maximin =−1=-1, 열 최대값은 둘 다 11이므로 minimax =1= 1. −1<1-1 < 1이므로 안장점이 없다 — 어떤 셀도 "행 최소이면서 열 최대"가 아니다.

  2. 완전혼합 공식에 대입하면 p∗=d−ca−b−c+d=24=12p^* = \frac{d-c}{a-b-c+d} = \frac{2}{4} = \frac12, q∗=d−ba−b−c+d=12q^* = \frac{d-b}{a-b-c+d} = \frac12, 값 v=ad−bca−b−c+d=0v = \frac{ad-bc}{a-b-c+d} = 0이다. 폰 노이만의 미니맥스 정리대로, 혼합을 허용하면 maximin과 minimax가 00에서 일치한다.

아래 보수행렬의 영합게임에서 maximin·minimax를 구하고, 안장점이 없으면 혼합균형 (p∗,q∗)(p^*, q^*)와 게임의 값을 계산하라.

(4123)\begin{pmatrix}4 & 1 \\ 2 & 3\end{pmatrix}
p∗=d−ca−b−c+d,q∗=d−ba−b−c+d,v=ad−bca−b−c+dp^* = \frac{d-c}{a-b-c+d}, \quad q^* = \frac{d-b}{a-b-c+d}, \quad v = \frac{ad-bc}{a-b-c+d}
(4123)\begin{pmatrix}4 & 1 \\ 2 & 3\end{pmatrix} — 혼합균형 p∗=1/4p^* = 1/4, q∗=1/2q^* = 1/2, v=2.5v = 2.5.
증명 보기

  1. 행 최소값: min⁡(4,1)=1\min(4,1) = 1, min⁡(2,3)=2\min(2,3) = 2 → maximin =2= 2 (아래 행).

    열 최대값: max⁡(4,2)=4\max(4,2) = 4, max⁡(1,3)=3\max(1,3) = 3 → minimax =3= 3 (오른쪽 열).

    2≠32 \ne 3이므로 안장점이 없다.

  2. a−b−c+d=4a - b - c + d = 4, 따라서 p∗=3−24=14p^* = \frac{3-2}{4} = \frac14, q∗=3−14=12q^* = \frac{3-1}{4} = \frac12, v=12−24=2.5v = \frac{12-2}{4} = 2.5. 검증: q∗q^*에서 P1의 두 행 기대보수는 4⋅12+1⋅12=2.5=2⋅12+3⋅124 \cdot \frac12 + 1 \cdot \frac12 = 2.5 = 2 \cdot \frac12 + 3 \cdot \frac12로 일치한다.

8. 게임이론