序贯博弈和同时博弈的结合 Combining Sequential and Simultaneous Moves第6章 Chapter 6

序贯博弈和同时博弈的结合 Combining Sequential and Simultaneous Moves博弈类型 Game Type概念 Concepts分析技术 Techniques of Analysis博弈树(扩展形式) Game Trees (Extensive form)收益表(策略形式) Payoff tables (Strategic form)

纯粹序贯博弈反转均衡 Purely Sequential- Rollback move games equilibrium纯粹同时博弈 Purely Simultaneousmove games纳什均衡 Nash equilibrium

Slide 2

序贯博弈和同时博弈的结合 Combining Sequential and Simultaneous Moves在现实中，许多策略环境包含了这两种相互作用的成分。 In reality, many strategic situations contain elements of both types of interaction.而且，我们还可以使用扩展形式或策略形式分析任何一种博弈(可以交叉使用)。 Also, we can use either extensive form or strategic form for any type of game.Slide 3

内容提要 Outline兼具同时和序贯行动的博弈 Games with both simultaneous and sequential moves改变博弈中的行动顺序 Changing the order of moves in a game !改变分析方法 Change in the method of analysis *三人博弈 Three-player gamesSlide 4

兼具同时和序贯行动的博弈 Games with Both Simultaneous and Sequential Moves典型的例子一般都是博弈者在一段比较长的时间内相互作用。 The most obvious examples are those between players over an extended period of time.这样的博弈是同时利用博弈树和反转，以及收益表和纳什均衡的工具来分析的。 Such games are analyzed by combing the tools of trees and rollback, and payoff tables and Nash Equilibrium.Slide 5

兼具序贯和同时行动的一个两阶段博弈 A Two-stage Game Combining Sequential and Simultaneous Moves有两个可能成为电信巨头的企业：C和G。 There’re two would-be telecom giants, CrossTalk and GlobeDialog.每个企业都需要同时选择是否投资100亿以购置光纤网。 Each can choose whether to invest$10 billion in the purchase of a fiberoptic network, simultaneously.如果一个企业投资了而另一个没有，投资的企业需要确定其电信服务的定价。 If one invests and the other does not, then the investor has to make a pricing decision for its telecom service.如果两个企业都投了，那么他们的定价选择成为一个第二阶段的同时博弈。 If both invest, then their pricing choices become a second simultaneous-move game.Slide 6

兼具序贯和同时行动的一个两阶段博弈 A Two-stage Game Combining Sequential and Simultaneous MovesFirst stage: Investment Game GLOBEDIALOG Don’t CROSSTALK Don’t Invest 0, 0,0 Invest 0, GLOBALDIALOG High Second stage: GlobalDialog’s pricing decision

14

Low Second stage: pricing game

6

Second stage: GlobalDialog’s pricing decision High

GLOBEDIALOG High Low -10, 6 -2, -2 Slide 7

CROSSTALK

14

CROSSTALK

High L

ow

2, 2 6,-10

Low

6

兼具序贯和同时行动的一个两阶段博弈 A Two-stage Game Combining Sequential and Simultaneous MovesTwo Nash Equilibria: A chicken game GLOBEDIALOG Don’t CROSSTALK Don’t Invest 0, 0 14, 0 Invest 0, 14 -2, -2

Stage one Investment Game (After Substituting Rolled-Back Payoffs from the Equilibrium of the Second Stage)

Slide 8

子博弈 Subgames一个子博弈是整个博弈的一部分，它自身就构成一个完备博弈，具有完整的结构：博弈者、策略和收益。 A subgame is a part of a full game, which is also a full-fledged game in its own right, with a fully specified structure of players, strategies, and payoffs.更一般的，一个子博弈是多行动博弈的一部分，它开始于原博弈的某一个节点。 More generally, a subgame is the part of a multimove game that begin at a particular node of the original game.一个多行动博弈具有的子博弈数目等于其决策点数目。 A multimove game has as many subgames as it has decision nodes.Slide 9

