博弈论 复旦大学 王永钦.pptx

《博弈论 复旦大学 王永钦.pptx》由会员分享，可在线阅读，更多相关《博弈论 复旦大学 王永钦.pptx（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Fall,2007,Fudan University 1Outline of Static Games of Complete Information Introduction to gamesNormal-form(or strategic-form)representation Iterated elimination of strictly dominated strategies Nash equilibriumApplications of Nash equilibrium Mixed strategy Nash equilibrium第1页/共96页Fall,2007,Fudan

2、University 2AgendaWhat is game theoryExamplesPrisoners dilemmaThe battle of the sexesMatching penniesStatic(or simultaneous-move)games of complete informationNormal-form or strategic-form representation第2页/共96页Fall,2007,Fudan University 3What is game theory?We focus on games where:There are at least

3、 two rational playersEach player has more than one choicesThe outcome depends on the strategies chosen by all players;there is strategic interactionStrategic externalityExample:Six people go to a restaurant.Each person pays his/her own meal a simple decision problemBefore the meal,every person agree

4、s to split the bill evenly among them a game第3页/共96页Fall,2007,Fudan University 4What is game theory?Game theory is a formal way to analyze strategic interaction among a group of rational players(or agents)Game theory has applicationsEconomics/Politics/Sociology/Law/Biology The“double helix”and unify

5、ing tool for social scientists第4页/共96页Fall,2007,Fudan University 5Classic Example:Prisoners DilemmaTwo suspects held in separate cells are charged with a major crime.However,there is not enough evidence.Both suspects are told the following policy:If neither confesses then both will be convicted of a

6、 minor offense and sentenced to one month in jail.If both confess then both will be sentenced to jail for six months.If one confesses but the other does not,then the confessor will be released but the other will be sentenced to jail for nine months.-1,-1-9,0 0,-9-6,-6Prisoner 1Prisoner 2ConfessMumCo

7、nfessMum第5页/共96页Fall,2007,Fudan University 6Classic Example:Prisoners DilemmaThe meaning of symmetry Single population dynamicsEvolutionary game theorySmith(1982)第6页/共96页Fall,2007,Fudan University 7Example:The battle of the sexesAt the separate workplaces,Chris and Pat must choose to attend either a

8、n opera or a prize fight in the evening.Both Chris and Pat know the following:Both would like to spend the evening together.But Chris prefers the opera.Pat prefers the prize fight.2,1 0,0 0,0 1,2ChrisPatPrize FightOperaPrize FightOpera第7页/共96页Fall,2007,Fudan University 8Example:Matching penniesEach

9、of the two players has a penny.Two players must simultaneously choose whether to show the Head or the Tail.Both players know the following rules:If two pennies match(both heads or both tails)then player 2 wins player 1s penny.Otherwise,player 1 wins player 2s penny.-1,1 1,-1 1,-1-1,1Player 1Player 2

10、TailHeadTailHead第8页/共96页Fall,2007,Fudan University 9Static(or simultaneous-move)games of complete informationA set of players(at least two players)For each player,a set of strategies/actionsPayoffs received by each player for the combinations of the strategies,or for each player,preferences over the

11、 combinations of the strategiesPlayer 1,Player 2,.Player nS1 S2 .Snui(s1,s2,.sn),for all s1 S1,s2 S2,.sn Sn.A static(or simultaneous-move)game consists of:第9页/共96页Fall,2007,Fudan University 10Static(or simultaneous-move)games of complete informationSimultaneous-moveEach player chooses his/her strate

12、gy without knowledge of others choices.Complete information(on games structure)Each players strategies and payoff function are common knowledge among all the players.Assumptions on the playersRationalityPlayers aim to maximize their payoffsPlayers are perfect calculatorsEach player knows that other

13、players are rational第10页/共96页Fall,2007,Fudan University 11Static(or simultaneous-move)games of complete informationThe players cooperate?No.Only non-cooperative games Methodological individualismThe timingEach player i chooses his/her strategy si without knowledge of others choices.Then each player

14、i receives his/her payoff ui(s1,s2,.,sn).The game ends.第11页/共96页Fall,2007,Fudan University 12Definition:normal-form or strategic-form representationThe normal-form(or strategic-form)representation of a game G specifies:A finite set of players 1,2,.,n,players strategy spaces S1 S2 .Sn andtheir payoff

15、 functions u1 u2 .un where ui:S1 S2 .SnR.第12页/共96页Fall,2007,Fudan University 13Normal-form representation:2-player gameBi-matrix representation2 players:Player 1 and Player 2Each player has a finite number of strategiesExample:S1=s11,s12,s13 S2=s21,s22Player 2s21s22Player 1s11u1(s11,s21),u2(s11,s21)

