博弈论的历史发展课件

1、Game theory and Strategic Thinking: An Introduction杨冠琼北京师范大学公共部门绩效测评研究中心北京师范大学管理学院博弈论与策略性思维导论第1页，共69页。模拟性思考题 Rousseau: Discourse on the Origin and Basis of Equality among Men:If a group of hunters set out to take a stag, they are fully aware that they would all have to remain faithfully at their pos

2、ts in order to succeed; but if a hare happens to pass near one of them, there can be no doubt that he pursued it without qualm, and that once he had caught his prey, he cared very little whether or not he had made his companion miss theirs. 第2页，共69页。0、策略性思维的基本概念（一）策略性思维的意义策略性思维：人类的内在优势策略性思维的两面性策略性思维

3、的不可回避性策略性思维：基本的生活技巧第3页，共69页。0、策略性思维的基本概念（二）策略性博弈实例例一：西班牙叛乱Roman: Pompey and PiusRebellion: Sertorius and Hirtuleius第4页，共69页。0、策略性思维的基本概念实例二：囚徒困境(Prisoners Dilemma)实例三：性别战(the Battle of the Sexes)实例四：鹰鸽博弈(the Hawk and Dove)实例五：猜硬币博弈（Matching pennies）实例六：齐威王田忌赛马实例七：小偷与守卫博弈实例八：智猪博弈第5页，共69页。0、策略性思维的基本概念

4、（三）策略性思维的系统性研究：博弈论的历史发展（四）博弈论的性质博弈论是对理性、智能决策者之间冲突与合作的模型研究，是寻求决策者最佳反应策略的一种理论体系第6页，共69页。0、策略性思维的基本概念（五）博弈论的基本假设个人主义理性智能共同知识第7页，共69页。0、策略性思维的基本概念（六）策略性思维的基本框架决策与博弈博弈的基本类型1、同时行动或序惯行动(are the moves in the game sequential or simultaneous)2、冲突还是合作(are the players interests in total conflict or is there som

5、e commonality)3、一次博弈还重复博弈,参与人是否变化(is the game played once or repeatedly, and with the same or changing opponents)第8页，共69页。0、策略性思维的基本概念博弈的基本类型4、信息是否完备和完全(do the players have full of equal information)5、规则是否可变(are the rules of the game fixed or manipulateable)6、协议是否可实施(Are agreements to cooperate enfo

6、rceable)博弈论的运用解释（Explanation）预测(prediction)建议（Advice or prescription）第9页，共69页。博弈分类（Categories）一、完备信息的同时行动博弈（Static Games of Complete Information ）二、完全信息的序惯行动博弈（Dynamic Games of Complete Information ）三、不完全信息的同时行动博弈（Static Games of Incomplete Information ）四、不完全信息的序惯行动博弈（Dynamic Games of Incomplete Inf

7、ormation ）五、高级专题（Advanced Topics）第10页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium 1.1策略式博弈导论与严格占优Introduction to Games in Strategic Form and Iterated Strict Dominance 1.1.1博弈的策略式(Strategic-Form Games )三要素参与人（players)可选策略(the strategies available to each players)支付(the pay-offs): 第11

8、页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Common knowledgeUsually we also assume that all players know the structure of the strategic form, and know that their opponents know it, and know that their opponents know that they know, and so on ad infinitum. That is, the structure of

9、 the game is common knowledge, a concept examined more formally in chapter 14. This chapter uses common knowledge informally, to motivate the solution concept of Nash equilibrium and iterated strict dominance. As will be seen, common knowledge of payoffs on its own is in fact neither necessary nor s

10、ufficient to justify Nash equilibrium. 第12页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium We focus our attention on finite games, that is, games where is finite; finiteness should be assumed wherever we do not explicitly note otherwise. Strategic forms for finite two-player games are

