응용수학과 컴퓨터공학 I
- 강의 개요 및 게임이론 개요
부산가톨릭대학교 컴퓨터공학과 변 상 선
Course introduction
•
수업 진행•
강의와 토론•
평가•
중간 (30), 기말 (40), 출석 (10), 토론참여 (20)•
오픈북 / 오픈노트•
[email protected]•
교재•
하임 샤파라 지음, 이재경 옮김, “n분의 1의 함정: 합리적이고 전략적인 게임이론의 모든 것”, 반니Game theory
• Game
• 다수의 이해당사자들이 각자의 또는 그룹 (2명 이상의 이해당사자가 그룹을 구성)의 이득을 최대화 하기 위해 전략적 의사결정 (decision-making) 을 하는 행위
• 전략적 의사 결정
• 주어진 상황에서, 또는 상대방의 전략에 따라 내리는 의사결정
• 다수의 이해당사자 => Player
• 합리성 (rationality)
• 이론적 합리성 => 현실적 비합리성
• Game theory
• 주어진 상황에서 플레이어들 개인 또는 그들의 그룹이 취할 수 있는 최적의 전략과 이득을 수학적으로 제시하는 응용 수학의 한 분야
• 가장 폭넓게 적용되는 분야는 경제학
• 그 외에 정치학, 컴퓨터공학, 생물학에도 적용
게임이론의 역사
•
John von Neumann and Oskar Morgenstern
•
Theory of Games and Economic Behavior, 1944
•
최소최대정리 (minimax theorem)
•
Two-person zero-sum 게임에서 각 플레이어는 자기 가 잃을 수 있는 최대 금액을 고려했을 때, 이 최대 금액을 최소화 할 수 있는 전략이 존재하고, 이것이 최적의 전략 이다
•
John Nash
• Nash equilibrium (내쉬 균형), Nash bargaining
solution (NBS)
•
<=> 아담 스미스 “국부론”
•
개인의 이익 추구는 집단을 이롭게 한다
게임이론의 역사
• Economics Nobel Laureates
• Paul A. Samuelson (1970)
• Kenneth J. Arrow (1972)
• Reinhard Selten, John F. Nash Jr., John C. Harsanyi (1994)
• Robert E. Lucas Jr. (1995)
• William Vickrey (1996)
• Thomas C. Schelling, Robert J. Aumann (2005)
• Eric S. Maskin, Leonid Hurwicz, Roger B. Myerson (2007)
• Alvin E. Roth, Lloyd Shapley (2012)
• Jean Tirole (2014)
내쉬 균형
•
게임에서 경쟁자 대응에 따라 최선의 선택을 하면 서로가 자신의 선 택을 바꾸지 않는 균형 상태•
게임에서 상대방의 전략에 따라 어떤 선택을 했을 때, 경쟁자의 전 략이 바뀌지 않는 상태에서 더 큰 이득을 내는 선택이 불가능한 상 황 => 이 상황이 모든 게임 참가자에게 발생되는 상태•
네가 생각하고 있는 것을 내가 알고 있다고 네가 알고 있다는 것을 나는 안다내쉬 균형
•
죄수의 딜레마•
공범 두 명을 각각 심문함•
각 공범은 다른 공범과 일체 의사소통이 불가능한 상태•
전략: 자백 또는 묵비권•
보상•
둘 다 자백: 둘다 징역 1년•
둘 중 하나만 자백: 자백한 쪽은 즉시 석방, 자백하지 않은 쪽은 징역 10년 독박•
둘 다 묵비권: 둘다 징역 5년•
여기서 내쉬 균형은?자백 묵비권
자백
(-5, -5) (0, -10)
묵비권(-10, 0) (-1, -1)
내쉬 균형
2개 타공 1개 타공 2개 타공
(4, 4) (6, 3)
1개 타공(3, 6) (5, 5)
•
유전개발
•
A, B 두 회사가 총 매장량이 1억 2000만달러의 가치를 갖는 유전을 개발
•
유공을 뚫는 비용 1개당 1000만 달라
•
전략: 유공은 1개 또는 2개를 뚫을 수 있음
•
보상
•
각 회사가 취득하는 석유의 양은 유공의 개수에 비례
•
여기서 내쉬 균형은?
내쉬 균형
돌진 회피
돌진
