최대최소 정리 - 2. KKM 사상과 Ky Fan의 정리

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

KKM 사상과 Ky Fan의 정리

정의 2.1. 유한닫힌집합(finitely closed set)

집합 $A \subseteq X$에 대하여, $A$와 $X$의 임의의 유한차원 아핀 부분공간(affine subspace) $L$과의 교집합 $A \cap L$이 ($L$의 위상에서) 언제나 닫힌집합이면, $A$를 유한닫힌집합(finitely closed set)이라 한다.

예제. 만약 $X$가 유한차원이라면 닫힌집합(closed set)과 유한닫힌집합(finitely closed set)은 서로 동치이다. 하지만 $X$가 무한차원인 경우, 모든 닫힌집합은 유한닫힌집합이지만 그 역은 성립하지 않는다. 이를 살펴보기 위하여, $X = l_2$라 하자. 이제 집합 $A \subseteq X$를

\[ A := \{ (1,\,0,\,0,\,\ldots),\, (0,\,1,\,0,\,\ldots),\, (0,\,0,\,1,\,\ldots),\, \ldots \} \]

와 같이 정의하자. 그러면 $A$는 유한닫힌집합이지만 닫힌집합은 아님을 쉽게 보일 수 있다.

정의 2.2. 유한교차성(finite intersection property)

집합족 $\mathcal{A} = \set{A_i \subseteq X}{i \in I}$의 임의의 유한 부분집합족 $\{ A_{i_1},\, A_{i_2},\, \ldots,\, A_{i_N} \}$의 원소들의 교집합이 공집합이 아니면, 즉,

\[ \bigcap_{k=1}^{N} A_{i_k} \neq \emptyset \]

을 만족하면 $\mathcal{A}$가 유한교차성(finite intersection property)을 갖는다고 한다.

정의 2.3. KKM 사상(Knaster-Kuratowski-Mazurkiewicz map)

$X$가 선형위상공간이라 하자. $E \subseteq X$에 대하여, 사상 $G : E \to 2^X$가 $E$의 임의의 유한집합 $\{x_1,\, x_2,\, \ldots,\, x_N \}$에 대하여

\[ \operatorname{conv}\{x_1,\, x_2,\, \ldots,\, x_N \} \subseteq \bigcup_{i=1}^{N} G(x_i) \]

를 만족하면, $G$를 KKM 사상(Knaster-Kuratowski-Mazurkiewicz map)이라 한다.

정리 2.4. KKM 정리(Knaster-Kuratowski-Mazurkiewicz Theorem)

선형위상공간 $X$, $E \subseteq X$, 그리고 사상 $G : E \to 2^X$를 생각하자. 만약 $G$가 KKM 사상이면서 임의의 $x \in E$에 대하여 $G(x)$가 유한닫힌집합이면, 집합족 $\set{G(x)}{x \in E}$는 유한교차성을 갖는다.

증명. 모순을 이끌어 내기 위하여 $E$의 부분집합 $\{x_1,\, x_2,\, \ldots,\, x_N \}$이 존재하여

\[ \bigcap_{k=1}^{N} G(x_i) = \emptyset \tag*{$(\ast)$}\]

이라 가정하자. 이제 유한차원 아핀 부분공간 $L = \operatorname{span}\{x_1,\, x_2,\, \ldots,\, x_N \}$과 볼록집합 $C = \operatorname{conv}\{x_1,\, x_2,\, \ldots,\, x_N \} \subset L$을 각각 정의하자. 이제 $G(x_i)$는 유한닫힌집합이므로, $L \cap G(x_i)$는 $L$에서 닫힌집합이고, 따라서

\[ x \in L \cap G(x_i) \iff d(x,\, L \cap G(x_i)) = 0 \]

임을 알 수 있다. 이제$(\ast)$를 가정했으므로, 함수 $\lambda : C \to \R$