多阶段博弈的构成：例子 Configurations of Multistage Games: Examples假设G事先已经投了100亿了 Suppose GlobalDialog has already made the$10 billion investment……CROSSTALK High Low GLOBEDIALOG High 2, 2 6,-10 Low -10, 6 -2, -2

Invest

CROSSTALKDon’t GLOBALDIALOG

High

0, 14

Low

0, 6Slide 10

多阶段博弈的构成：例子 Configurations of Multistage Games: Examples德国女足防守阵形中国女足防守阵形进攻阵形 1 3进攻阵形 2

反应德国女足

1 2

变阵中国女足不变阵 -1

不反应

Simultaneous-move First Stage Followed by Sequential MovesSlide 11

多阶段博弈的构成：例子 Configurations of Multistage Games: Examples德国女足防守阵形中国女足防守阵形进攻阵形 1 3进攻阵形 2 1

No pure strategy Nash equilibrium. It turns out our Chinese team should choose the attack lineup with probability 1/3. (Shown in Ch7)

Slide 12

改变博弈中的行动顺序 Changing the Order of Moves in a Game序贯博弈可以变成同时的，如果参与者在做出自己的选择时，不能观察到对手的行动。 Sequential-move games become simultaneous if the players cannot observe moves made by their rivals before making their own choices.这样，我们就得去寻找纳什均衡而非反转均衡。 In that case, we would analyze the game by searching for a Nash equilibrium rather than for a rollback equilibrium.Slide 13

改变博弈中的行动顺序 Changing the Order of Moves in a Game同时博弈也可以变成序贯的，如果某一参与者能够在做出自己选择前观察到其他人的行动。 A simultaneous-move game could become sequential if one player were able to observe the other’s move before choosing her own.博弈规则的任何改变，也能改变其结果。 Any changes to the rules of the game can also change its outcome.Slide 14

变同时博弈为序贯博弈 Changing Si

multaneous-Move Games into Sequential-Move Games结果不变 No change in outcome先行者优势 First-mover advantage后行者优势 Second-mover advantage双方都更好 Both Players may be betterSlide 15

结果不变 No Change in Outcome某些博弈，无论是同时的，还是序贯的，也无论序贯博弈中行动顺序如何，结果都不变。 Certain games have the same outcomes in the equilibrium of both simultaneous and sequential versions and regardless of the order of play in the sequential game.这一结果通常产生在所有博弈者都具有优势策略时。This result generally arises only when both or all players have dominant strategies.Slide 16

例：囚徒困境的三个版本 Three Versions of the Prisoners’ Dilemma GameWIFE Confess (Defect) HUSBAND Confess (Defect) Deny (Cooperate) 10 yr, 10 yr 25 yr, 1 yr Deny (Cooperate) 1 yr, 25 yr 3 yr, 3 yr

(a) Simultaneous play Confess WIFE Confess HUSBAND Confess Deny WIFE Deny 3, 3 HUSBAND, WIFE (b) Sequential play: Husband moves first 25, 1 4? Deny HUSBAND Deny 3, 3 Deny 1, 25 WIFE Confess 25, 1 10, 10 Confess HUSBAND Confess 10, 10

Deny

1, 25

WIFE, HUSBAND Slide 17 (c) Sequential play: Wife moves first

先行者优势 First-Mover Advantage先行者优势可能产生在博弈规则从同时行动变为顺序行动时。 A first-mover advantage may emerge when the rules of a game are changed from simultaneous to sequential play.至少来说，如果同时博弈具有多重均衡，序贯博弈可以使先行者从中选择对自己有利的结果。 At a minimum, if the simultaneousmover version has multiple equilibria, the sequential-move version enables the first mover to choose his preferred outcome. Slide 18

先行者优势：小鸡博弈的例子 First-Mover Advantage: An Example of ChickenDEAN Swerve (Chicken) JAMES Swerve (Chicken) Straight (Tough) 0, 0 1, -1 Straight (Tough) -1, 1 -2, -2