16、u1(s11,s22),u2(s11,s22)s12u1(s12,s21),u2(s12,s21)u1(s12,s22),u2(s12,s22)s13u1(s13,s21),u2(s13,s21)u1(s13,s22),u2(s13,s22)第13页/共96页Fall,2007,Fudan University 14Classic example:Prisoners Dilemma:normal-form representationSet of players:Prisoner 1,Prisoner 2Sets of strategies:S1=S2=Mum,ConfessPayoff fu

17、nctions:u1(M,M)=-1,u1(M,C)=-9,u1(C,M)=0,u1(C,C)=-6;u2(M,M)=-1,u2(M,C)=0,u2(C,M)=-9,u2(C,C)=-6-1,-1-9,0 0,-9-6,-6Prisoner 1Prisoner 2ConfessMumConfessMumPlayersStrategiesPayoffs第14页/共96页Fall,2007,Fudan University 15Example:The battle of the sexesNormal(or strategic)form representation:Set of players:

18、Chris,Pat (=Player 1,Player 2)Sets of strategies:S1=S2=Opera,Prize FightPayoff functions:u1(O,O)=2,u1(O,F)=0,u1(F,O)=0,u1(F,O)=1;u2(O,O)=1,u2(O,F)=0,u2(F,O)=0,u2(F,F)=2 2,1 0,0 0,0 1,2ChrisPatPrize FightOperaPrize FightOpera第15页/共96页Fall,2007,Fudan University 16Example:Matching penniesNormal(or stra

19、tegic)form representation:Set of players:Player 1,Player 2Sets of strategies:S1=S2=Head,Tail Payoff functions:u1(H,H)=-1,u1(H,T)=1,u1(T,H)=1,u1(H,T)=-1;u2(H,H)=1,u2(H,T)=-1,u2(T,H)=-1,u2(T,T)=1-1,1 1,-1 1,-1-1,1Player 1Player 2TailHeadTailHead第16页/共96页Fall,2007,Fudan University 17Example:Tourists&Na

20、tivesOnly two bars(bar 1,bar 2)in a cityCan charge price of$2,$4,or$56000 tourists pick a bar randomly4000 natives select the lowest price barExample 1:Both charge$2each gets 5,000 customers and$10,000Example 2:Bar 1 charges$4,Bar 2 charges$5Bar 1 gets 3000+4000=7,000 customers and$28,000Bar 2 gets

21、3000 customers and$15,000第17页/共96页Fall,2007,Fudan University 18Example:Cournot model of duopolyA product is produced by only two firms:firm 1 and firm 2.The quantities are denoted by q1 and q2,respectively.Each firm chooses the quantity without knowing the other firm has chosen.The market price is P

22、(Q)=a-Q,where Q=q1+q2.The cost to firm i of producing quantity qi is Ci(qi)=cqi.The normal-form representation:Set of players:Firm 1,Firm 2Sets of strategies:S1=0,+),S2=0,+)Payoff functions:u1(q1,q2)=q1(a-(q1+q2)-c),u2(q1,q2)=q2(a-(q1+q2)-c)第18页/共96页Fall,2007,Fudan University 19One More ExampleEach

23、of n players selects a number between 0 and 100 simultaneously.Let xi denote the number selected by player i.Let y denote the average of these numbersPlayer is payoff=xi 3y/5The normal-form representation:第19页/共96页Fall,2007,Fudan University 20Solving Prisoners DilemmaConfess always does better whate

24、ver the other player choosesDominated strategyThere exists another strategy which always does better regardless of other players choices-1,-1-9,0 0,-9-6,-6Prisoner 1Prisoner 2ConfessMumConfessMumPlayersStrategiesPayoffs第20页/共96页Fall,2007,Fudan University 21Definition:strictly dominated strategy-1,-1

25、-9,0 0,-9-6,-6Prisoner 1Prisoner 2ConfessMumConfessMumregardless of other players choicessi”is strictly better than si第21页/共96页Fall,2007,Fudan University 22ExampleTwo firms,Reynolds and Philip,share some marketEach firm earns$60 million from its customers if neither do advertisingAdvertising costs a

26、 firm$20 millionAdvertising captures$30 million from competitorPhilipNo AdAdReynoldsNo Ad60,6030,70Ad70,3040,40第22页/共96页Fall,2007,Fudan University 232-player game with finite strategiesS1=s11,s12,s13 S2=s21,s22s11 is strictly dominated by s12 if u1(s11,s21)u1(s12,s21)and u1(s11,s22)u1(s12,s22).s21 i

