게임이론 Von Neumann Theory of Games and Economic Behavior with Oskar Morgenstern, widely recognized as the first formal treatment of game theory. 1944Oskar Morgenstern Hugarian genius Computer, Functional analysis, game theory, Atomic bomb "If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." -JvN
게임이론의 쓰임 체스, 장기, 바둑 등 오락 사업, 정치, 옥션, 분배 등 실제 문제 사회학, 경제학 등 학문 전쟁 또는 외교 ( 쿠바 미사일 위기, 나폴 레온과 웰링턴 Waterloo 전투 )
게임의 요소 게임의 경기자 게임의 규칙 게임의 가능한 결과 ( 승패, payoff) 게임에서 알수 있는 정보 ( 공유, 사유 ) 게임의 종류에는 교대형과 동시진행형이 있다.
강도게임 강도와 정환 규칙 : 1 억원을 안주면 폭파한다. 정환은 줄수도 안줄수도 있다. 강도는 1 억원을 확인할수 있다. 강도는 폭파할수도 안할수도 있다.
강도 정환 강도 1 억줌 1 억안줌 폭파 비폭파 폭파 비폭파 정환의보수 강도의보수
Game tree for game G
Tick Tack Toe
Strategic form of game G Pure strategy: if the node is achieved, the player’s moves are listed
Zermelo ’ s algorithm Winning strategy: a choice for each node such that player I or player II always wins no matter what the other player does. Subgames: replace L with W in subgames. If there is a winning strategy for replaced subgrames, then there is one for orginal games. There exists an algorithm to tell whether there exists a winning strategy or not in a finite game.
Hex 0 표와 x 표를 번갈아서 그린 다. 연결하는 사람 이 이긴다. 비길수는 없다. Player I 이 항상이긴다.
Zermelo ’ s Theorem Let T be any set of outcomes in a finite two-player game of perfect information without chance moves. Then either player I can force an outcome in T or player II can force an outcome in ~T.
Saddle point Strategy pair (s, t): player I 이 보았을때 결과 v 는 t 열에 있는 것중 최고중하나이 고 v 는 s 행의 있는 결과중 최하중하나이 다. (“ 즉 상대방이 움직인 경우의 최소결 과 를 극대화 minmax”) A finite, strictly competitive game of perfect information has a saddle point (s, t).
체스 경우의 새들점 L white wins W black wins D draw
Nash Equilibrium ( 내쉬균형점 ) (s,t) 가 균형점이려면 s 는 player I 이 player II 가 t 를 두려고 할때 최선의 수이 고 역으로 t 는 player II 가 player I 이 s 를 두려고 할때 최선의 수이여야 한다. 내쉬정리 : 모든 유한 게임은 최소한 한 개의 내쉬균형을 가진다.
적대적게임 어떤 결과에도 두사람의 보수의 합은 0 이된다 L R U D 경기자 2
어떤 전략을 사용 ? 1 의 선택후 2 는 1 에 가장 불리한 전략을 사용한다. 경기자 1 은 전략을 선택했을 때 최악의 결과가 최선인 전략을 택한다 최소극대화전략 (maxmin) L R U D 경기자 1 의 최소 보수 1,0 경기자 2 의 최소 보수 –1,3
추적게임 ( 혼합전략 ) 고속도로산길 고속도로 산길 경찰 죄수의 행 최소 경찰의 최소보수
죄수가 고속도로를 택할 확률 p 산길 (1-p) 라 하면 경찰이 고속도로를 추적한다고 하면 도주에 성공할 확률은 px 0 + (1-p)x 0.9 = 0.9(1-p) 경찰이 산길을 택한다면 px0.8 + (1-p)x 0.3 = p /70 3/7 범죄자의 최소 극대화전락 보수
경찰관이 고속도로를 추적할 확률 q 라하 고 산길을 추적할 확률을 (1-q) 라 하자. 죄수가 고속도로를 이용한다면 qx1 + (1-q)x02= q 가 성공률 죄수가 산길을 이용한다면 qx0.1 + (1-q)x 0.7 = q /70 5/14 경찰의 최소 극대화전락 0.7
열등전략 경기자 1 의 전략 D 는 M 에 비해 명백열등 전략이다 이경우 D 대신 M 을 쓰므로 D 는 없다고 생각하면된다. L R U 1 M 1 1 D
상점위치선정게임 1 킬로의 거리 10 미터 간격으로 집이 있다. 1 가 구에 1 인이 살고 있다. 상인 1 은 0.0 에서 0.5 까지 선택하고 상인 2 는 0.5 에서 1 까지 선택한다. 이경우 상인 1 은 커질수록 절대우위전략이다. 상인 2 는 작아질수록 절대우위전략이다
내쉬균형 게임에서 각경기자는 상대방 경기자의 행동에 따라서 최선의 전략을 사용할수있다. 경기자들이 택할 전략으로 s = (s1, s2, …, sn) 라고 하자. 이때 경기자 i 의 전략을 s i = (s1 i, s2 i, …, sn i ) 이라고 하자. 각 경기자는 전략 s i 를 최 상의 것으로 만들것이다. 이경우 다른 경기자 도 전략을 바꾸어야 한다. 어떤 시점에서 더 이 상 전략을 바꿀수 없게 된다. 즉 모든 다른 전 략이 정한 전략보다 못하게 되는 점이 있다. 이 것을 내쉬균형이라고 한다.
Brouwer 정리 유클리드 공간의 볼록집합에서 자신으 로 가는 연속사상은 항상 정지점을 가진 다. 증명 ( 위상수학 )
References 게임이론, 김영세, 박영사 게임이론 갈라잡이, 신성휘, 박영사 Fun and games, Binmore, D.C. Heath Co. Mathematics in life, society, and the world, Chapter Beautiful Mind, Silvia Nasar The essential John Nash, Nash, Silvia Nasar, H. Kuhn