(a) Simultaneous play Swerve DEAN Swerve Straight JAMES Swerve Straight DEAN -2, -2 Straight JAMES, DEAN (b) Sequential play: James moves first 1, -1 Straight JAMES -2, -2 Straight DEAN, JAMES Slide 19 (c) Sequential play: Dean moves first -1, 1 DEAN Swerve 1, -1 Swerve Straight 0, 0 Swerve JAMES -1, 1 0, 0

后行者优势 Second-Mover Advantage从同时行动变为序贯行动的博弈，也可以导致后行者优势。 A second-mover advantage may emerge when simultaneous play is changed into sequential play.

Slide 20

后行者优势：运动比赛的例子 Second-Mover Advantage: An Example of SportNo pure strategy Nash equilibrium. In the mixed strategy Nash equilibrium, Evert gets 62 on average.EVERT DL CC NAVRATILOVA DL 50 90 CC 80 20

(a) Simultaneous play

DL NAVRATILOVA DL CC EVERT DL CC NAVRATILOVA CC

50, 50 EVERT 80, 20 90, 10 CC 20, 80 EVERT DL NAVRATILOVA

DL

50, 50

CC DL

10, 90 20, 80

EVERT, NAVRATILOVA (b) Sequential play: EVERT moves first

80, 20 CC NAVRATILOVA, EVERT Slide 21 (c) Sequential play: Wife moves first

双方

都更好 Both Player May Do Better直观地，一个博弈可能具有先行者或后行者优势。只不过在同时行动时，这一优势被压制了，而在给出行动顺序后得到了体现。 Intuitively, A game may have a firstmover or a second-mover advantage, which is suppressed when moves have to be simultaneous but emerges when an order of moves is imposed.令人惊讶的是，当规则从一种变为另一种时，双方参与者都有可能变好。 Surprisingly, both player may do better under one set of rules of play than Slide 22 under another.

双方都更好：例子 Both Player May Do Better: An Example(a) Simultaneous moves FEDERAL RESERVE

Low interest rates CONGRESS Budget balance Budget deficit 3, 4

High interest rates 1, 3

4, 1

2, 2

Congress has a dominant strategy: Budget deficit. The unique Nash equilibrium is: (Budget deficit, High interest rate) Slide 23

双方都更好：例子 Both Player May Do Better: An Example(b) Sequential moves: Fed moves first FED, CONGRESS

CONGRESS

Balance Deficit

4, 3 1, 4

Low FED High CONGRESS

Balance

3, 1 2, 2

Deficit

Slide 24

双方都更好：例子 Both Player May Do Better: An Example(b) Sequential moves: Congress moves first CONGRESS, FED

FED

Low High

3, 4 1, 3

Balance CONGRESS Deficit FED

Low

4, 1 2, 2

High

Slide 25

双方都更好：例子 Both Player May Do Better: An Example更令人奇怪的是，更好的结果来自于当国会先行时，而它所选择的平衡预算策略是它的劣势策略。 Even more surprisingly, the better outcome obtain when Congress moves first results from its choosing Balance, which is its dominated strategy.是否矛盾？ Is this a paradox?Slide 26

双方都更好：例子 Both Player May Do Better: An Example赤字成为优势策略，从国会的角度讲，就要求它在任意给定的 Fed的行动下，都要比平衡预算来得好。 For deficit to be a dominant strategy, it must be better than Balance from the Congress’s perspective for each given choice of the Fed.这种比较在同时博弈中是有意义的，因为国会必须： This type of comparison between Deficit and Balance is relevant in the simultaneous-move game because there the Congress must…………在不知道Fed的选择时决策 make a decision without knowing the Fed’s choice……透彻考虑Fed的行动，或者对之形成信念，以选择自己的最优反应。也即，选择一个理性化策略。 think through, or formulate a belief about, the Fed’s action, and choose its best response to that. I.e, it must choose a rationalizable strategy.Slide 27