27、s strictly dominated by s22 if u2(s1i,s21)u2(s1i,s22),for i=1,2,3Player 2s21s22Player 1s11u1(s11,s21),u2(s11,s21)u1(s11,s22),u2(s11,s22)s12u1(s12,s21),u2(s12,s21)u1(s12,s22),u2(s12,s22)s13u1(s13,s21),u2(s13,s21)u1(s13,s22),u2(s13,s22)第23页/共96页Fall,2007,Fudan University 24Definition:weakly dominated

28、strategy 1,1 2,0 0,2 2,2Player 1Player 2RUBLregardless of other players choicessi”is at least as good as si第24页/共96页Fall,2007,Fudan University 25Strictly and weakly dominated strategyA rational player never chooses a strictly dominated strategy.Hence,any strictly dominated strategy can be eliminated

29、.A rational player may choose a weakly dominated strategy.The order of elimination does not matter for strict dominance elimination(pin down the same equilibrium),but does for weak one.第25页/共96页Fall,2007,Fudan University 26Iterated elimination of strictly dominated strategiesIf a strategy is strictl

30、y dominated,eliminate itThe size and complexity of the game is reducedEliminate any strictly dominated strategies from the reduced gameContinue doing so successivelyRationalizable equilibrium第26页/共96页Fall,2007,Fudan University 27Iterated elimination of strictly dominated strategies:an example 1,0 1,

31、2 0,1 0,3 0,1 2,0Player 1Player 2MiddleUpDownLeft 1,0 1,2 0,3 0,1Player 1Player 2MiddleUpDownLeftRight第27页/共96页Fall,2007,Fudan University 28Example:Tourists&NativesOnly two bars(bar 1,bar 2)in a cityCan charge price of$2,$4,or$56000 tourists pick a bar randomly4000 natives select the lowest price ba

32、rExample 1:Both charge$2each gets 5,000 customers and$10,000Example 2:Bar 1 charges$4,Bar 2 charges$5Bar 1 gets 3000+4000=7,000 customers and$28,000Bar 2 gets 3000 customers and$15,000第28页/共96页Fall,2007,Fudan University 29Example:Tourists&NativesBar 2$2$4$5Bar 1$210,1014,1214,15$412,1420,2028,15$515

33、,1415,2825,25Payoffs are in thousands of dollarsBar 2$4$5Bar 1$420,2028,15$515,2825,25第29页/共96页Fall,2007,Fudan University 30Example:Tourists&NativesInefficiency again as in Prisoners dilemmaSome games have no rationalizable equilbrium(co-ordination games)Strategic ambiguity第30页/共96页Fall,2007,Fudan U

34、niversity 31One More ExampleEach of n players selects a number between 0 and 100 simultaneously.Let xi denote the number selected by player i.Let y denote the average of these numbersPlayer is payoff=xi 3y/5第31页/共96页Fall,2007,Fudan University 32One More ExampleThe normal-form representation:Players:

35、player 1,player 2,.,player nStrategies:Si=0,100,for i=1,2,.,n.Payoff functions:ui(x1,x2,.,xn)=xi 3y/5Is there any dominated strategy?What numbers should be selected?What if ui(x1,x2,.,xn)=xi 6y/5第32页/共96页Fall,2007,Fudan University 33New solution concept:Nash equilibriumPlayer 2LCRPlayer 1T0,44,05,3M

36、4,00,45,3B3,53,56,6The combination of strategies(B,R)has the following property:Player 1 CANNOT do better by choosing a strategy different from B,given that player 2 chooses R.Player 2 CANNOT do better by choosing a strategy different from R,given that player 1 chooses B.第33页/共96页Fall,2007,Fudan Uni

37、versity 34New solution concept:Nash equilibriumPlayer 2LCRPlayer 1T0,44,03,3M4,00,43,3B3,33,33.5,3.6The combination of strategies(B,R)has the following property:Player 1 CANNOT do better by choosing a strategy different from B,given that player 2 chooses R.Player 2 CANNOT do better by choosing a str

38、ategy different from R,given that player 1 chooses B.第34页/共96页Fall,2007,Fudan University 35Nash Equilibrium:ideaNash equilibriumA set of strategies,one for each player,such that each players strategy is best for her,given that all other players are playing their equilibrium strategiesTwo interpretat

39、ions of Nash EquilibriumProbability based onePopulation based oneSymmetric gamesAsymmetric games第35页/共96页Fall,2007,Fudan University 36Definition:Nash EquilibriumGiven others choices,player i cannot be better-off if she deviates from si*(cf:dominated strategy)Prisoner 2MumConfessPrisoner 1Mum-1,-1-9,

