최대최소 정리 - 3. 사이온의 최대최소 정리(Sion's Minimax Theorem)

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

사이온의 최대최소 정리(Sion's Minimax Theorem)

정의 3.1. 반연속 함수(semi-continuous function)

$X$가 선형위상공간(linear topological space)이라 하자. 함수 $f: X \to \R$에 대하여

1. 임의의 $r \in \R$에 대하여 $\set{x \in X}{f(x)<r}$이 열린집합이면 $f$가 $X$에서 상반연속(lower semi-continuous)이라 한다.
2. 임의의 $r \in \R$에 대하여 $\set{x \in X}{f(x)>r}$이 열린집합이면 $f$가 $X$에서 하반연속(lower semi-continuous)이라 한다.

주어진 함수 $f : X \to \R$이 상반연속이면서 동시에 하반연속이면, $f$는 연속함수이다. 또한 $f : X \to \R$가 연속함수이고 $E \subseteq X$가 긴밀집합이면, 극값정리(Extreme Value Theorem)에 의해 $f$는 $E$에서 최댓값과 최솟값을 가짐은 잘 알려져 있다. 만약 $f$가 상반연속이면 $f$는 $E$에서 언제나 최댓값을 가지고, 반대로 $f$가 하반연속이면 $f$는 $E$에서 언제나 최솟값을 가진다.

보조정리 3.2.

$\mathcal{F}$와 $\mathcal{G}$가 각각 상반연속함수 $f : X \to \R$들의 집합, 하반연속함수 $g: X \to \R$들의 집합이라 하자. 그러면

\[ F(x) := \inf_{f \in \mathcal{X}} f(x), \quad G(x) := \sup_{g \in \mathcal{G}} g(x) \]

에 대하여, $F$는 상반연속이고 $G$는 하반연속이다.

정의 3.3. 준볼록함수(quasi-convex function)

$X$가 선형위상공간이라 하자. 함수 $f: X \to \R$에 대하여

1. 임의의 $r \in \R$에 대하여 $\set{x \in X}{f(x) < r}$이 볼록집합이면 $f$를 준볼록함수(quasi-convex function)이라 한다.
2. 임의의 $r \in \R$에 대하여 $\set{x \in X}{f(x) > r}$이 볼록집합이면 $f$를 준오목함수(quasi-concave function)이라 한다.

이제 폰 노이만의 최대최소 정리를 일반화 한 사이온의 최대최소 정리는 다음과 같다.

정리 3.4. 사이온의 최대최소 정리(Sion's Minimax Theorem)

선형위상공간 $X,\,Y$에 대하여, 집합 $C \subseteq X$와 $D \subseteq Y$가 공집합이 아닌 긴밀 볼록집합들이라 하자. 함수 $f : C \times D \to \R$이 다음의 조건을 만족한다고 하자.

1. 고정된 $y \in D$에 대하여, $x \mapsto f(x,\,y)$는 하반연속이고 준볼록함수이다.
2. 고정된 $x \in C$에 대하여, $y \mapsto f(x,\,y)$는 상반연속이고 준오목함수이다.

그러면 다음의 등식이 성립한다.

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

증명. 먼저 임의의 $x \in C$에 대하여 $y \mapsto f(x,\,y)$가 상반연속이므로, $\max_{y \in D} f(x,\,y)$가 잘 정의된다. 또한 보조정리에 의해 $x \mapsto \max_{y \in D} f(x,\,y)$는 하반연속이므로, $\min_{x \in C} \max_{y \in D} f(x,\,y)$ 또한 잘 정의된다. 마찬가지 방법으로 $\max_{y \in D} \min_{x \in C} f(x,\,y)$ 또한 잘 정의됨을 알 수 있다. 또한 이전 글에서 살펴 보았듯이

\[ \min_{x \in C} \max_{y \in D} f(x,\,y) \geq \max_{y \in D} \min_{x \in C} f(x,\,y) \]

임은 자명하다. 이제 등식을 증명하기 위하여 $r \in \R$이 존재하여,

\[ \min_{x \in C} \max_{y \in D} f(x,\,y) > r >  \max_{y \in D} \min_{x \in C} f(x,\,y) \]

을 만족한다고 가정해 보자. 이제 두 사상 $A,\,B : C \to 2^D$를

\begin{align*} A(x) &= \set{y \in D}{f(x,\,y) < r} \\ B(x) &= \set{y \in D}{f(x,\,y) > r} \end{align*}

와 같이 정의하자. 그러면 $y \mapsto f(x,\,y)$가 상반연속이므로, 모든 $x \in E$에 대하여 $A(x)$는 열린집합이다. 또한 $y \mapsto f(x,\,y)$는 준오목함수이므로 $B(x)$는 (공집합이 아닌) 볼록집합이다. 이제

\begin{align*} A^{-1}(y) &= \set{x \in C}{y \in A(x)} \\ &= \set{x \in C}{f(x,\,y) < r} \\ B^{-1}(y) &= \set{x \in C}{y \in B(x)} \\ &= \set{x \in C}{f(x,\,y) > r} \end{align*}

이므로 $x \mapsto f(x,\,y)$가 하반연속이고 준볼록함수임을 이용하면, 모든 $y \in D$에 대하여 $B^{-1}(y)$는 열린집합이고 $A^{-1}(x)$는 (공집합이 아닌) 볼록집합임을 알 수 있다. 따라서 Ky Fan의 동시발생 정리에 의해 $x_0 \in C$가 존재하여 $A(x_0) \cap B(x_0) \neq \emptyset$를 만족한다. 이제 $y_0 \in A(x_0) \cap B(x_0)$이라 하면, 

\[ r < f(x_0,\, y_0) < r \]

이 되어 모순이 발생한다. 따라서

\[ \min_{x \in C} \max_{y \in D} f(x,\,y) \leq \max_{y \in D} \min_{x \in C} f(x,\,y) \]

를 얻는다.