경영공학과 게임이론 기존연구 앞으로의 연구 독자적인 시스템을 최적화하는 연구 자연과의 싸움 다수의 시스템을 최적화하는 연구 참가자들간의 싸움, 협동, 타협 등등 연구의 목표 연구의 도구 Decision theory Game theory

게임이론 (game theory) 두 명(그룹) 이상의 참가자가 각각 자신을 이익을 최대화하기 위해 노력할 때 각자가 택해야 할 전략을 연구하는 학문 예: 전투기 기종 선정, 삼성전자와 하이닉스, 현대자동차와 Toyota, 미국정부와 Microsoft, 전투작전수립 1960 년 경까지는 주로 수학자들에 의해 연구되었다 1980 년 말 부터 경제학분야에 활발히 응용되기 시작함. 현재는 핵심적 분야로 인정됨 노벨경제학상 1994 John C. Harsanyi, John F. Nash Jr., Reinhard Selten for their pioneering analysis of equilibria in the theory of non-cooperative games

게임이론의 내용 Static games with complete information Dynamic games with complete information Static games with incomplete information Dynamic games with incomplete information

A classification of games Static games (simultaneous move games): All players make their choices at the same time. 2인 영화(零化)게임, 2인 비영화게임, 입찰 Dynamic games (sequential move games): Some players make their choices first, then other players observe these choices and then make thiers, etc. 경제시스템에서의 현상, 두 회사의 가격결정

Some examples Static games: Dynamic games: 입찰 Prisoner’s dilemma Cournot game (꾸르노게임, 생산량 결정) Bertrand game (베르뜨랑게임, 가격결정) 일반적인 n-person games Dynamic games: Entry game(시장진입게임) Stackelberg game(두 회사의 순차적 가격결정) 경매

게임이론 예제 1 월남전 중 한국군은 다음과 같은 세 가지의 공격전략과 이에 대응하는 베트남군의 세 가지 방어전략, 그리고 결과를 예측할 수 있었다. <한국군의 공격 전략> 1. 야간의 대대급 공격 2. 주간의 대대급 공격 3. 주간의 공중공격 후 야간공격 <베트남군의 방어전략> 1. 현 수준으로 고지 방어 2. 후방 예비사단의 추가 투입 3. 작전상 후퇴 후 기습 공격 한국군이 선택해야 할 전략은?

게임이론 예제 1 베트남군의 전략 1 2 3 한 국 군 의 전 략 1 2 3 0 1 -1 1 0 5 1 2 4

Solution methodologies for zero-sum two person games Removing dominated strategies Minimax principle Linear Programming Solve some problems, but not all of them. Can solve all the two-person zero-sum game.

Removing dominated strategies 베트남군의 전략 두 번째 1 2 3 1 2 3 0 1 -1 1 0 5 1 2 4 첫 번째 네 번째 한 국 군 의 전 략 세 번째

Minimax principle Dominated stratetgy 가 존재하지 않음 베트남군의 전략 1 2 3 2 0 2 1 2 3 1 2 3 -3 -2 6 2 0 2 5 -2 - 4 한 국 군 의 전 략 Dominated stratetgy 가 존재하지 않음

각 전략에 대하여 상대방의 전략에 따른 최대손실을 최소화하고자 하는 전략 Minimax principle 각 전략에 대하여 상대방의 전략에 따른 최대손실을 최소화하고자 하는 전략 Minimize the maximum loss 방법 각 전략별로 최대손실을 파악한다. 전략별 최대손실중 가장적은 손실에 해당히는 전략을 선택한다. 1 2 4 2 2 2 -6 2 2 의 이익과 6 의 손실중 좋은 값인 2 에 해당하는 1 번 전략을 선택한다. -6 4 2

Minimax principle 각 열의 최소값 선택 선택된 값들 중 최대인 값에 해당하는 전략 선택 -3 -4 5 6 1 2 3 1 2 3 -3 -2 6 2 0 2 5 -2 - 4 -3 한 국 군 의 전 략 -4 5 6

같은 생각으로 player 2 는 각 column 값의 최대값 중 최소값을 찾게 된다. 이를 minimax 값이라 함. 값을 찾으므로 maxmin 값이라 함 5 0 6 같은 생각으로 player 2 는 각 column 값의 최대값 중 최소값을 찾게 된다. 이를 minimax 값이라 함.

Minimax principle 로 해를 구할 수 없는 경우 끝없는 반복으로 인하여 해를 구하는 데 실패 Minimax principle 로 해를 구할 수 없는 경우 베트남군의 전략 1 2 3 1 2 3 0 -2 2 5 4 -3 2 3 - 4 (한국군) 첫 선택 (한국군) 세번째 선택 한 국 군 의 전 략 (월맹군) 두 번째 선택 (월맹군) 네 번째 선택

