《Ch15 Game Theory.ppt》由会员分享，可在线阅读，更多相关《Ch15 Game Theory.ppt（94页珍藏版）》请在三一办公上搜索。
1、Chapter Twenty-Eight,Game Theory博弈论,Game Theory,Game theory models strategic behavior by agents who understand that their actions affect the actions of other agents.,什么是博弈呢？博弈是指在一定的游戏规则约束下，基于直接相互作用的环境条件，各参与人依靠所掌握的信息，选择各自策略（行动），以实现利益最大化和风险成本最小化的过程。简单说就是人与人之间为了谋取利益而竞争。我们平时生活中接触到的打牌，买彩票以及各种赌博，都是属于博弈的范畴
2、的。在当今世界，博弈已经用于身边的各个方面了。,他叫做约翰-纳什：约翰纳什生于1928年6月13日。父亲是电子工程师与教师，第一次世界大战的老兵。纳什小时孤独内向，虽然父母对他照顾有加，但老师认为他不合群不善社交。纳什的数学天分大约在14岁开始展现。他在普林斯顿大学读博士时刚刚二十出头，但他的一篇关于非合作博弈的博士论文和其他相关文章，确立了他博弈论大师的地位。在20世纪50年代末，他已是闻名世界的科学家了。然而，正当他的事业如日中天的时候，30岁的纳什得了严重的精神分裂症。他的妻子艾利西亚麻省理工学院物理系毕业生，表现出钢铁一般的意志：她挺过了丈夫被禁闭治疗、孤立无援的日子，走过了惟一儿子同
3、样罹患精神分裂症的震惊与哀伤漫长的半个世纪之后，她的耐心和毅力终于创下了了不起的奇迹：和她的儿子一样，纳什教授渐渐康复，并在1994年获得诺贝尔奖经济学奖。,If he and his friends all hit on the same woman,Nash reasons,theyll devastate one anothers chances while letting other,slightly less desirable,women get away.Adam Smith needs revision!he declares triumphantly.To his baffl
4、ed classmates,he explains:Adam Smith said the best result comes from everyone in the group doing whats best for himself,right?Adam Smith was wrong!The message:Sometimes its better to cooperate!,亚当斯密在1776年发表的经典之作原富中认为：我们的晚餐不是来自屠夫、酿酒的商人或面包师傅的仁慈之心，而是因为他们对自己的利益特别关注。每个人都会尽其所能，运用自己的资本争取最大的利益，一般而言，他不会有意图为公
5、众服务，也不自知对社会有什么贡献，他关心的仅仅是自己的安全、自己的利益，但如此一来，他就好象被一只无形的手引领，在不知不觉中对社会改进尽力而为。,约翰-纳什提出的是这样一个问题：,Some Applications of Game Theory,The study of oligopolies(industries containing only a few firms)The study of cartels;e.g.OPECThe study of externalities;e.g.using a common resource such as a fishery.The study o
6、f military strategies.,纳什均衡,假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己效用最大化。所有局中人策略构成一个策略组合（Strategy Profile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。,纳什均衡应用举例,诺贝尔经济学奖获得者萨缪尔森有一句话：你可以将一只鹦鹉训练成一个经济学家，因为它只需要学习两个词：供给和需求。博弈论专家坎多瑞引申说：要成为现代经济学家，这只鹦鹉必须再多学一个词
7、，就是“纳什均衡”。,What is a Game?,A game consists ofa set of playersa set of strategies for each playerthe payoffs to each player for every possible list of strategy choices by the players.,Two-Player Games,A game with just two players is a two-player game.We will study only games in which there are two pl
8、ayers,each of whom can choose between only two strategies.,An Example of a Two-Player Game,The players are called A and B.Player A has two strategies,called“Up”and“Down”.Player B has two strategies,called“Left”and“Right”.The table showing the payoffs to both players for each of the four possible str
9、ategy combinations is the games payoff matrix(收益矩阵).,An Example of a Two-Player Game,A play of the game is a pair such as(U,R)where the 1st element is the strategychosen by Player A and the 2nd is the strategy chosen by Player B.,An Example of a Two-Player Game,What plays are we likely to see for th
10、isgame?,An Example of a Two-Player Game,If B plays Left then As best reply is Down.,An Example of a Two-Player Game,If B plays Right then As best reply is Down.,An Example of a Two-Player Game,So no matter what B plays,Asbest reply is always Down.Down is As dominant strategy 占优策略,An Example of a Two
11、-Player Game,Similarly,Left is Bs dominant strategy.,An Example of a Two-Player Game,Therefore,(Down,Left)is dominant strategyfor both players.It is the only equilibrium.,Dominant Strategy for Both,When Strength Is Weakness(当力量成为弱势时),No Dominant Strategy for Both,The Battle of Sexes（性别战）,Nash Equili
12、brium,A play of the game where each strategy is a best reply to the other is a Nash equilibrium.A dominant strategy equilibrium is a Nash equilibrium;In the“strength is weakness”example,(W,P)is a Nash equilibrium.In the“battle of sexes”example,there are two Nash equilibria.,The Prisoners Dilemma,A N
13、ash equilibrium may not be Pareto optimal/efficient.Consider a famous second example of a two-player game called the Prisoners Dilemma（囚徒困境）.,The Prisoners Dilemma,What plays are we likely to see for thisgame?,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10,-10),S,C,S,C,The Prisoners Dilemma,If Bonnie p
14、lays Silence then Clydes bestreply is Confess.,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10,-10),S,C,S,C,The Prisoners Dilemma,If Bonnie plays Silence then Clydes bestreply is Confess.If Bonnie plays Confess then Clydesbest reply is Confess.,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10,-10),S,C,S,C,Th
15、e Prisoners Dilemma,So no matter what Bonnie plays,Clydesbest reply is always Confess.Confess is a dominant strategy for Clyde.,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10,-10),S,C,S,C,The Prisoners Dilemma,Similarly,no matter what Clyde plays,Bonnies best reply is always Confess.Confess is a domina
16、nt strategy forBonnie also.,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10,-10),S,C,S,C,The Prisoners Dilemma,So the only Nash equilibrium for thisgame is(C,C),even though(S,S)givesboth Bonnie and Clyde better payoffs.The only Nash equilibrium is inefficient.,Clyde,Bonnie,(-5,-5),(-30,-1),(-1,-30),(-10
17、,-10),S,C,S,C,Other Examples of Prisoners Dilemma,Cheating in a Cartel.Price competition.Military competition in the cold war.,How to Avoid Prisoners Dilemma,Repeated gamesBinding contract,Multiple Equilibria,Chicken game（逗鸡博弈）,Youth 2,Youth 1,Swerve,Straight,Swerve,(0,0),(1,-1),(-1,1),(-2,-2),Strai
18、ght,Multiple Equilibria,Chicken game（逗鸡博弈）,Youth 2,Youth 1,Swerve,Straight,Swerve,(0,0),(1,-1),(-1,1),(-2,-2),Straight,Multiple Equilibria,Sometimes a game has more than one Nash equilibrium and it is hard to say which is more likely to occur.Solutions:CoordinationStrategic behavior;establish reputa
19、tionSequential moves,A Sequential Game Example,When such a game is sequential it is sometimes possible to argue that one of the Nash equilibria is more likely to occur than the other.,A Sequential Game Example,Incumbent,Entrant,(Enter,dont fight)and(stay out,fight)are both Nash equilibria when this
20、game is played simultaneouslyand we have no way of deciding whichequilibrium is more likely to occur.,Fight,Dont fight,Enter,Stay out,(1,9),(0,0),(1,8),(2,1),Suppose instead that the game is playedsequentially,with incumbent leading and entrant following.We can rewrite the game in its extensive form
21、.,A Sequential Game Example,Incumbent,Entrant,Fight,Dont fight,Enter,Stay out,(1,9),(0,0),(1,8),(2,1),A Sequential Game Example,Fight,Dont fight,Enter,Stay out,(1,9),(1,8),(0,0),(2,1),Entrant,Incumbent,Incumbent,Dont fight,Fight,(Stay out,Fight)is a Nash equilibrium.,A Sequential Game Example,Fight,
22、Dont fight,Enter,Stay out,(1,9),(1,8),(0,0),(2,1),Entrant,Incumbent,Incumbent,Dont fight,Fight,(Stay out,Fight)is a Nash equilibrium.(Enter,Dont Fight)is a Nash equilibrium.Which is more likely to occur?,The entrant prefers(Enter,Dont Fight),but the incumbent may threat to fight.Is the threat credib
23、le?Can make it credible.,A Sequential Game Example,A Sequential Game Example,Fight,Dont fight,Enter,Stay out,(1,9),(1,8),(0,2),(2,1),Entrant,Incumbent,Incumbent,Dont fight,Fight,By building up excess capacity,the threat becomes credible.The potential entrant stays out.,Pure Strategies,In all previou
24、s examples,players are thought of as choosing to play either one or the other,but no combination ofboth;that is,as playing purely one or the other.The strategies presented so far are players pure strategies（纯粹策略）.Consequently,equilibria are pure strategy Nash equilibria.Must every game have at least
25、 one pure strategy Nash equilibrium?,Pure Strategies,Player B,Player A,Here is a new game.Are there any purestrategy Nash equilibria?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Pure Strategies,Player B,Player A,Is(U,L)a Nash equilibrium?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Pure Strategies,Player B,Player A,Is(U,L)
26、a Nash equilibrium?No.Is(U,R)a Nash equilibrium?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Pure Strategies,Player B,Player A,Is(U,L)a Nash equilibrium?No.Is(U,R)a Nash equilibrium?No.Is(D,L)a Nash equilibrium?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Pure Strategies,Player B,Player A,Is(U,L)a Nash equilibrium?No.Is(U,
27、R)a Nash equilibrium?No.Is(D,L)a Nash equilibrium?No.Is(D,R)a Nash equilibrium?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Pure Strategies,Player B,Player A,Is(U,L)a Nash equilibrium?No.Is(U,R)a Nash equilibrium?No.Is(D,L)a Nash equilibrium?No.Is(D,R)a Nash equilibrium?No.,(1,2),(0,4),(0,5),(3,2),U,D,L,R,More
28、Examples,Matching Pennies,Player B,Player A,(1,-1),(-1,1),(-1,1),(1,-1),H,T,H,T,More Examples,点球,进攻球员,守门员,(1,0),(0,1),(0,1),(1,0),左,右,左,右,Pure Strategies,Player B,Player A,So the game has no Nash equilibria in purestrategies.Even so,the game does have aNash equilibrium,but in mixed strategies(混合策略).
29、,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Mixed Strategies,Instead of playing purely Up or Down,Player A selects a probability distribution(pU,1-pU),meaning that with probability pU Player A will play Up and with probability 1-pU will play Down.Player A is mixing over the pure strategies Up and Down.The prob
30、ability distribution(pU,1-pU)is a mixed strategy for Player A.,Mixed Strategies,Similarly,Player B selects a probability distribution(pL,1-pL),meaning that with probability pL Player B will play Left and with probability 1-pL will play Right.Player B is mixing over the pure strategies Left and Right
31、.The probability distribution(pL,1-pL)is a mixed strategy for Player B.,Mixed Strategies,Player A,This game has no pure strategy Nash equilibria but it does have a Nash equilibrium in mixed strategies.How is itcomputed?,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Player B,Mixed Strategies,Player A,(1,2),(0,4),(
32、0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,If B plays Left her expected payoff is,(1,2),(0,4),(0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,If B plays Left her expected payoff isIf B plays Right her expected payoff is,(1,2),(0,4),(0,5),(3,2),U,pU,D
33、,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,If,then,B would play only Left.But there are noNash equilibria in which B plays only Left.,(1,2),(0,4),(0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,If,then,B would play only Right.But there are noNash equilibria in which
34、B plays only Right.,(1,2),(0,4),(0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,So for there to exist a Nash equilibrium,Bmust be indifferent between playing Left orRight;i.e.,(1,2),(0,4),(0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,So for there to ex
35、ist a Nash equilibrium,Bmust be indifferent between playing Left orRight;i.e.,(1,2),(0,4),(0,5),(3,2),U,pU,D,1-pU,L,pL,R,1-pL,Player B,Mixed Strategies,Player A,So for there to exist a Nash equilibrium,Bmust be indifferent between playing Left orRight;i.e.,(1,2),(0,4),(0,5),(3,2),U,D,L,pL,R,1-pL,Pla
36、yer B,Mixed Strategies,Player A,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,If A plays Up his expected payoff is,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,If A plays Up his expected payoff isIf A plays Down his expected payoff is,(1,2),
37、(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,If,then A would play only Up.,But there are no Nash equilibria in which Aplays only Up.,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,If,Down.But there are no Nash equilibria inwhich A plays only Down.,
38、then A would play only,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,So for there to exist a Nash equilibrium,Amust be indifferent between playing Up orDown;i.e.,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,So for there to exist a Nash equil
39、ibrium,Amust be indifferent between playing Up orDown;i.e.,(1,2),(0,4),(0,5),(3,2),L,pL,R,1-pL,U,D,Player B,Mixed Strategies,Player A,So for there to exist a Nash equilibrium,Amust be indifferent between playing Up orDown;i.e.,(1,2),(0,4),(0,5),(3,2),L,R,U,D,Player B,Mixed Strategies,Player B,Player
40、 A,So the games only Nash equilibrium has Aplaying the mixed strategy(3/5,2/5)and hasB playing the mixed strategy(3/4,1/4).,(1,2),(0,4),(0,5),(3,2),U,D,L,R,Mixed Strategies,Player B,Player A,The payoffs will be(1,2)with probability,(1,2),(0,4),(0,5),(3,2),U,D,L,R,9/20,Mixed Strategies,Player B,Playe
41、r A,The payoffs will be(0,4)with probability,(0,4),(0,5),(3,2),U,D,L,R,(1,2),9/20,3/20,Mixed Strategies,Player B,Player A,The payoffs will be(0,5)with probability,(0,4),(0,5),U,D,L,R,(1,2),9/20,3/20,6/20,(3,2),Mixed Strategies,Player B,Player A,The payoffs will be(3,2)with probability,(0,4),U,D,L,R,
42、(1,2),9/20,3/20,(0,5),(3,2),6/20,2/20,Mixed Strategies,Player B,Player A,As expected Nash equilibrium payoff is,Bs expected Nash equilibrium payoff is,(0,4),U,D,L,R,(1,2),9/20,3/20,(0,5),(3,2),6/20,2/20,Mixed Strategies,For games with multiple pure strategies,there also exists mixed strategies.Examp
43、le:Chicken game.The probability that each player plays straight is.,How Many Nash Equilibria?,A game can have both pure strategy Nash equilibrium and mixed strategy Nash equilibrium.if the game has no pure strategy Nash equilibrium then it must have at least one mixed strategy Nash equilibrium.,Cont
44、ents,Dominant strategyNash equilibriumPrisoners dilemma and repeated gamesMultiple equilibria and sequential gamesPure and mixed strategies,人生处处皆博弈,囚徒A,囚徒 B,坦白,抵赖,坦白,抵赖,行动,完全信息静态博弈纳什均衡纳什（1950，1951）,囚徒困境,人生处处皆博弈-智猪博弈,等待,小猪,大猪,按,等待,按,4大于10大于-1,智猪博弈,行动,囚徒困境,完全信息静态博弈纳什均衡纳什（1950，1951）,完全信息动态博弈-子博弈精练纳什均衡（
45、举例）泽尔腾（1965）,进入者,进入,不进入（0，300）,在位者,合作（40，50）,斗争（-10，0）,市场进入阻挠博弈树,特点：剔除博弈中包含的不可置信威胁；承诺行动-破釜沉舟给定进入者进入，剔除（进入，斗争），（进入，默许）是唯一的子博弈精练纳什均衡-举例（结婚-反对）,不可置信威胁,行动,房地产开发中需求小情况,不开发,开发商A,开发,不开发,开发,不开发,开发商B,开发商A,开发,不开发,开发,开发商B,需求小的情况,需求大的情况,博弈的战略式表述,重复剔除的占优均衡,M,列先生,行先生,U,D,L,R,行：没有占优战略列：M严格优于R剔除 R,行：L优于D列：无占优战略剔除 D
46、,M优于L,（U，M）是重复剔除的占优均衡,重复剔除的占优均衡,卑斯麦海之战卑斯麦海之战发生在1943年的南太平洋上，日本海军上将木村受命将日本陆军运抵新几内亚，其间要穿越卑斯麦海。而美国上将肯尼欲对日军运输船进行轰炸，穿越卑斯麦海通往新几内亚的有两条航线，木村必须从中选一条，而肯尼则必须决定将其飞机派往何处去搜索日军，如果肯尼将他的飞机派到了错误的航线上，他虽可以召回他们，但可供轰炸的天数将减少。,木村,肯尼,北,南,北,南,混合战略纳什均衡,社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,没有一个战略组合构成纳什均衡,混合战略纳什均衡,社会福利博弈,流浪,流浪汉,政府,救济,不救
47、济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略,五 混合战略纳什均衡,假定最优混合战略存在，给定流浪汉选择混合战略（r，1-r），政府选择纯战略救济的期望效用为：3r+（-1）（1-r）=4r-1选择纯战略不救济的效用为：-1r+0（1-r）=-r如果一个混合战略（而不是纯战略）是政府的最优选择，一定意味着政府在救济与不救济之间是无差异的。4r-1=-r r=0.2,流浪,流浪汉,政府,救济,不救济,寻找工作,支付等值法,混合战略纳什均衡,社会福利博弈,流浪,流浪汉,政府,救济,
48、不救济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的期望效用：1/22+1/2 1=1.5 流浪的期望效用：1/23+1/2 0=1.5因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应,五 混合战略纳什均衡,反面,正面,反面,正面,猜谜游戏两个小孩的最优策略是采取每个策略的可能性均为1/2；每个小孩各取策略的1/2是纳什均衡。,零和博弈,混合战略纳什均衡,反面,正面,反面,正面,猜谜游戏两个儿童各拿一枚硬币，若同时正面朝上或朝下，A给B 1分钱，若只有一面朝上，B给A 1分钱。,零和博弈博弈参与者有输有赢，但结果永远是0。,没有一个战略组合构成纳什均衡,混合战略纳什均衡,警察与小偷,银行,酒馆,警察,小偷,2万元,1万元,东边,西边,警察与小偷的最优策略各是什么？,西边,东边,西边,东边,混合战略纳什均衡,警察抽签决定去银行还是酒馆，2/3的机会去银行，1/3的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，2/3的机会去酒馆，1/3的机会去银行。,