40、0Confess 0,-9-6,-6第36页/共96页Fall,2007,Fudan University 372-player game with finite strategiesS1=s11,s12,s13 S2=s21,s22(s11,s21)is a Nash equilibrium if u1(s11,s21)u1(s12,s21),u1(s11,s21)u1(s13,s21)andu2(s11,s21)u2(s11,s22).Player 2s21s22Player 1s11u1(s11,s21),u2(s11,s21)u1(s11,s22),u2(s11,s22)s12u1(s

41、12,s21),u2(s12,s21)u1(s12,s22),u2(s12,s22)s13u1(s13,s21),u2(s13,s21)u1(s13,s22),u2(s13,s22)第37页/共96页Fall,2007,Fudan University 38Finding a Nash equilibrium:cell-by-cell inspection 1,0 1,2 0,1 0,3 0,1 2,0Player 1Player 2MiddleUpDownLeft 1,0 1,2 0,3 0,1Player 1Player 2MiddleUpDownLeftRight第38页/共96页Fal

42、l,2007,Fudan University 39Example:Tourists&NativesBar 2$2$4$5Bar 1$210,1014,1214,15$412,1420,2028,15$515,1415,2825,25Payoffs are in thousands of dollarsBar 2$4$5Bar 1$420,2028,15$515,2825,25第39页/共96页Fall,2007,Fudan University 40One More ExampleThe normal-form representation:Players:player 1,player 2

43、,.,player nStrategies:Si=0,100,for i=1,2,.,n.Payoff functions:ui(x1,x2,.,xn)=xi 3y/5What is the Nash equilibrium?第40页/共96页Fall,2007,Fudan University 41Best response function:exampleIf Player 2 chooses L then Player 1s best strategy is MIf Player 2 chooses C then Player 1s best strategy is TIf Player

44、 2 chooses R then Player 1s best strategy is BIf Player 1 chooses B then Player 2s best strategy is RBest response:the best strategy one player can play,given the strategies chosen by all other playersPlayer 2LCRPlayer 1T0,44,03,3M4,00,43,3B3,33,33.5,3.6第41页/共96页Fall,2007,Fudan University 42Example:

45、Tourists&Nativeswhat is Bar 1s best response to Bar 2s strategy of$2,$4 or$5?what is Bar 2s best response to Bar 1s strategy of$2,$4 or$5?Bar 2$2$4$5Bar 1$210,1014,1214,15$412,1420,2028,15$515,1415,2825,25Payoffs are in thousands of dollars第42页/共96页Fall,2007,Fudan University 432-player game with fin

46、ite strategiesS1=s11,s12,s13 S2=s21,s22Player 1s strategy s11 is her best response to Player 2s strategy s21 if u1(s11,s21)u1(s12,s21)andu1(s11,s21)u1(s13,s21).Player 2s21s22Player 1s11u1(s11,s21),u2(s11,s21)u1(s11,s22),u2(s11,s22)s12u1(s12,s21),u2(s12,s21)u1(s12,s22),u2(s12,s22)s13u1(s13,s21),u2(s1

47、3,s21)u1(s13,s22),u2(s13,s22)第43页/共96页Fall,2007,Fudan University 44Using best response function to find Nash equilibriumIn a 2-player game,(s1,s2)is a Nash equilibrium if and only if player 1s strategy s1 is her best response to player 2s strategy s2,and player 2s strategy s2 is her best response to

48、 player 1s strategy s1.-1,-1-9,0 0,-9-6,-6Prisoner 1Prisoner 2ConfessMumConfessMum第44页/共96页Fall,2007,Fudan University 45Using best response function to find Nash equilibrium:exampleM is Player 1s best response to Player 2s strategy L T is Player 1s best response to Player 2s strategy C B is Player 1

49、s best response to Player 2s strategy R L is Player 2s best response to Player 1s strategy TC is Player 2s best response to Player 1s strategy M R is Player 2s best response to Player 1s strategy BPlayer 2LCRPlayer 1T0,44,03,3M4,00,43,3B3,33,33.5,3.6第45页/共96页Fall,2007,Fudan University 46Example:Tour

50、ists&NativesBar 2$2$4$5Bar 1$210,1014,1214,15$412,1420,2028,15$515,1415,2825,25Payoffs are in thousands of dollarsUse best response function to find the Nash equilibrium.第46页/共96页Fall,2007,Fudan University 47Example:The battle of the sexesOpera is Player 1s best response to Player 2s strategy OperaO