최대최소 정리 - 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,\dots ),(0,1,0,\dots ),(0,0,1,\dots ),\dots \}$$

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

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

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

$$\bigcap _{k=1}^N{A}_{i_k}\ne \mathrm{\varnothing }$$

을 만족하면 $\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,\dots ,x_N\}$에 대하여

$$\mathrm{conv}\{x_1,x_2,\dots ,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)$가 유한닫힌집합이면, 집합족 $\left\{G(x)\right|x\in E\}$는 유한교차성을 갖는다.

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

$$\begin{array}{}(\ast )& \bigcap _{k=1}^{N}G(x_i)=\mathrm{\varnothing }\end{array}$$

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

$$x\in L\cap G(x_i)⟺d(x,L\cap G(x_i))=0$$

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

$$c\mapsto \lambda (c):=\sum _{i=1}^{N}d(c,L\cap G(x_i))$$

를 정의하면 임의의 $c\in C$에 대하여 $\lambda (c)\ne 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=\left\{i\right|d(c_0,L\cap G(x_i))\ne 0\}$으로 정의하자. 앞에서 살펴보았듯이 $I\ne \mathrm{\varnothing }$임을 알 수 있다. 또한

$$c_0\notin \bigcup _{i\in I}G(x_i)$$

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

$$c_0=f(c_0)\in \mathrm{conv}\left\{x_i\right|i\in I\}\subseteq \bigcup _{i\in I}G(x_i)$$

이 되어 모순이 발생한다. 따라서 집합족 $\left\{G(x)\right|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)\ne \mathrm{\varnothing }.$$

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

$$\bigcap _{x\in E}G(x)=\mathrm{\varnothing }$$

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

$$G(x_0)=G(x_0)\setminus (\bigcap _{x\in E}G(x))=\bigcup _{x\in E}[G(x_0)\setminus G(x)]$$

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

$$G(x_0)=\bigcup _{i=1}^n[G(x_0)\setminus G(x_i)]=G(x_0)\setminus (\bigcap _{i=1}^{n}G(x_i))$$

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

정리 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)\ne \mathrm{\varnothing }$를 만족한다. (단, $A^{-1}(y):=\left\{x\in X\right|y\in A(x)\}$로 정의한다.)

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

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

그러면 모든 $(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}[B^{-1}(x)\times A(y)]$$

임을 알 수 있다. 그러므로 

$$\bigcup _{(x,y)\in E}G(x,y)=E\setminus \bigcup _{(x,y)\in E}[B^{-1}(x)\times A(y)]=\mathrm{\varnothing }$$

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

$$z_0=(x_0,y_0)=(\sum _{i=1}^n{\lambda }_i{x}_i,\sum _{i=1}^n{\lambda }_i{y}_i)\in \mathrm{conv}\{z_1,\dots ,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[B^{-1}(y_i)\times A(x_i)]$$

를 얻는다. 따라서 모든 $i=1,\dots ,n$에 대하여 $x_0\in B^{-1}(y_i)$이고 $y_0\in A(x_i)$이다. 따라서 모든 $i=1,\dots ,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,\dots ,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)\ne \mathrm{\varnothing }$임을 보였으므로, 증명이 완료된다.