내쉬 균형(Nash equilibrium)의 존재성

얼마전에 별세한[1] 내쉬 선생의 그 한 쪽짜리 논문[2]을 대충 봤는데, 너무 짧아서 유명하다.[3] 뭔가 무림 초고수의 내공[4]-_- 같은게 있는 사람이다. ㅎㅎㅎ 사실 그 내용은 자세히 보지 않았는데, 지금 보니 내쉬 균형의 존재성을 증명하기 위해 카쿠타니 고정점 정리를 사용한다.

카쿠타니 시즈오가 누군가 싶어 위키피디아를 보니, 2차 세계대전 전후로 미국과 일본에서 활약한 수학자인 듯 하다. 당시 미-일은 서로 적대국인데, 어떻게 공부했는지 개인사가 꽤나 궁금해진다.

본인은 이와 관련하여 전공을 하지 않았고, 본 블로그의 글은 본인이 대충-_- 이해한 내용이므로 내용이 틀릴 수도 있다. ㅋㅋㅋ

.


여하간 용어를 설명하자면 이러하다.

2X는 X의 power set을 의미한다.

set-valued function은 말 그대로 함수값이 set인 function이다.

closed graph는, set-valued function인 φ: X → 2Y이 주어질 때, X × Y의 부분집합 {(x,y) | y ∈ φ(x)}이 product topology로서 closed면 φ는 closed graph라고 정의한다.

fixed point는, set-valued function인 φ: X → 2X이 주어질 때, a ∈ φ(a)인 a를 φ의 fixed point라 부른다.

카쿠타니 고정점 정리는, 유클리드 공간 Rn에서 공집합이 아니고 compactconvex인 부분집합을 S라 하고, set-valued function φ: S → 2S가 closed graph이면 φ는 fixed point를 가진다는 정리다.

.


그러면 어떤 종류의 게임에서 각 플레이어가 선택 가능한 유한한 개수의 전략들(pure strategy라 부르는 듯)이 n개 있다고 하자. 각 pure strategy에 대해 자신이 선택할 확률을 할당하는데, 이걸 mixed strategy라 부르는 것 같다. 뭐 각자의 입장에서 선택 불가능한 전략은 확률을 각 pure strategy에 대해 취할 확률을 0으로 세팅하면 되므로, 어쨌든 모든 플레이어가 같은 dimension의 전략 세트를 두고 게임을 플레이 할 수 있다.

각 플레이어들에 대해 이 mixed strategy는 Rn의 한 점이 된다. 각 플레이어들이 취할 수 있는 모든 Rn의 한 점의 합집합을 S라 하자. 각자 Rn의 한 점을 선택하면 그 결과는 Rn의 부분집합이 되므로, 한 번의 게임이 set-valued function의 한 번의 대응이라 볼 수 있다.

예를 들어 A, B, C가 가위바위보를 한다고 하자. A는 가위를 낼 확률을 0.1, 바위를 낼 확률을 0.5, 보를 낼 확률을 0.4로 세팅한다고 하자. A의 mixed strategy를 (0.1, 0.5, 0.4)라 쓰면, R3의 한 점이 된다. B, C의 mixed strategy를 (0.2, 0.8, 0), (0.3, 0.3, 0.4)로 세팅하면 R3의 세 점이 되고, A의 입장에서 (0.1, 0.5, 0.4)가 세 점에 대응되는 set-valued function의 함수값이 된다.

S가 bounded인 이유는 자명한데, closed인 이유는 각자 mixed strategy들의 sequence P_1, P_2, …. 의 limit point도 여전히 선택가능한 전략이기 때문인 듯 하다. 뭐 각 pure strategy 별로 확률을 엄청 근접하게 선택할 수 있으면 그 확률도 선택할 수 있겠지. convex인 이유는 한 mixed strategy P에서 다른 mixed strategy Q까지, tP + (1-t)Q가 모두 선택 가능하기 때문인 듯 한데, 이것도 확률을 연속적으로 쪼금씩 분배하면 되니까 가능한 듯 하다.

이 set-valued function이 closed graph인 이유는 S가 closed니까 그 product topology에서도 closed가 되는 듯 하다.

여하간 대충 그렇다 치면-_- 카쿠타니 고정점 정리를 쓸 수 있으므로, 각 플레이어는 자신이 선택한 mixed strategy가 그대로 게임의 결과(즉, set-valued function의 함수값)가 되는 상태가 반드시 존재한다. 이 점을 내쉬 균형이라 부른다.

.


아참 깜빡했는데, 일전에 이야기한 이코노미스트지의 Big economic ideas 시리즈[5]에서 Nash equilibrium편[6]도 참고하시라.

.


[1] 내 백과사전 존 내쉬 별세 2015년 5월 24일
[2] Nash, John (1950) “Equilibrium points in n-person games” Proceedings of the National Academy of Sciences 36(1):48-49. https://doi.org/10.1073/pnas.36.1.48
[3] 내 백과사전 분량비 중요도가 가장 높은 수학논문? 2010년 11월 7일
[4] 내 백과사전 존 내쉬의 지도교수 추천서 2015년 6월 5일
[5] 내 백과사전 이코노미스트지의 Big economic ideas 시리즈 2016년 8월 1일
[6] 이코노미스트 Prison breakthrough Aug 20th 2016

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중

This site uses Akismet to reduce spam. Learn how your comment data is processed.