7 장 : 게임이론?
입지선택게임 A B,. M L,,. A B 10 5. M L 7 3.?
입지선택게임 ( 계속 ) M L (player). M L {A, B}. M L : M L (payoff).. M (strategy), (equilibrium). A B 7 A 3 L B
게임이론의역사 1944 The theory of games and economic behavior. (zero-sum), (cooperative). 1950 (Nash Equilibrium) - Nash, Shapley, Harsanyi,....,,,...,,....,,,... - (Scott Shenker)
2, 3,.... 게임모형의분류 -. -.. -,,,, ( : ).. -, ( ) ( : ). -... ( : ). -. 2 (bimatrix game) - 2
동시게임.. 2 2 (bimatrix).
우위전략 I s,, I, s I (dominant strategy).,. 2.
우위전략 ( 계속 ) LG ` HD-DVD '. HD-DVD 150, 50..,. S B H? B L 75 50 75 150 150 25 50 25 H
우위전략 ( 계속 ), LG HD-DVD.? L B H HD- B 45 50 DVD LG 40%, LG S H 105 150 110 35 90 15 40%.
우위전략 ( 계속 ) - A B.., 5,., 2. A B., 5., (plea bargain) 1, 10.? B A -5-10 -5-1 -1-2 -10-2
i v i. (,.) 우위전략 ( 계속 ) Vickrey auction -,..,. i v i, p i, v i - p i.,..,.
내쉬균형 2, I II, (s,t) (Nash equilibrium). I s, t II. II t, s I..,,..,.
내쉬균형 ( 계속 ) (battle of sexes) -..,.,,.? 1-2 0-2 -1 0-1 1
내쉬균형 ( 계속 ) - (hawk-dove game) -. (hawk).,. -100., (dove).., -10. I 1/2., 50, 0. II 15 50 15 0 0-25 50-25
라우팅게임 - (s, t) s-t. ( selfish routing,,.),. (,,.).,. (routing game).
라우팅게임 - 연속흐름모형,. ( 15 1 700.),.. (-1000) (-500) (1000) (500)
라우팅게임 - 연속흐름모형 ( 계속 ) -, s i -t i,i = 1,..., m ( - 3, - ), r i (r 1 =1000, r 2 =500). s i -t i P i (P 1 ={P,Q}, P 2 ={R,S}), r i P P i f P. e f e = P e f P. : f (, ) = f P +f R. c e (f e ) P c P = e P c e (f e ).
라우팅게임 - 연속흐름모형 ( 계속 ) (Pigout) - s t r = 1. s-t, P, Q,, f, c P (f) =1, c Q (f)=f.,,. P c P (f)=1 s t Q c Q (f)=f
라우팅게임 - 연속흐름모형 ( 계속 ) ( )-. x, 1-x+x 2, x* =1/2 3/4. P c P (f)=1 1/2 s t Q c Q (f)=f 1/2?
라우팅게임 - 연속흐름모형 ( 계속 ). (People route selfishly.),,... P c P (1/2)=1 s t Q c Q (1/2)=1/2 (Public transport).
라우팅게임 - 연속흐름모형 ( 계속 ) - f. i = 1,..., m, s i -t i P,Q P i : f P >0 c P (f) c Q (f). x<1.. P c P (0)=1 0 s t Q c Q (1)=1 1 x=1, 1. (Price of anarchy)= / -
라우팅게임 - 연속흐름모형 ( 계속 ) (Braess s paradox)-. P, Q, 1/2. 3/2. u v 0. R P, Q, R 1. R 2, 2..
순수전략과혼합전략 (pure strategy).... (mixed strategy).
순수전략과혼합전략 ( 계속 ) -,,,.. (mixed strategy)...,, (pure strategy). -1. R L R L 1-1 -1 1-1 1 1-1
순수전략과혼합전략 ( 계속 ) ( )- x 1-x. x L 1-x R L 1-1 -1 1-1 1 1-1 R, 2x-1, -2x+1., x=0.5,,.. (, x=0.5..)
순수전략과혼합전략 ( 계속 ) ( )-.. x y. y 1 0 1 x
순수전략과혼합전략 ( 계속 ) (evolutionary stable strategy)- -. (species).. (1),.? (2). (3)? ( : -.) (4)* (3),., p*, p* p*, p p*, p.
순차적게임..,.,,.,..,,.
순차적게임 ( 계속 ) (tic-tac-toe)- 2., 3x3.,,..
( ) 순차적게임 ( 계속 )
순차적게임 ( 계속 ) -,.,..,. ( (subgame). )
-,,.. A : (a,d,e,f,g), (b,d,e,f,g), (c,d,e,f,g) B : (u,w,y), (u,w,z), (u,x,y), (u,x,z), (v,w,y), (v,w,z), (v,x,y), (v,x,z) 순차적게임 ( 계속 )
순차적게임 ( 계속 ) (backward induction)-...,.. (subgame perfect equilibrium)..
순차적게임 (계속) 역귀납법 (계속) - 종료 직전 A가 수 를 쓰는 마디들을 보자. 모두 대안이 유일하기 때문에 그 대안이 최적이다. 발생하는 성과를 마디에 표시한다. 왼쪽 마디를 예로보자. A가 승리하 는 u보다, 무승부가 되는 v가 최선이 다. u를 자르고, v를 굵게 표시하고 해당 성과를 표시한다. u= 무 v d 승 e 무 f 무 g 무 이제, B가 수를 쓰는 시점인 두번째 단계 마디 분석이 가능하다. w 패 =x y 패 =z
순차적게임 ( 계속 ) ( ) -. A a, b, c, a, b, c, a b,c.. : ((a,d,e,f,g), (v,w,y)).. a = b = c (subgame perfect u v. w x y z d e f g
순차적게임 ( 계속 ) ( ) -. A a, b, c, a, b, c, a b,c.. : ((a,d,e,f,g), (v,w,y)).. (subgame perfect). u a = b = c v w x y z d e f g. (.)
순차적게임 ( 계속 ) - I. II.. I, II.,., I.
순차적게임 ( 계속 ) - I, II. I II 1 0 1-1 2 2 0 0. {(, ), (, )}..
순차적게임 ( 계속 ) (platform) -.... 0, 1, [0,1]. 0 1.? 3 3?
순차적게임 ( 계속 ) (centipede) -,.,..?.