혼합전략과 선형계획법을 이용한 해법 혼합전략까지를 고려하면 모든 2인 게임의 안정해를 구할 수 있다. 혼합전략이란 사용할 전략을 확률에 따라 선택하는 것을 의미한다. 예: 가위, 바위, 보 혼합전략의 핵심은 당사자도 무슨 전략을 실제로 사용하게 될지를 모른다는 것 따라서 상대방도 모른다 는 것이다. 게임이론의 핵심은 내가 무슨 전략을 사용할지를 모른다는 것을 상대방이 알고 있다는 걸 내가 안다는 걸 상대방도 알고 있다는 걸…. 처럼 표현될 수 있다.

선형계획법 모형의 수립 혼합전략은 각각의 전략을 정해진 확률값에 따라 선택하는 것이다. 따라서 각 참가자가 각각의 전략을 선택하는 가장 적합한 확률값을 구하면 된다. 이를 위하여 다음처럼 정의한다.

선형계획법 모형의 수립 2 -1 -4 3 1 5 따라서 1번 참가자는 1번 2번 2번 참가자의 전략 1번 참가자의 기대이익 1번 2번 2 -1 -4 3 1 5 따라서 1번 참가자는 중 작은 값을 최대화하려고 할 것이다. 앞에서도 여러경우 중 가장 나쁜 결과 중 가장 나은 결과를 선택했음

모형화 방법 여러 개의 식들의 최소값을 최대화 하는 방법 따라서 앞의 경우에는

일반적인 선형계획법 모형의 수립 1번 2번 n 번 Player 2’s strategy Expected payoff of the player 1 1번 2번 n번째 전략

선형계획법 모형의 수립 Player 의 기본 생각은 minimize the maximum loss 이므로 Player 2’s strategy Expected payoff of the player 1 1 번 2 번 N 번째 n 개의 식으로 나타난 이 값들의 최소값을 최대화 (minimize the maximum loss) 하여야 한다.

여러 개의 식의 최소값을 최대화하는 방법은 실수범위의 새로운 변수 한 개를 지정 각각의 식들이 이 변수보다 크거나 같다고 제약 목적식은 이 변수를 최대화 하는 것으로 준다. 혼합전략의 합이 1 이 된다는 조건

예제 14.2 에 대한 모형 1 2 3 -2 5 4 -3 -4

Output of the LP Equilibrium strategy for player 1 is to choose action 1 with 63.63% and 2 with 36.36%. The expected gain of the player 1 is 0.1818. Note that player 2’s strategy is shown as dual variable values

게임이론 예제 2 (죄수의 고민문제) 용의자2 자백함 자백 안함 용의자1 자백 함 (-5,-5) (0, -20) (-1,-1) 2명의 남자가 강도사건의 용의자로 구속되어서 각각 다른 독방에 수감되어 있다. 담당 검사는 두 죄수가 강도 사건을 범행을 했다는 의심을 하고 있지만 물증을 아직 확보하지 못하고 있다. 따라서 검사는 각각의 용의자가 자백하는 경우는 5년, 다른 용의자가 자백할 경우는 자백한 사람은 석방, 하지 않은 용의자는 20년형, 그리고 두 용의자 모두 자백하지 않은 경우는 잡힐 때 경관을 폭행하였으므로 1년형을 구형하려 한다. 각 용의자가 실제로 받는 형량이 검사의 구형량과 일치한다고 가정할 때 각 용의자가 택할 최적의 선택은? 이 점에서는 내가 움직이면 나만 손해, 나는 움직일 수 없다. 즉 균형점 이 점에서 상대가 움직이면 내가 손해, 즉 나는 이 점에 머무를 수 없음 표. 죄수의 고민문제의 이득표 용의자2 자백함 자백 안함 용의자1 자백 함 (-5,-5) (0, -20) (-1,-1) 자백 안함 (-20, 0) 용의자 1이 움직일 때 용의자 2의 형량변화 용의자 2가 움직일 때 용의자 1의 형량변화

2인 게임의 균형점 죄수의 고민의 (자백, 자백) 처럼 상대방이 현재의 전략을 그대로 유지할 때 내가 혼자 움직이면 손해가 나게 되는 경우, 현재의 점을 균형점이라 부른다. 균형점의 예 앞에서 찾았던 모든 점들은 균형점이었음 Player 2 Player 1 전략 1 전략 2 (3, -5) (-1, -3) (-5, 2) ( 3, 3) 균형점

영화 Beautiful Mind 의 주인공 John F. Nash 의 균형이론 각자가 벗어나면 손해를 보게 되는 균형점이 존재한다. 이를 Nash 의 Equilibrium point 라고 하며, 1950 년 이를 발견한 Nash 는 1994 년 노벨 경제학상을 받게 된다.