10-05 Matrix Games

이번 장에서는 게임이론에서의 primal LP, dual LP의 예시인 mixed strategies for matrix games에 대해서 살펴본다. 설정은 두명의 player, J와 R, 그리고 payout matrix $P$ 가 있다고 하자.

Game Setup

payout matrix는 만약 J가 전략 $i$ 를 선택하고(row), R이 전략 $j$ 를 선택했을때(column), J가 R에게 주어야 하는 보상의 크기이다( $P_{i j}$ ). 하지만 이 값이 양수라면, J가 R에게 해당 matrix의 크기만큼의 보상을 주고, 음수라면 R이 J에게 해당 matrix의 크기만큼의 보상을 주게 된다.

이러한 setting을 zero-sum setting이라고도 하는데, R이 받게 될 혹은 지불해야할 보상을 $r_{R}$ , J의 보상을 $r_{J}$ 라 할 때, 매 게임에서 보상의 결과는 $r_{R} = - r_{J}$ 이고, 두 보상의 총합은 항상 0이 된다.

또한 두 명의 player가 모두 mixed strategies를 사용한다고 가정한다, mixed strategies는 각자의 선택이 특정한 확률분포를 따른다는(혹은 특정한 확률분포에서 sampling 된다는) 가정이다.

$\begin{array}{r} x : P (J chooses i) = x_{i}, i = 1, . . . m \\ y : P (R chooses j) = y_{j}, j = 1, . . . n . \end{array}$

서로가 서로의 mixed strategy, 즉 확률분포를 알고 있다면, 각자는 각자가 얻을 것으로 기대하는 payout, 즉 expected payout을 계산할 수 있다.

$\begin{array}{r} \sum_{i = 1}^{m} \sum_{j = 1}^{n} x_{i} y_{j} P_{i j} = x^{T} P y . \end{array}$

payout matrix의 부호가 J가 R에게 주는 크기로 정의되어 있음을 생각할 때, J는 R에게 최대한 주지 않으려 하기 때문에, 이 expected payout을 최소화(minimize)하려 할 것이고, R은 J에게서 최대한 받고 싶어하기 떄문에, 이 expected payout을 최대화(maximize)하려 할 것이다.

이제 두 player의 입장에서 각자가 상대의 mixed strategy를 고려하여, 이 expected payout을 최대화(R의 입장) 혹은 최소화(J의 입장)하려는 관점을 살펴보고, 서로가 서로를 optimal하게 행동하는 전제하에, 두 입장에서 유도되는 optimal strategy를 구하고, 결과적으론 Von Neumman’s minimax theorem에 의해 두 결과가 같다는 것을 확인할 것이다.

Minimizing Expected Payout : J’s Perspective

먼저 R이 J의 strategy $x$ 를 알고 있다고 가정하자. R은 expected payout $x^{T} P y$ 를 maximize하고자 할 것이다.

$\begin{array}{r} max {x^{T} P y : y \geq 0, 1^{T} y = 1} = max_{i = 1, . . . n} (P^{T} x)_{i} . \end{array}$

이때 R은 식의 내용처럼 $(P^{T} x)_{i}$ 중 가장 큰 값을 갖는 i(row index)를 찾게되고, 이 i에 대응되는 $y_{i}$ 를 1로 가지고 나머지의 row index에 대해선 0을 가지는 strategy가 R에게 있어서 expected payout을 maximize하는 strategy일 것이다.

R이 위처럼 최적으로 행동할 것을 알고 있을 때, J의 최적의 strategy는 밑의 식을 만족하는 distribution $x$ 일 것이다.

$\begin{aligned} min_{x} & max_{i = 1, . . . n} (P^{T} x)_{i} \\ subject to & x \geq 0, 1^{T} x = 1. \end{aligned}$

Convex function의 maximization 또한 convex function이 된다. 이를 첫 번째 관점의 문제 정의라고 칭할 것이다. 또한 이 최적화 문제의 해를 optimal expected payout $f_{1}^{*}$ 이라고 정하자. 또 하나 유념할 점은 게임참가자, 즉 player들이 모두 최적으로 행동한다는 가정이 기본적인 형태의 게임이론 formulation에서 가정이 된다.