11、often depicted as matrices, as in figure 1.1. In this matrix, players 1 and 2 have three pure strategies each: U, M, D (up, middle, and down) and L, M, R (left, middle, and right), respectively. The first entry in each box is player 1s payoff for the corresponding strategy profile; the second is pla

12、yer 2s.第13页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Mixed Strategy第14页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Note that player is payoff to a mixed-strategy profile is a linear function of players mixing probability i, a fact which has many important implic

13、ations. Note also that player is payoff is a polynomial function of the strategy profile, and so in particular is continuous. Last, note that the set of mixed strategies contains the pure strategies, as degenerate probability distributions are included. 第15页，共69页。1. 完全信息静态博弈Games in Strategic Form a

14、nd Nash Equilibrium For instance, in figure 1.1 a mixed strategy for player 1 is a vector (1(U), 1(M), 1(D) such that 1(U), 1(M), 1(D) are nonnegative and 1(U)+1(M)+1(D)=1. The payoffs to profiles 1(1/3, 1/3, 1/3) and 2(0, 1/2, 1/2) are 第16页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibri

15、um 1.1.2劣策略(Dominated Strategies)Is there an obvious prediction of how the game described in figure 1.1 should be played? Note that, no matter how player 1 plays, R gives player 2 a strictly higher payoff than M does. In formal language, strategy M is strictly dominated. Thus, a “rational” player 2

16、should not play M. Furthermore, if player 1 knows that player 2 will not play M, then U is a better choice than M or D. Finally, if player 2 knows that player 1 knows that player 2 will not play M, then player 2 knows that player 1 will play U, and so player 2 should play L.第17页，共69页。1. 完全信息静态博弈Game

17、s in Strategic Form and Nash Equilibrium 一个纯策略，即使其不严格劣于任何一个纯策略，却可能严格劣于一个混合策略A pure strategy may be strictly dominated by a mixed strategy even if it is not strictly dominated by any pure strategyHere player 1s strategy M is not dominated by U, because M is better than U if player 2 moves R; and M is

18、 not dominated by D, because M is better than D when 2 moves L. However, if Player 1 plays U with probability 1/2 and D with probability 1/2, he is guaranteed an expected payoff of 1/2 regardless of how player 2 plays, which exceeds the payoff of 0 he receives from M. Hence, a pure strategy may be s

19、trictly dominated by a mixed strategy even if it is not strictly dominated by any pure strategy. 第18页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium 严格劣策略 (Strictly Dominated Pure Strategy )第19页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium So far we have considered domi

20、nated pure strategies. It is easy to see that a mixed strategy that assigns positive probability to a dominated pure strategy is dominated. However, a mixed strategy may be strictly dominated even though it assigns positive probability only to pure strategies that are not even weakly dominated. Figu

21、re 1.3 gives an example. 第20页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium When a game is solvable by iterated strict dominance in the sense that each player is left with a single strategy, as in figure 1.1, the unique strategy profile obtained is an obvious candidate for the predict

22、ion of how the game will be played. Although this candidate is often a good prediction, this need not be the case, especially when the payoffs can take on extreme values.第21页，共69页。1. Games in Strategic Form and Nash EquilibriumIn the original story, two suspects are being separately interrogated and

23、 invited to confess. One of them, say A, is told, “If the other suspect, B, does not confess, then you can cut a very good deal for yourself by confessing. But if B does confess, then you would do well to confess, too; otherwise the court will be especially tough on you. So you should confess no mat

24、ter what the other does.” B is told to confess, with the use of similar reasoning. AlconfessDontBobconfess0, 02, -1Dont-1, 21, 11.1.3 Applications of the Elimination of Dominated Strategies Example 1.1 The Prisoners Dilemma如果Bob的策略是Al的最优反应策略是坦白坦白不坦白坦白第22页，共69页。1. Games in Strategic Form and Nash Equ

25、ilibrium 1.1.3 Applications of the Elimination of Dominated Strategies Many versions of the prisoners dilemma have appeared in the social sciences. One example is moral hazard in teams. Suppose that there are two workers, i=1,2, and that each can “work”(si=1) or “shirk” (si=0). The total output of t

26、he team is 4(s1+ s2) and is shared equally between the two workers. Each worker incurs private cost 3 when working and 0 when shirking. With “work” identified with C and “shirk” with D, the payoff matrix for this moral-hazard-in-teams game is that of figure 1.7, and “work” is a strictly dominated st

27、rategy for each worker. 第23页，共69页。1. Games in Strategic Form and Nash Equilibrium1.1.3 Applications of the Elimination of Dominated StrategiesExamplePlayer 2LeftMiddleRightPlayer 1Up1, 01, 20, 1Down0, 30, 12, 0第24页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Example Second-Price Auc

28、tion第25页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Solution to the Second-Price Auction第26页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Solution to the Second-Price AuctionThus, it is reasonable to predict that bidders bid their valuation in the second-price aucti

29、on. Therefore, bidder I wins and has utility vI-vI-1. Note also that because bidding ones valuation is a dominant strategy, it does not matter whether the bidders have information about one anothers valuations. Hence, if bidders know their own valuation but do not know the other bidders valuations,

30、it is still a dominant strategy for each bidder to bid his valuation. 第27页，共69页。1. Games in Strategic Form and Nash Equilibrium 1.2 Nash Equilibrium 1.2.1 Definitions of Nash EquilibriumA Nash equilibrium is a profile of strategies such that each players strategy is an optimal response to the other

31、players strategies. 第28页，共69页。1. Games in Strategic Form and Nash Equilibrium Pure-Strategy Nash EquilibriumA pure-strategy Nash equilibrium is a pure-strategy profile that satisfies the same conditions. That is, for allSince expected utilities are “linear in the probabilities,” if a player uses a n

32、ondegenerate mixed strategy in a Nash equilibrium, he must be indifferent between all pure strategies to which he assigns positive probability. 第29页，共69页。1. Games in Strategic Form and Nash Equilibrium Strict Nash Equilibrium第30页，共69页。1. Games in Strategic Form and Nash Equilibrium Consistent Predic

33、tionsNash equilibria are “consistent” predictions of how the game will be played, in the sense that if all players predict that a particular Nash equilibrium will occur then no player has incentive to play differently. Thus, a Nash equilibrium, and only a Nash equilibrium, can have the property that

34、 the players can predict it, predict that their opponents predict it, and so on. In contrast, a prediction that any fixed non-Nash profile will occur implies that at least one player will make a “mistake,” either in his prediction of his opponents play or (given that prediction) in his optimization

35、of his payoff. 第31页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium We do not maintain that such mistakes never occur. In fact, they may be likely in some special situations. But predicting them requires that the game theorists know more about the outcome of the game than the participan

36、ts know. This is why most economic applications of game theory restrict attention to Nash equilibria. 第32页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium The fact that Nash equilibria pass the test of being consistent predictions does not make them good predictions, and in situations i

37、t seems rash to think that a precise prediction is available. By “situations” we mean to draw attention to the fact that the likely outcome of a game depends on more information than is provided by the strategic form. For example, one would like to know how much experience the players have with game

38、s of this sort, whether they come from a common culture and thus might share certain expectations about how the game will be played, and so on. 第33页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Dominance and Nash EquilibriumThe same property holds for iterated dominance. That is, if

39、a single strategy profile survives iterated deletion of strictly dominated strategies, then it is the unique Nash equilibrium of the game. 第34页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Dominance and Nash EquilibriumConversely, any Nash-equilibrium strategy profile must put weight

40、 only on strategies that are not strictly dominated (or, more generally, do survive iterated deletion of strictly dominated strategies), because a player could increase his payoff by replacing a dominated strategy with one that dominates it. However, Nash equilibria may assign positive probability t

41、o weakly dominated strategies. 第35页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium 1.2.2 Examples of Pure-Strategy EquilibriaExample: Cournot Competition 第36页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Example: Cournot Competition (continued)第37页，共69页。1. 完全信息静态博弈Games

42、 in Strategic Form and Nash Equilibrium Example: Cournot Competition (continued)第38页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Example: Hotelling Competition 第39页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Example: Hotelling Competition 第40页，共69页。1. 完全信息静态博弈Games

43、 in Strategic Form and Nash Equilibrium Example: Hotelling Competition 第41页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Example: Majority Voting There are three players, 1, 2, and 3, and three alternatives, A, B, and C. Players vote simultaneously for an alternative; abstaining is n

44、ot allowed. Thus, the strategy spaces are Si=A, B, C. The alternative with the most votes wins; if no alternative receives a majority, then alternative A is selected. The payoff functions areThis game has three pure-strategy equilibrium outcomes: A, B, and C. There are more equilibria than this: If

45、players 1 and 3 vote for outcome A, then player 2s vote does not change the outcome, and player 3 is indifferent about how he votes. Hence, the profiles (A, A, A) and (A, B, A) are both Nash equilibrium whose outcome is A. (The profile (A, A, B) is not a Nash equilibrium, since if player 3 votes for

46、 B then player 2 would prefer to vote for B as well.) 第42页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash EquilibriumRogerHeadsTailsBarryHeads-1, 11, -1Tails1, -1-1, 11.2.3 Nonexistence of a Pure-Strategy Equilibrium Not all games have pure-strategy Nash equilibria. Two examples of games whose onl

47、y Nash equilibrium is in (nondegenerate) mixed strategies follow.Matching Pennis Game第43页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash EquilibriumPrincipalINIAgentS0, -hw, -wWw-g, v-w-hw-g, v-wInspection Game A popular variant of the “matching pennies” game is the “inspection game,” which has be

48、en applied to arms control, crime deterrence, and worker incentives. 第44页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Battle of the sexes WshowgameHshow1, 20, 0game0, 02, 11.2.4 Multiple Nash Equilibria, Focal Points, and Pareto OptimalityMany games have several Nash equilibria. Whe

49、n this is the case, the assumption that a Nash equilibrium is played relies on there being some mechanism or process that leads all the players to expect the same equilibrium. 2/3 1/31/32/3第45页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash EquilibriumChicken Game or hawk-dove Game MikeGo straight

50、TTurn awayWNeilGo straightT-1, -12, 1Turn awayW1, 20, 01/21/2第46页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Focal pointsSchellings (1960) theory of “focal points” suggests that in some “real-life” situations players may be able to coordinate on a particular equilibrium by using in

51、formation that is abstracted away by the strategic form. One reason that game theory abstracts away from such considerations is that the “focalness” of various strategies depends on the players culture and past experiences. For example, suppose two players are asked to name an exact time, with the p

52、romise of a reward if their choices match. 第47页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Focal Points: Stag-hunt GameAnother example of multiple equilibria is the stag-hunt game we used to begin with chapter, where each player has to choose whether to hunt hare by himself or to j

53、oin a group that hunts stag. Suppose now that there are I players, that choosing hare gives payoff 1 regardless of the other players actions, and that choosing stag gives payoff 2 if all players choose stag and gives payoff 0 otherwise. This game has two pure-strategy equilibria: “all stag” and “all

54、 hare.” Nevertheless, it is not clear which equilibrium should be expected. In particular, which equilibrium is more plausible may depend on the number of players. p 1/2; p8 1/2, or p 0.93 “all hare” risk-dominates “all stag.” 第48页，共69页。1. 完全信息静态博弈Games in Strategic Form and Nash Equilibrium Pareto OptimalityPlayer 2LRPlayer 1U9, 90, 8D8, 07, 7Although risk dominance then suggests that a Pareto-dominant equilibrium need not always be played, it is sometimes argued that players will in fact coordinate on the Pareto-dominant equilibrium (provided one exists) if they are able to talk to one a