\[ c \mapsto \lambda(c) := \sum_{i=1}^{N} d(c,\, L \cap G(x_i)) \]

를 정의하면 임의의 $c \in C$에 대하여 $\lambda(c) \neq 0$임을 알 수 있다. (만약 $\lambda(c) = 0$이면, 모든 $x_i$에 대하여 $d(c,\, L \cap G(x_i))$이고 따라서 $c \in L \cap G(x_i)$를 얻는데, 이는 $(\ast)$에 모순이다.) 이제 $f : C \to C$를

\[ c \mapsto f(c) := \frac{1}{\lambda(c)} \sum_{i=1}^{N} d(c,\, L \cap G(x_i)) x_i \]

로 정의한다. 그러면 $f$는 연속함수이면서 $C$ 안으로의 함수임을 쉽게 알 수 있다. 또한 $C$는 긴밀 볼록집합(compact convex set)이므로, 브라우어 고정점 정리(Brouwer's fixed-point theorem)에 의해 $c_0 \in C$가 존재하여 $f(c_0) = c_0$를 만족한다. 이제 $I = \set{i}{d(c_0,\, L \cap G(x_i)) \neq 0}$으로 정의하자. 앞에서 살펴보았듯이 $I \neq \emptyset$임을 알 수 있다. 또한

\[ c_0 \notin \bigcup_{i \in I} G(x_i) \]

를 얻는다. 하지만 $G$가 KKM 사상이므로

\[ c_0 = f(c_0) \in \operatorname{conv}\set{x_i}{i \in I} \subseteq \bigcup_{i \in I} G(x_i) \]

이 되어 모순이 발생한다. 따라서 집합족 $\set{G(x)}{x \in E}$는 유한교차성을 갖는다.

따름정리 2.5. Ky Fan의 정리(Ky Fan's Theorem)

선형위상공간 $X$, $E \subseteq X$, 그리고 사상 $G : E \to 2^X$를 생각하자. 만약 $G$가 KKM 사상이면서 $x \in E$에 대하여 $G(x)$가 닫힌집합이고 그 중 적어도 하나가 긴밀 집합이면 다음이 성립한다.

\[ \bigcap_{x \in E} G(x) \neq \emptyset. \]

증명. $G(x_0)$가 긴밀 집합이라 하자. 가정에 의해 모든 $x \in E$에 대하여 $G(x)$가 닫힌집합이므로 자명하게 유한닫힌집합이다. 따라서 KKM 정리에 의해 집합족 $\set{G(x)}{x \in E}$는 유한교차성을 가짐을 알 수 있다. 이제 모순을 이끌어 내기 위하여

\[ \bigcap_{x \in E} G(x) = \emptyset \]

라 가정해 보자. 임의의 $x \in E$에 대하여, $G(x_0) \setminus G(x)$는 $G(x_0)$에서 열린집합이고,

\[ G(x_0) = G(x_0) \setminus \bigg( \bigcap_{x \in E} G(x) \bigg) = \bigcup_{x \in E} \Big[ G(x_0) \setminus G(x) \Big] \]

이므로 $G(x_0)$의 긴밀성에 의해 

\[ G(x_0) = \bigcup_{i=1}^{n} \Big[ G(x_0) \setminus G(x_i) \Big] = G(x_0) \setminus \bigg( \bigcap_{i=1}^{n} G(x_i) \bigg) \]

를 얻는다. 하지만 유한교차성에 의해 $\bigcap_{i=1}^{n} G(x_i) \neq \emptyset$이므로 모순이 생기고 따라서 증명이 완료된다.

정리 2.6. Ky Fan의 동시발생 정리(Ky Fan's Coincidence Theorem)

선형위상공간 $X,\,Y$에 대하여, 집합 $C \subseteq X$와 $D \subseteq Y$가 공집합이 아닌 긴밀 볼록집합들이라 하자. 두 사상 $A,\,B : C \to 2^D$가 아래 두 조건을 만족한다고 하자.

1. 임의의 $x \in C$에 대하여 $A(x)$는 열린집합이고 $B(x)$는 공집합이 아닌 볼록집합이다.
2. 임의의 $y \in D$에 대하여 $B^{-1}(y)$는 열린집합이고 $A^{-1}(y)$는 공집합이 아닌 볼록집합이다.

그러면 $x_0 \in C$가 존재하여 $A(x_0) \cap B(x_0) \neq \emptyset$를 만족한다. (단, $A^{-1}(y) := \set{x \in X}{y \in A(x)}$로 정의한다.)

증명. $E = C \times D$라 하자. 이제 함수 $G : E \to 2^{X \times Y}$를 다음과 같이 정의한다.

\[ (x,\,y) \mapsto G(x,\,y) := E \setminus \big[ B^{-1}(y) \times A(x) \big]. \]

그러면 모든 $(x,\,y)$에 대하여 $G(x,\,y)$는 $E$에서 닫힌집합이고 따라서 긴밀 집합이다. 이제 임의의 $(x_0,\,y_0) \in E$에 대하여 $(x,\,y) \in A^{-1}(y_0) \times B(x_0)$를 택하면, $(x_0,\,y_0) \in B^{-1}(x) \times A(y)$를 얻는다. 따라서

\[ E = \; \bigcup_{(x,\,y) \in E} \; \big[ B^{-1}(x) \times A(y) \big] \]

임을 알 수 있다. 그러므로 

\[ \bigcup_{(x,\,y) \in E} \; G(x,\,y) = E \setminus \; \bigcup_{(x,\,y) \in E} \; \big[ B^{-1}(x) \times A(y) \big] = \emptyset \]

가 되어, 따름정리(의 대우명제)에 의해 $G$는 KKM 사상이 될 수 없음을 알 수 있다. 그러므로 $z_1,\, \ldots,\, z_n \in E$가 존재하여 $z_i = (x_i,\, y_i)$이고 $\operatorname{conv}\{z_1,\, \ldots,\, z_n\}$는 $\bigcup_{i=1}^{n} G(z_i)$의 부분집합이 아니다. 즉,

\[ z_0 = (x_0,\, y_0) = \left( \sum_{i=1}^{n} \lambda_i x_i,\, \sum_{i=1}^{n} \lambda_i y_i \right) \in \operatorname{conv}\{z_1,\, \ldots,\, z_n\} \]

가 존재하여, $z_0 \notin \bigcup_{i=1}^{n} G(z_i)$를 만족한다. 한편 $E$는 볼록집합이므로 $z_0 \in E$이고 따라서

\[ z_0 \in E \setminus \bigcup_{i=1}^{n} G(z_i) = \bigcap_{i=1}^{n} \big[ B^{-1}(y_i) \times A(x_i) \big] \]

를 얻는다. 따라서 모든 $i = 1,\, \ldots,\, n$에 대하여 $x_0 \in B^{-1}(y_i)$이고 $y_0 \in A(x_i)$이다. 따라서 모든 $i = 1,\, \ldots,\, n$에 대하여 $y_i \in B(x_0)$이고 $B(x_0)$가 볼록집합이므로 $y_0 = \sum_{i=1}^{n} \lambda_i y_i \in B(x_0)$를 얻는다. 마찬가지 방법으로 모든 $i = 1,\, \ldots,\, n$에 대하여 $x_i \in A^{-1}(y_0)$이고 $A^{-1}(y_0)$가 볼록집합이므로 $x_0 = \sum_{i=1}^{n} \lambda_i x_i \in A^{-1}(y_0)$를 얻는다. 이는 $y_0 \in A(x_0)$임을 뜻한다. 따라서 $x_0 \in C$가 존재하여 $y_0 \in A(x_0) \cap B(x_0) \neq \emptyset$임을 보였으므로, 증명이 완료된다.