수학의 기초와 응용 X
부산가톨릭대학교 컴퓨터공학과
변 상 선
순차적 게임
•
Sequential games => games in extensive form•
기존의 정규형의 형태로 표현되는 게임은 동시에 전략의 선택이 발 생•
순차적 게임에서는 어떤 순서에 의해 전략의 선택이 발생•
상대의 전략 선택을 보고 또는 상대가 전략을 선택하기 전에 결 정을 하는 경우진입 저지를 위한 전략적 투자
•
스피젤라 사는 컴퓨터 칩을 생산하는 회사
•
칩의 단가에 따른 수요
•
3,000,000 (700), ,6,000,000 (400), 9,000,000 (200)
•
생산 비용
•
연간 칩 하나당 $333.33
•
따라서, 3,000,000개의 칩을 생산하면 $10억의 비용이 연간 소모됨
•
경쟁사인 패서 사가 시장에 진입하려고 함
•
현재 공장 하나에서 3백만개의 칩을 생산, 따라서, 연간 $11억의 이윤 ($21억 - $10억)이 발생
•
공장을 하나 더 늘리면 6백만개의 칩을 생산, 따라서, 연간 $4억의 이윤 ($24억 - $20억)이 발생
•
공장을 세 개까지 운영하면, 9백만개의 칩을 생산, 따라서, 연간 $12억의 손실 ($18억 - $30억) 이 발생
진입 저지를 위한 전략적 투자
•
스피젤라의 최선의 전략은?
•
공장을 2개 짓는 것
•
패서가 결정하기 전에 제 2공장을 짓게 되면, 패서의 공장은 3번째 공장이 됨
•
이렇게 되면 모든 공장당 연간 $4억을 손해 봄
•
이 사실을 패서가 인지할 것이고, 패서는 자신들의 공장이 전체 시장의 3번째 공장이 되려고는 하지 않을 것 이고, 스피젤라는 연간 $4억의 이윤을 확보하게 됨
•
만약, 제 2공장을 짓지 않는다면
•
패서가 $2억달러의 이윤을 얻을 것이기 때문에, 패서는 공장 하나를 지을 것이고, 이로 인해 스피젤라의 이윤은 $2억달러가 됨
•
제 2공장을 짓는것
•
진입저지를 위한 전략적 투자
진입 저지를 위한 전략적 투자
• 정규형으로 표현
• 순차적이 아닌 동시에 전략을 선택하는 형태로 표현
패서
build don’t
스피젤라
build (-800,-400) (400, 0) don’t (200, 200) (1100, 0)진입 저지를 위한 전략적 투자
•
전개형으로 표현•
하부게임 (subgame)•
아래 그림에서 1, 2A, 2B•
2A와 2B에서 전략 선택은 패서가 수행•
1에서는 스피젤라가 수행•
원래 게임도 하부게임의 하나A Subgame
Another Subgame
진입 저지를 위한 전략적 투자
진입 저지를 위한 전략적 투자
•
패서는 2A에서는 don’t를 선택할 것이고, 2B에서는 build를 선택할 것임•
즉, subgame 2A와 2B에서 패서의 전략선택은 각각, don’t, build 임•
그리고, subgame 1에서 스피젤라의 전략선택은 build 임•
즉, 모든 하부게임이 균형점 (equilibrium, 확실한 전략선택)을 가짐•
순차 게임을 구성하는 모든 하부게임이 균형점 (정확하게는 내시균형)을 갖는 경우, 이 게임은 하부게임 완전균형 (subgame perfect equilibrium) 을 갖는다고 함•
진입 저지 게임에서 각 하부게임 2A -> don’t, 2B -> build, 1 -> build 이 균형점을 가지므로 게임 1은 하부게임 완전균형을 가지고, 이 게임 1의 하부게임 완전균형이 바로 이 순차적 게임의 내시 균형임•
하부게임 완전균형•
원래 게임의 모든 하부게임이 균형을 갖는다•
원래 게임의 균형으로 인해 하부 게임의 균형이 결정, 또, 그 하부 게임의 균형이 결정 => 이렇게 해서 도달된 최종 하부 게임의 균형, 이 균형을 원래 게임의 하부게임 완전균형이라고 함•
1 -> 짓는다, 2 -> 안짓는다 => 이것이 하부게임 완전균형•
하부 게임 완전균형을 찾는 방법•
후진 귀납법 (backward induction)진입 저지를 위한 전략적 투자
•
후진 귀납법순차적 게임을 위한 개념
• 죄수의 딜레마의 순차적 전개
• 앨이 1단계에서 밥이 2단계에서 각각 자백할 것인지 여부를 결정
• 단, 이 경우 밥은 앨이 무슨 결정을 내렸는지 알 수 없다고 가정
• 즉, 타원 2의 위쪽 가지에 있는지, 아래쪽 가지에 있는지 밥이 알지 못함
• 이 경우, 타원 2는 하부게임이라고 하지 않음
• 한 게임의 하부게임은 이전 분기의 게임 결과 (즉, 현재 하부게임의 시작 상태) 를 알고 있는 상태에서 진행됨 => 완전정보
순차적 게임을 위한 개념
순차적 게임을 위한 개념
• 하부게임
• 완전정보를 가지고 진행되어야 함
• 고유 하부 게임 (proper subgame)
• 전체 하부게임의 집합에서 원래게임 (original game) 을 제외한 나머지 하부게임
• 기초 하부 게임 (basic subgame)
• 2A, 2B
• 최소 하부게임
• 더 이상의 전략 결정을 갖지 않는 게임
• 복합 하부 게임 (<=> 기초 하부 게임, complex subgame)
• 작은 단위의 하부게임의 조합으로 이루어진 하부게임
• 1
• 어떤 게임을 구성하는 하부게임들이 모두 내시 균형을 가질 때 “이 게임은 하부게임 완전균형을 갖는다” 라고 함
• 순차적 게임은 누가 먼저 전략을 선택하는가, 즉, 행동구조 (commitment structure)를 가져야 함
순차적 게임을 위한 개념
The game as a whole is a subgame,
but is not proper.
순차적 게임을 위한 개념
If a game has no proper subgames,
we say it is basic.
순차적 게임을 위한 개념
• 정규형으로 표현
• 순차적이 아닌 동시에 전략을 선택하는 형태로 표현
• 정규형 게임의 내시균형 ≠ 순차적 게임의 내시균형
• 하부 게임 완전 균형 => 정규형 게임의 내시균형의 또 다른 정제
패서
build don’t
스피젤라
build (-800,-400) (400, 0) don’t (200, 200) (1100, 0)내시와 하부 게임 완전균형
•
순차적 게임에서의 하부 게임 완전균형•
순차적 게임에서의 내시균형, 즉, 최선반응 균형임•
시장 진입 게임•
정규형 게임•
두 개의 내시균형•
순차적 게임•
파랑새가 먼저 결정하고, 방울새가 나중에 결정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.
Bluebird
enter 3,5 -5,2
don’t 0,10 0,10
내시와 하부 게임 완전 균형
•
이 상황에서 후진 귀납법을 적용시키면 (3, 5)가 하부 게임 완전균 형•
즉, 두 개의 내시균형 가운데 (3, 5) 만이 하부 게임 완전균형임•
즉, 모든 하부 게임 완전균형은 내시 균형, 하지만, 모든 내시 균형 이 하부 게임 완전균형은 아님지네 게임
• 참가자는 애나 (A) 와 바브 (B)
• 책상위에 돈뭉치가 있음
• 첫 째 단계에서, 애나가 먼저 돈을 잡거나, 바브가 잡도록 통과 시킬 수 있음
• 만일, 애나가 잡으면, 돈을 둘이 나누어 가지는데, 애나가 더 많이 갖는다
• 만일, 바브가 잡으면, 게임 진행자는 판돈을 더 놓는다
• 둘 째 단계에서는 바브가 먼저 돈을 잡을 수 있는데, 만약, 잡으면 애나보다 바브가 더 많이 가져감
• 둘 째 단계에서 바브가 통과시키면, 둘 이서 판돈을 반반씩 나누어 갖고 게임은 종료
지네 게임
•
바브의 선택은? => 잡는다
•
애나의 선택은? => 잡는다
•
따라서, 애나가 돈을 잡는 것이 이 게임의 하부 게임 완전균형
•
지네 게임
•
이를 무한히 확장시킬 수 있으므로
코코넛 게임
• 로빈슨과 조는 표류되었음
• 작은 보트를 타고 노를 열심히 저어 4 그루의 야자수만 있는 아주 작은 섬에 도달 하였음
• 일단 생존을 위해 야자수를 따기로 하였음
• 각 야자수에는 5개의 코코넛이 있어, 총 20개의 코코넛이 있음
• 번갈아가며, 한 사람이 야자수에 올라 5개의 코코넛을 따면, 나머지 한 사람은 밑에서 이를 주워 배에 담는다
• 그리고, 20개의 코코넛을 둘이서 나누어 갖기로 하였음
• 하지만, 어느 단계에서든 밑에서 배에 주워 담는 사람은 혼자서 여태껏 딴 코코넛을 독차지하기 위해 보트를 타고 가버릴 수 있음
• 이들은 모두 합리적이어서, 최대한의 코코넛을 차지하려고 함
코코넛 게임
•
이 게임의 하부게임 완전균형은?pa s s
grab
pa s s
grab
pa s s
grab
pa s s
grab
J R J R 10,10
0,20 15,0
0,10 5,0
Figure 9. The Coconutty Game
코코넛 게임
•
경제학에 영향을 미침
•
분업과 우회생산 (최종소비재를 생산하는 것이 아닌, 중간재 생산)
•
애덤 스미스와 오스트리아 학파의 경제학자들이 분업과 우회생산의 효용성을 주장
•
코코넛 채취
•
땅에 떨어진 코코넛은 식량이 되기 위한 중간재 역할 => 우회생산
•
나무 올라가기와 주워담기를 나누어서 진행 => 분업
•
하지만, 결과적으로 한 사람이 계약을 파기함으로써 불공정한 결과를 가져올 수 있다
=> 법적인 강제력 필요
•
갑질!!
반격
• 냉전시대
• 소련은 마음만 먹으면 서독을 공격할 수 있음
• 이를 위해 미국은 군대를 서독에 주둔시켰음
• 하지만, 소련의 전면 공격을 막아내기에는 군대의 규모가 작았음
• 어떻게, 미국은 소련의 공격을 억제할 수 있었는가?
• 규모가 작더라도 서독에 군대를 주둔시키는 전략으로 억제가
가능
반격
•
첫 번째 경우 => 미군이 서독에 군대를 주둔시키지 않은 상태
•
서독이 공격당하면, 본토에 있는 핵무기를 사용하겠다는 보복 위협
•
하지만, 이 게임의 하부 게임 완전균형은, 미국은 공격하지 않고, 소련은 공격하는 것이다
•
즉, 핵억제는 신빙성이 없음
•