Maximizing Expected Payout : R’s Perspective

두 번째 관점으로 J가 R의 strategy $y$ 를 알고 있다고 가정하자. J는 expected payout을 minimize하고자 할 것이다.

$\begin{array}{r} min {x^{T} P y : x \geq 0, 1^{T} x = 1} = min_{j = 1, . . . n} (P y)_{j} . \end{array}$

같은 논리로, J가 위처럼 최적으로 행동할 것을 알고 있을 때 R의 최적의 strategy는 밑의 식을 만족하는 distribution $y$ 이다.

$\begin{aligned} max_{y} & min_{j = 1, . . . m} (P y)_{j} \\ subject to & y \geq 0, 1^{T} y = 1. \end{aligned}$

위와 마찬가지로 이를 두 번째 관점의 문제 정의라고 칭하고, 이 최적화 문제의 해를 $f_{2}^{*}$ 라고 하자. player R이 이 expected payout을 maximize하고자 하기 때문에, 첫 번째, 즉, R이 J의 strategy를 미리 알고 있다는 가정 하에 결정되는 expected payout $f_{1}^{*}$ 이 두 번째 가정보다 더 크거나 같은 값을 가질 것이라 쉽게 예상할 수 있다. ( $f_{1}^{*} \geq f_{2}^{*}$ )

Von Neumann’s minimax theorem

하지만, Von Neumann’s minimax theorem에 따르면 $f_{1}^{*} = f_{2}^{*}$ 가 된다. 실제 minimax theorem은 다음과 같다.

$\begin{aligned} Let X \subset R^{N} and Y \subset R^{m} be compact convex sets. \\ If f : X \times Y \to R is a continuous function that is convex-concave, i.e. \\ f (\cdot, y) : X \to R is convex for fixed y, and \\ f (x, \cdot) : Y \to R is concave for fixed x . \\ Then we have that \\ min_{x \in X} max_{y \in Y} f (x, y) = max_{y \in Y} min_{x \in X} f (x, y) . \end{aligned}$

해당 내용의 증명은 생략한다.

Proof of each perspective having Primal and Dual relationship

이제 위 두 가지 관점의 경우에 대한 expected payout이 LP 문제로써 서로 primal, dual 관계이고, Von Neumman’s minimax theorem에 의하여 두 결과가 같다는 점을 이용하여, strong duality를 만족함을 보이고자 한다.

먼저 첫 번째 관점의 문제를 다음과 같이 reformulate 할 수 있다.

$\begin{aligned} min_{x} max_{i = 1, . . . m} & (P^{T} x)_{i} \\ subject to & x \geq 0, 1^{T} x = 1 \end{aligned}$ $\begin{aligned} \Leftrightarrow \\ min_{x, t} & t \\ subject to & x \geq 0, 1^{T} x = 1, P^{T} x ⪯ t . \end{aligned}$

$t$ 를 $P^{T} x$ 의 항들 중 가장 큰 값과 같게 만들어주는 문제로 reformulate 하였다.

이제 여기에 앞서 배운 duality의 두 번째 방법인 Lagrangian을 구하고, Lagrange dual function $g$ 를 구하면,

$\begin{aligned} L (x, t, u, v, y) & = t - u^{T} x + v (1 - 1^{T} x) + y^{T} (P^{T} x - t 1) \\ g (u, v, y) & = min_{x, t} L (x, t, u, v, y) \\ = {\begin{cases} v & if 1 - 1^{T} y = 0, P y - u - v 1 = 0 \\ - \infty & otherwise. \end{cases} \end{aligned}$

$u$ 는 slack variable이므로, 이를 제거하고 식을 정리하면 다음과 같다.

$\begin{aligned} max_{y, v} & v \\ subject to & y \geq 0, 1^{T} y = 1 \\ P y \geq v . \end{aligned}$

이는 두 번째 관점의 문제의 primal LP이다. 따라서 두 관점은 dual 관계에 있고 두 문제의 optimal value는 같으므로, strong duality가 성립한다.

일반적으로 LP문제에서는, 향 후의 내용에서 다루지만, primal과 dual 중 하나만 feasible하다면 strong duality가 성립한다.

모두를 위한 컨벡스 최적화