최대최소 정리 - 1. 폰 노이만의 최대최소 정리(Von Neumann's Minimax Theorem)

      Comments Off on 최대최소 정리 - 1. 폰 노이만의 최대최소 정리(Von Neumann's Minimax Theorem)

이번 글의 목적은, 게임 이론에서 폰 노이만(John Von Neumann, 1903-1957)의 최대최소 정리(Minimax Theorem)의 조건을 좀 더 일반화 한 사이온(Maurice Sion)의 최대최소 정리에 대해 알아보고 이를 KKM 사상(Knaster-Duratowski-Mazurkiewicz map)과 Ky Fan의 동시발생 정리(Ky Fan's Conincidence Theorem)을 이용하여 증명하는 것이다.

 

폰 노이만의 최대최소 정리(Von Neumann's Minimax Theorem)

게임 이론에서 폰 노이만은 유한 2인 영합 게임(finite two-person zero-sum game)에서는 언제나 최적의 혼합전략(mixed strategy)이 존재한다 사실을 그의 최대최소 정리를 통해 증명하였다. 먼저 경기자 $I$와 $II$의 혼합전략 공간을 정의하자.

\begin{align*} \Delta_m &:= \set{x \in \R^m_+}{\sum_{i=1}^{m} x_i = 1}, \\ \Delta_n & := \set{y \in \R^n_+}{\sum_{i=1}^{n} y_j = 1}. \end{align*}

각 경기자 $I$와 $II$는 동시에 각각 혼합전략 $x \in \Delta_m$과 $y \in \Delta_n$을 이용하며, 각 경기자의 전략의 결과에 따라 보수가 결정되는데, 각 경기자의 보수는 보수행렬(payoff matrix) $M \in \R^{m \times n}$을 통해 다음과 같이 나타낼 수 있다.

\[ f(x,\,y) := \sum_{i,\,j} x_i M_{ij} y_j = x^{\T}My. \]

그러면 경기자 $I$은 $f(x,\,y)$ 만큼의 보수를 지불하고, 반대로 경기자 $II$는 $f(x,\,y)$ 만큼의 보수를 받게 된다. (물론 $f(x,\,y)$가 음수일 수도 있다. 이때는 경기자 $I$이 $-f(x,\,y)$ 만큼의 보수를 받고, 경기자 $II$는 $-f(x,\,y)$ 만큼의 보수를 지불한다.)

 

이제 각 경기자들이 상대방의 전략을 모른다는 가정하에서, 경기자 $I$은 경기자 $II$가 어떤 전략을 사용하든지 상관 없이 $p(x,\,y)$를 최소화 하고 싶어한다. 즉, 경기자 $I$의 최적 전략 $x_0 \in \Delta_m$은

\[ f(x,\, y) \geq f(x_0,\,y) \quad \forall\; x \in \Delta_m,\, y \in \Delta_n \]

를 만족해야 한다. 마찬가지로 경기자 $II$의 최적 전략 $y_0 \in \Delta_n$은

\[ f(x,\, y_0) \geq f(x,\,y) \quad \forall\; x \in \Delta_m,\, y \in \Delta_n \]

을 만족해야 한다.

 

정의 1.1. 내쉬 균형(Nash equilibrium)

혼합전략 $(x_0,\, y_0) \in \Delta_m \times \Delta_n$이 다음을 만족하면,

\[ f(x,\,y_0) \geq f(x_0,\,y_0) \geq f(x_0,\, y) \quad \forall\; x \in \Delta_m,\, y \in \Delta_n \tag*{$(\ast)$} \]

이를 내쉬 균형(Nash equilibrium)을 이룬다고 한다.

 

따라서 두 경기자가 내쉬 균형을 이루는 혼합전략 $(x_0,\, y_0) \in \Delta_m \times \Delta_n$이용하면, 두 경기자 모두가 만족하는 게임의 결과가 나오게 된다. 유한 2인 영합 게임에서 이러한 내쉬 균형이 언제나 존재한다는 사실은 존 내쉬(John Forbes Nash Jr.)가 증명하였다.

 

이제 위 부등식 $(\ast)$는 다음과 같이 나타낼 수 있다.

\[ \min_{x \in \Delta_m} f(x,\,y_0) \geq f(x_0,\,y_0) \geq \max_{y \in \Delta_n} f(x_0,\, y) \]

따라서

\[ \min_{x \in \Delta_m} \max_{y \in \Delta_n} f(x,\,y) \geq f(x_0,\,y_0) \geq \max_{y \in \Delta_n} \min_{x \in \Delta_m} f(x,\, y) \]

를 얻는다. 여기서 더 나아가 폰 노이만은 다음과 같은 사실을 증명하였다.

 

정리 2.2. 폰 노이만의 최대최소 정리(Von Neumann's Minimax Theorem)

유한 2인 영합 게임(finite two-person zero-sum game)에서, $f(x,\,y)$의 최소최대해(minimax solution)과 최대최소해(maximin solution)의 값은 서로 같고 나아가 이 값은 내쉬 균형을 이룬다. 즉, 다음이 성립한다.

\[ \min_{x \in \Delta_m} \max_{y \in \Delta_n} f(x,\,y) = \max_{y \in \Delta_n} \min_{x \in \Delta_m} f(x,\,y). \]

 

사실 유한 2인 영합 게임(finite two-person zero-sum game)에서는 내쉬 균형의 존재성과 폰 노이만의 최대최소 정리가 서로 동치임이 알려져 있다.