수학의 기초와 응용

수학의 기초와 응용

부산가톨릭대학교 컴퓨터공학과

변 상 선

Course introduction

• ^{수업 진행}

• ^{강의와 토론}

• ^평가

• 중간 (30), 기말 (30), 출석 (10), 토론참여 (30)

• ^{오픈북 / 오픈노트}

• [email protected]

• ^교재

• Roger A. McCain 지음, 이규억 옮김, “게임이론: 쉽게 이해할 수 있는 전략분석”, 제 3

판, 시그마프레스

Game theory

•

^Game

•

다수의 이해당사자들이 각자의 또는 그룹 (2명 이상의 이해당사자가 그룹을 구성)의 이득을 최대화 하기 위해 전략적 의사결정 (decision-making) 을 하는 행위

•

^{전략적 의사 결정}

•

최선반응 (best response)

•

주어진 상황에서, 또는 상대방의 전략에 따라 내리는 의사결정

•

다수의 이해당사자 => 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)

vs. 신고전파 경제학

•

^공통점

•

합리성 (rationality)

•

자기 자신의 이득 최대화, 즉 최선반응

•

가능성의 범위를 좁혀 수학적 분석이 가능하고 경제 체계의 효율성 (비용 < 이익)을 평가하는 잣대

•

비용 < 이익인 전략 선택이 합리적인 전략선택

•

^{신고전파 경제학}

•

주어진 상황에서 자기자신의 이득을 최대화 하는 것

•

^한계

•

주어진 상황 (제도) 만을 고려, 즉, 나의 최선의 전략선택으로 인해 주어진 상황이 변할 수도 있는 것에 대한 고려가 없음

•

^게임이론

•

이해당사자들간의 상호작용이 전략 선택에 반영이 됨

죄수의 딜레마

• Prisoner’s dilemma

• Payoff table (또는 payoff matrix)

Al

confess don't

confess 10 years,10 years 0,20 years Bob

don't 20 years,0 1 year,1 year

죄수의 딜레마

• 이기적이고 합리적인 행동이 결과적으로 열등한 결과를 초래

• ^{비협조해가 우월전략}

• <=> 국부론과 대치

• 신고전파 경제학의 한계

• ^{다른 결과}

• ^{의사소통이 있다면?}

• 이 게임을 반복한다면?

게임의 표현

• 정규형 (또는 전략형)

• Payoff table을 통해 표현

• ^전개형

• 각각의 전략적 결정을 분기점으로 나타내는 나무 그림으로 게임

을 표현

또 다른 게임

• ^{광고 게임}

• 역시 비협조해가 우월전략

Fumco

don’t advertise advertise

don’t advertise 8,8 2,10

Tabacs

advertise 10,2 4,4

정규형의 표현: 기업의 사례

• 특정 사업의 규제해제로 인한 어려움

• ^공익사업

• 가격 규제 및 이윤의 제한

• ^{대신 독점}

• ^{규제가 해제}

• 경쟁기업이 시장에 진입하고 가격경쟁을 시도함

• 과연 가격경쟁에 대응하는 것이 효과적일까?

정규형의 표현: 기업의 사례

• 한 참가자가 먼저 전략을 선택하고, 다른 참가자는 전략을 선택하기 전에 기다렸다가 경쟁자가 어떻게 하는가를 볼 수 있음

• Leader-follower 게임

• 전개형으로 표현하는 것이 더 직관적, 하지만 정규형으로도 표현 가능

정규형의 표현: 기업의 사례

Goldfinch If Bluebird enters then

accommodate; if Bluebird does not enter, then do

business as usual.

If Bluebird enters then initiate price war if Bluebird

does not enter, then do business as usual.

enter 3,5 -5,2

Bluebird

dont 0,10 0,10

제로섬 게임과 비일정합 게임

•

Zero-sum 게임

•

이득의 합이 항상 0인 경우

•

일정합 게임 (Constant-sum game)

•

플레이어들이 어떤 전략을 선택하든 상관없이 모든 플레이어들의 이득의 합이 일정한 상수인 게임

•

제로섬 게임 => 일정합 게임

•

^{독재자 게임 Amanda}

(Whether Barbara accepts

or rejects) offer 50-50