双方都更好：例子 Both Player May Do Better: An Example这一比较在国会后行动时也是有意义的。它知道Fed的行动后，只需选择其最优反应，总为赤字。 The comparison is also relevant with sequential moves if the Congress moves second, then it knows what the Fed has already done and merely picks its best respon

se, which is always Deficit.然而，如果国会先行，它就不能(或无须)将Fed的行动看成既定。 However, if the Congress moves first, it cannot take the Fed’s choice as given.相反，它必须考虑到Fed对自己先前行动的最优反应，以及由此带来的收益。然后选择自己喜欢的结果。 Instead, it must recognize the Fed’s best response to each of its own first moves, and payoffs as a result. Then choose its more preferred outcome between them.因而优势的思想对于先行者来说可能没有意义。 Thus the idea of dominant may cease to be a relevant concept for the first mover.Slide 28

双方都更好：例子 Both Player May Do Better: An Example在这一博弈中，国会和Fed将会达成协议，让国会先行。 In this game, the Congress and the Fed would agree that the Congress should move first.不过，协议要得以实施，先行的技术条件必须满足，即：先行的行动必须可以被后行者观察到，并且一旦行动，不能逆转。 However, to implement the agreement, the technical requirements of a first move– that it be observable to the second mover and not reversible thereafter– must be satisfied.

Slide 29

改变分析方法 Change in the Method of Analysis博弈树是表示序贯博弈的理想方式，收益表是表示同时博弈的理想方式。 Game trees are the natural way to display sequential-move games, and payoff tables the natural representation of simultaneous-move games.不过，上述每一方法适当修改都可以用来表示另一种博弈。 However, each technique can be adapted to the other type of game.Slide 30

用博弈树表示同时博弈 Illustrating Simultaneous-Move Games by Using TreesEVERT, NAVRATILOVA NAVRATILOVA

DL

50, 50

DL EVERT CCNAVRATILOVA

CC

80, 20

Information setDL 90, 10

CC

20, 80

Slide 31

信息集 Information Set信息集表明对于当前参与者不完美信息的存在：给定其可得的信息，她无法辨别该集合中的节点。 An information set indicate the presence of imperfect information for the player who moves there. She cannot distinguish between the nodes in the set, given her available information.她在单独一个信息集中的策略选择必须对集合中的所有节点规定相同的行动。 Her strategy choice from within a single information set must specify the same move at all the nodes contained in it.Slide 32

用策略形式表示和分析序贯博弈 Showing and Analyzing SequentialMove Games in Strategic FormCONGRESS, FED

FED Balance CONGRESS Deficit FED

Low High

3, 4 1, 3

Low

4, 1 2, 2

High

How to show this game in normal/strategic form, i.e., by using a payoff table? Slide 33

用策略形式表示和分析序贯博弈 Showing and Analyzing SequentialMove Games in Strategic FormFed’s strategies Congress’s strategies Balance CONGRESS Deficit L if B, H if D 3, 4 2, 2 FED H if B, L if D 1, 3 4, 1 L if B, L if D 3, 4 4

, 1 H if B, H if D 1, 3 2, 2

Two Nash Equilibria: (Balance, LH), (Deficit, HH). But the game produced just one rollback equilibrium– (Balance, LH) when analyzed in its extensive form! Slide 34

用策略形式表示和分析序贯博弈 Showing and Analyzing SequentialMove Games in Strategic Form不过，策略组合(赤字，总是高利率)不是该序贯博弈的合理预测。 Yet, the strategy combination (Deficit, High always) is not a sensible prediction of this sequential game.在这一策略组合中，Fed从来没有使用过其策略的一部分——“在平衡时采取高利率”。这一部分仅作为了对国会的一种威胁。 In this strategy combination, Fed never plays one part of his strategy–“ High if Balance”. It’s only a threaten to the Congress.但这一威胁是不可信的，因为一旦有必要采取它时，Fed总会发现偏离它是最优的。 But this threaten is incredible since once the need arises to play it, the Fed will always find it optimal to deviate.国会预计到了这一点，不会对这一威胁当真。 The Congress will foresee this and not take this threaten seriously.Slide 35