(Whether Barbara accepts or rejects) offer 90-10

If Amanda offers 50-50 , then accept; if Amanda offers 90-10,

then accept 50,50 10,90

If Amanda offers 50-50 , then accept; if Amanda offers 90-10, then reject

50,50 0,100

If Amanda offers 50-50 , then reject;

if Amanda offers 90-10 , then accept 0,100 10,90 Barbara

If Amanda offers 50-50 , then reject;

if Amanda offers 90-10 , then reject 0,100 0,100

제로섬 게임과 비일정합 게임

• 비일정합 게임 (Non-constant-sum game)

• 이득의 합이 상수가 되지 않고, 선택하는 전략에 따라 변하는 게 임

• 광고게임, 죄수의 딜레마

전개형으로 나타낸 죄수의 딜레마

• 죄수의 결정이 순차적으로 발생된다고 가정

• 단, 앞서 결정한 죄수의 전략을 그 다음에 결정하는 죄수는 알 수 없음

전시동원

우월전략과 사회적 딜레마

•

우월 전략 (Dominant strategy)

•

다른 플레이어가 어떤 전략을 선택하건 관계 없이 한 전략이 다른 전략보다 많은 이득을 초래하는 경우의 전 략

•

우월전략 균형 (Dominant strategy equilibrium)

•

모든 플레이어의 최선의 전략이 우월전략인 경우

•

협조 해와 비협조 해 (Cooperative and noncooperative solution)

•

협조 해 => Social optimal

•

모든 플레이어의 개인의 이득 최대화와 관계없이, 모든 플레이어의 전체 이득을 유발하는 해 (게임의 결 과)

•

^{비협조 해}

•

모든 플레이어의 개인의 이득 최대화로 인한 게임의 결과

우월 전략과 사회적 딜레마

•

^{사회적 딜레마}

•

우월전략 균형을 갖는데, 이 우월전략이 이 비협조해를 유발하는 경우

•

우월전략 균형의 해가 비균형전략의 해보다 나쁜 경우

•

^{쓰레기 버리기 게임}

•

사회적 딜레마가 있는 게임

Table 1. The Dumping Game in Normal Form

Mr. Smith

dump hire truck dump 4000,4000 5000,3500 Mr. Jones

hire truck 3500,5000 4500, 4500

가격정책 딜레마

• 우월전략 균형이 있고, 우월전략이 비협조해 임

• 즉, 사회적 딜레마가 있는 해

First payoff to Acorp,

second payoff to Bfirm. Bfirm!

low high Acorp low 20,20 90,5 high 5,90 60,60

!

협조적 제품 개발

• 사회적 딜레마가 없는 게임

• 즉, 우월전략 균형이 있고, 그 우월전략이 협조해를 유발함

Table 4. Collaborative Product Development

Omnisoft

commit hold back commit 5,5 2,3 Microquip

hold back 3,2 1,1

2개 이상의 전략이 있는 게임

•

3개의 전략이 있는 쓰레기 버리기 게임

•

‘쓰레기 버리기’가 여전히 우월전략

•

모든 플레이어의 우월전략이 ‘쓰레기 버리기’

•

^{사회적 딜레마}

Table 7. The Dumping Game with Three Strategies

Mr. Smith

dump hire truck burn dump 4000,4000 5000,3500 4750,3750 hire truck 3500,5000 4500,4500 4250,4750 Mr. Jones

burn 3750,4750 4750,4250 4650,4650

정치 게임

• ^{2명의 후보}

• ^{당선되는 것이 목표}

• 득표율이 payoff => 일정합 게임

• 중도적 정책을 선택하는 것이 모든 정치인의 우월전략 => 우월전략 균형

Table 5. Vote Payoffs for Two Candidates

Governor Gray left. middle right.

left 55,45 30,70 50,50 middle 75,25 50,50 70,30 Senator Blank

right 50,50 25,75 45,55

교과서 쓰기 게임

• 다른 교수보다 두꺼우면 됨

• 우월전략이 없는 게임

Table 9. Writing a Game Theory Textbook

Prof. Heffalump 400 p. 600 p. 800 p.

400 p. 45,45 15,50 10,40 600 p. 50,15 40,40 15,45 Dr. Boingboing

800 p. 40,10 45,15 35,35