用策略形式表示和分析序贯博弈 Showing and Analyzing SequentialMove Games in Strategic Form换句话说，该策略组合不合理，是因为Fed在其始于国会选了平衡后的子博弈中没有出最优反应(也就是纳什均衡策略)。 In other words, strategy combination (Deficit, High always) is not sensible because the Fed did not play its best response (and also, its Nash equilibrium strategy) in his subgame starting at the node where the Congress has already chosen Balance.这一策略组合没有构成一个子博弈完美均衡。 This strategy combination does not form a subgame-perfect equilibrium.Slide 36

子博弈完美均衡 Subgame-Perfect Equilibrium子博弈完美(纳什)均衡(SPE)由来自各参与者的策略组合而成。在博弈树的每一节点上(无论该节点是否位于博弈的均衡路径上)都有一个子博弈，而整体策略在子博弈延续的部分，在起始点上对于相应参与者为最优。 A subgame-perfect (Nash) equilibrium (SPE) is a set of strategies, one for each player, such that at every node of the game tree, whether or not the node lies along the equilibrium path of play, the continuation of the same strategy in the subgame starting at that node is optimal for the player who takes the action there.简单说，SPE要求参与者的策略在整个博弈的每一个子博弈中都是纳什均衡策略。 SPE requires players to use strategies that constitute a Nash equilibrium in every subgame of the larger game.Slide 37

子博弈完美均衡和反转均衡 SPE and Rollback Equilibrium在有限和信息完美的博弈中，除个别不重要的情况，反转的方法都可以找出唯一的子博弈均衡。 In games with finite trees and perfect information, where players can obse

rve every previous action taken by all other players so that there are no multiple nodes enclosed in one information set, rollback finds the unique (except for trivial and exceptional cases ot ties) subgame-perfect equilibrium of the game.复杂信息结构和信息集的博弈中，子博弈完美的概念涵盖更广。 In games with complex information structures and information set, subgame perfectness becomes a rich notion. Slide 38

子博弈完美均衡和反转均衡 SPE and Rollback Equilibrium因而，反转或SPE是对纳什均衡概念的进一步检验和补充，以从策略形式的多重均衡中进行选择。 Thus, rollback, or SPE is a further test, supplementing the requirements of a Nash equilibrium and helping to select from among multiple Nash equilibria of the strategic form.它是纳什均衡概念的一种精炼。 It is a refinement of the Nash equilibrium concept.Slide 39

总结 Summary许多博弈都包括了多重成分，包括同时和序贯行动。 Many games include multiple components, some of which entail simultaneous play and others of which entail sequential play.在后面的行动中出现的完备博弈成为整个博弈的子博弈。 Full-fledged games that arise in later stages of play are called subgames of the full game.Slide 40

总结 Summary改变博弈规则以变更行动顺序可能改变也可能不改变均衡结果。 Changing the rules of a game to alter the timing of moves may or may not alter the equilibrium outcome of a game.同时博弈可以用博弈树表示。由于参与者在决策时不知道他们处于某些节点中的具体哪个，就需要把所有这些节点归入信息集。 Simultaneous-move games can be illustrated in a game tree by collecting decision nodes in information set when players make decisions without knowing at which specific node they find themselves.Slide 41

总结 Summary序贯博弈可以用博弈表来表示。 Sequential-move games can be illustrated by using a game table.用其策略形式来求解一个序贯博弈，可能导致过多的纳什均衡，减少的办法时使用子博弈完美均衡(SPE)的概念。 Solving a sequential-move game from its strategic form may lead to many possible Nash equilibria, which can be reduced by using the concept of subgame-perfect equilibrium (SPE).Slide 42