Dynamic Games of Complete Information

Presentation on theme: "Dynamic Games of Complete Information"— Presentation transcript:

1 Dynamic Games of Complete Information
Lecture 12 June 4, 2003 Dynamic Games of Complete Information Subgame-Perfect Nash Equilibrium Game theory-Chapter 2

2 Outline of dynamic games of complete information
Extensive-form representation Dynamic games of complete and perfect information Game tree Subgame-perfect Nash equilibrium Backward induction Applications Dynamic games of complete and imperfect information More applications Repeated games Game theory-Chapter 2

3 市场进入博弈（Entry Game） 一个已进入市场的垄断者（incumbent）面临一个挑战者（challenger）可能的进入.
挑战者 可能选择 进入（in） 或者 不进入（out）. 如果 挑战者 进入, 那么 垄断者 可以选择 温和策略（accommodate，A） 或者 激进策略（to fight，F）。 收益是共同知识. Challenger In Out Incumbent 第一个数字是挑战者的收益. 第二个数字是垄断者的收益. 1, 2 A F 2, 1 0, 0 Game theory-Chapter 2

4 Sequential-move matching pennies
Player 1 两个参与人各有一枚硬币. Player 1先选择是显示 Head还是 Tail. 在观察player 1的选择之后, player 2选择显示Head或 Tail 两个参与人都知道以下规则: 如果两枚硬币一致 (都是heads 或都是 tails) 那么player 2 赢得 player 1的硬币. 否则, player 1赢得 player 2的硬币. H T Player 2 Player 2 H T H T -1, 1 1, -1 1, -1 -1, 1 Game theory-Chapter 2

5 Dynamic (or sequential-move) games of complete information
一个参与人集合 谁先行动，可以采取什么行动? 当参与人行动时他们知道什么? 参与人的收益取决于他们的选择. 所有这些都是参与人的共同知识. Game theory-Chapter 2

6 Definition: extensive-form representation
一个博弈的扩展式表述包括的要素: 博弈中的参与人 每个参与人在何时行动 每次轮到某一参与人行动时，可供她选择的行动 每次轮到某一参与人行动时，她所了解的信息 每个参与人从她每个可选的行动组合中获得的收益 Game theory-Chapter 2

7 Dynamic games of complete and perfect information
完全且完美信息动态博弈的特点： 行动是顺序发生的； 在选择下一次行动前可以观察到所有以前的行动； 每一可能的行动组合下参与者的收益都是共同知识。 例子： 斯塔克尔贝里的双头垄断模型； 里昂惕夫的有工会企业工资和就业模型。 Game theory-Chapter 2

8 博弈树 博弈树包括这样的节点（nodes ）集合和边缘（edges ）集合 每个边缘连接两个节点 (这两个节点应该是相连的)
x0 博弈树包括这样的节点（nodes ）集合和边缘（edges ）集合 每个边缘连接两个节点 (这两个节点应该是相连的) 对任何节点组合来说, 连接这两个节点的路径（path）是惟一的 a path from x0 to x4 a node x1 x2 x3 x4 x5 x6 x7 x8 an edge connecting nodes x1 and x5 Game theory-Chapter 2

9 Game tree a path from x0 to x4 路径是不同节点y1, y2, y3, ..., yn-1, yn 的一个序列，其中对于i=1, 2, ..., n-1，yi 和 yi+1相邻. 我们说这条路径是从y1到yn. 我们也可以用这些节点推导出的边缘的序列来定义路径. 路径的长度（length ）是路径中包含的边缘的数量. 例 1: x0, x2, x3, x7 是一条路径，长度为3. 例2: x4, x1, x0, x2, x6是一条路径，长度为4. x0 x1 x2 x3 x4 x5 x6 x7 x8 Game theory-Chapter 2

10 Game tree 博弈树中，博弈开始的节点x0被称为根（root ）
与x0相邻的节点是x0的后续节（successors ）. x0的后续节点是x1, x2 对任何两个相邻的节点来说, 与根相连接的路径更长的那个节点是另一个节点的后续节. 例3: x7 是x3的后续节点，因为它们相邻，而且x7到x0的路径比x3到x0的路径更长 x1 x2 x3 x4 x5 x6 x7 x8 Game theory-Chapter 2

11 Game tree 如果x是另一个节点y的后续节，那么y被称为x的前续节（predecessor ）.
在博弈树中, 根以外的任何节点都有惟一的前续节. 没有后续节的所有节点被称为终点节（terminal node ），它是博弈可能的终点 例4: x4, x5, x6, x7, x8 都是终点节 x1 x2 x3 x4 x5 x6 x7 x8 Game theory-Chapter 2

12 Game tree 除终点节以外的任何节点都代表了某个参与人.
Player 1 除终点节以外的任何节点都代表了某个参与人. 对于终点节以外的任意节点来说, 连接它和它的后续节的边缘代表了这个节点所代表的参与人可能采取的行动 H T Player 2 Player 2 H T H T -1, 1 1, -1 1, -1 -1, 1 Game theory-Chapter 2

13 Game tree 从根到一个终点节的路径代表了一个完全的行动序列，它决定了终点节的收益 Player 1 H T Player 2
-1, 1 1, -1 1, -1 -1, 1 Game theory-Chapter 2

14 Strategy 参与人的一个策略是关于行动的一个完整计划。 它明确了在参与人可能会遇到的每一种情况下对可行行动的选择.
Game theory-Chapter 2

15 Strategy and payoff 在博弈树中, 参与人的策略用边缘的集合（a set of edges）来表述出来.
每个参与人的一个策略共同构成一个策略组合（边缘的集合）。这个策略组合推导出从根到终点节的一条路径，这决定了所有参与人的收益 Game theory-Chapter 2

16 Sequential-move matching pennies
Player 1的策略 Head Tail Player 2的策略 H if player 1 plays H, H if player 1 plays T H if player 1 plays H, T if player 1 plays T T if player 1 plays H, H if player 1 plays T T if player 1 plays H, T if player 1 plays T Player 2的策略分别用HH, HT, TH 和TT来表示. Game theory-Chapter 2

17 Sequential-move matching pennies
博弈的标准式表达 {参与人1，参与人2} 参与人1的策略集={H，T} 参与人2的策略集={HH，HT，TH，TT} 两个参与人的收益 参与人 2 HH HT TH TT 参与人 1 H -1 , 1 1 , -1 T Game theory-Chapter 2

18 Nash equilibrium 完全信息动态博弈中的纳什均衡集（the set of Nash equilibrium）就是它的标准式的纳什均衡集合. 怎样找到完全信息动态博弈的纳什均衡 构建完全信息动态博弈的标准式 在标准式中找到纳什均衡 Game theory-Chapter 2

19 73-347 Game Theory--Lecture 12
Entry game Challenger的策略 In Out Incumbent的策略 Accommodate (如果challenger选择In) Fight (如果challenger选择In) 收益 标准式表述 Incumbent Accommodate Fight Challenger In 2 , 1 0 , 0 Out 1 , 2 June 4, 2003 Game Theory--Lecture 12

20 Nash equilibria in entry game
两个纳什均衡 ( In, Accommodate ) ( Out, Fight ) 第二个纳什均衡有意义吗? 不可置信的威胁（Non-creditable threats） Incumbent Accommodate Fight Challenger In 2 , 1 0 , 0 Out 1 , 2 Game theory-Chapter 2

21 不可置信的威胁（non-credible threat）
威胁可信性问题的根源是动态博弈中事前最优和事后最优的不一致性——动态不一致性。 1994年诺贝尔经济学奖获得者Reinhard J.R. Selten（泽尔藤）认为：在一个动态博弈中，如果参与人是理性的，他应该往前看，即不管是前制定的计划如何，他在新的时点上作决策都应该根据当前的情形选择最优的行动。 我们把动态博弈中的这种理性行为称为序贯理性（sequential rationality），它要求参与人在一个接一个的决策节点上都要选择最优行动。 Game theory-Chapter 2

22 去掉不合理的纳什均衡 子博弈完美纳什均衡（Subgame perfect Nash equilibrium）是纳什均衡的一个精炼（refinement ）。 它要求博弈的参与人必须是序贯理性的，即该战略不仅是事前最优的也是事后最优的，满足动态一致性的要求，因此可以排除不可置信的威胁。 如何在所有的纳什均衡中找出子博弈完美纳什均衡？ 我们首先需要定义子博弈（ subgame ）。 Game theory-Chapter 2

23 Subgame 博弈树的一个子博弈开始于一个非终点节，包含这个非终点节之后所有的节点和边缘 一个子博弈开始于一个非终点节x ，
Player 1 Player 2 H T 1, -1 -1, 1 a subgame -1, 1 Game theory-Chapter 2

24 Subgame: example Player 2 E F Player 1 G H 3, 1 1, 2 0, 0 Player 2 E F
C D 2, 0 Player 1 G H 1, 2 0, 0 Game theory-Chapter 2

25 Subgame-perfect Nash equilibrium
子博弈是指原博弈中由某一个决策时点开始之后的部分所构成的博弈，它本身可以视作一个独立的博弈，代表的是参与人在博弈过程中某一个决策时点所面临的决策情形。 原博弈可以看成是一个从根节点开始的子博弈。 在动态博弈中，如果一个纳什均衡的策略在每一个子博弈中都构成了纳什均衡，那么动态博弈的这个纳什均衡是子博弈完美的。 子博弈完美纳什均衡是一个纳什均衡. Game theory-Chapter 2

26 Entry game 两个纳什均衡 ( In, Accommodate ) 是子博弈完美的.
( Out, Fight )不是子博弈完美的，原因是在开始于Incumbent的子博弈中它没有导出纳什均衡. Challenger In Out Incumbent A F 1, 2 2, 1 0, 0 Incumbent A F 2, 1 0, 0 Accommodate is the Nash equilibrium in this subgame. Game theory-Chapter 2

27 Find subgame perfect Nash equilibria: backward induction
开始于那些最小的子博弈 然后反向移动直到到达根 Challenger In Out Incumbent 1, 2 A F 第一个数字是challenger的收益. 第二个数字是incumbent的收益. 2, 1 0, 0 Game theory-Chapter 2

28 Find subgame perfect Nash equilibria: backward induction
Player 2 E F Player 1 G H 3, 1 1, 2 0, 0 C D 2, 0 子博弈完美纳什均衡 (DG, E) Player 1 选D, 且如果player 2 选E ，则她选G 如果player 1选C，则 Player 2选E Game theory-Chapter 2

29 Existence of subgame-perfect Nash equilibrium
任何有限的完全且完美信息动态博弈都有一个子博弈完美纳什均衡，它可以通过逆向归纳法得到。 逆向归纳法的合理性在于我们假定参与人具有理性共识：参与人1具有理性，参与人2具有理性，参与人1知道参与人2具有理性，参与人2知道参与人1具有理性，参与人1知道参与人2知道参与人1具有理性，参与人2 知道参与人1知道参与人2具有理性。。。 Game theory-Chapter 2

30 Sequential bargaining (2.1.D of Gibbons)
参与人1和2就一美元的分配进行谈判. 时序如下: 在第一阶段开始时, player 1建议她分走1美元的 s1, 留给player 2的份额为 1-s1. Player 2或者接受这一条件，或者拒绝这一条件 (这种情况下，博弈将继续进行，进入第二阶段) 在第二阶段的开始, player 2提议 player 1分得1美元的 s2, 留给player 2的份额为 1-s2. Player 1或者接受这一条件，或者拒绝这一条件 (这种情况下，博弈继续进行，进入第三阶段) 在第三阶段的开始, player 1得到1美元的 s, player 2得到 1-s, 这里0<s <1. 参与人都是缺乏耐心的.他们用一个因子来对他们的收益进行贴现, 这里0<  <1 Game theory-Chapter 2

31 Sequential bargaining (2.1.D of Gibbons)
Player 1 propose an offer ( s1 , 1-s1 ) Period 1 Player 2 s1 , 1-s1 accept reject Player 2 propose an offer ( s2 , 1-s2 ) Player 1 Period 2 s2 , 1-s2 accept reject Period 3 s , 1-s Game theory-Chapter 2

32 Solve sequential bargaining by backward induction
阶段2: 当且仅当s2  s时，Player 1接受s2. (我们假定当接受和拒绝无差异时，参与人总是选择接受条件) Player 2面临以下两个选择 : (1) 向player 1提出 s2 = s, 在这个阶段留给她自己1-s2 = 1-s, 或者 (2) 向player 1提出 s2 < s (player 1将会拒绝它), 下阶段接受1-s. 它的贴现值是(1-s) 由于(1-s)<1-s, player 2应该提出条件 (s2* , 1-s2* ), 其中 s2* = s. Player 1将接受它. Game theory-Chapter 2

33 Sequential bargaining (2.1.D of Gibbons)
Player 1 propose an offer ( s1 , 1-s1 ) Period 1 Player 2 s1 , 1-s1 accept reject s , 1- s Player 2 propose an offer ( s2 , 1-s2 ) Player 1 Period 2 s2 , 1-s2 accept reject Period 3 s , 1-s Game theory-Chapter 2

34 Solve sequential bargaining by backward induction
阶段1: 当且仅当1-s1  (1-s2*)= (1- s) 或s1  1-(1-s2*)时, Player 2接受1-s1 ，其中s2* = s. Player 1面临以下两个选择 : (1) 向player 2提出 1-s1 = (1-s2*)=(1- s) ,在这个阶段留给她自己s1 = 1-(1-s2*)=1-+s, 或者 (2)向player 2提出1-s1 < (1-s2*) (player 2将会拒绝它),下阶段接受s2* = s.它的贴现值是s 由于s < 1-+s, player 1应该提出条件 (s1* , 1-s1* ), 其中 s1* = 1-+s Game theory-Chapter 2

35 Backward induction: illustration
Player 1 C D Player 2 E F 3, 0 2, 1 G H 1, 3 0, 2 子博弈完美纳什均衡 (C, EH). player 1选C; 如果player 1选 C，player 2选 E, 如果player 1 选D， player 2选 H. Game theory-Chapter 2

36 Multiple subgame-perfect Nash equilibria: illustration
Player 1 C E D Player 2 F G 1, 0 0, 1 Player 2 H I 2, 1 1, 1 Player 2 J K 1, 3 2, 2 子博弈完美纳什均衡(D, FHK). player 1选 D 如果player 1选C ，player 2选 F,如果player 1选D ， player 2选 H,如果player 1选E ， player 2选 K. Game theory-Chapter 2

37 Multiple subgame-perfect Nash equilibria
Player 1 C E D Player 2 F G 1, 0 0, 1 Player 2 H I 2, 1 1, 1 Player 2 J K 1, 3 2, 2 子博弈完美纳什均衡(E, FHK). player 1选 E; 如果player 1选C ，player 2选 F,如果player 1选D ， player 2选 H,如果player 1选E ， player 2选 K. Game theory-Chapter 2

38 Multiple subgame-perfect Nash equilibria
Player 1 C E D Player 2 F G 1, 0 0, 1 Player 2 H I 2, 1 1, 1 Player 2 J K 1, 3 2, 2 子博弈完美纳什均衡(D, FIK). player 1 plays D; 如果player 1选C ，player 2选 F,如果player 1选D ， player 2选 I,如果player 1选E ， player 2选 K. Game theory-Chapter 2

39 Stackelberg model of duopoly
仅有firm 1 和firm 2两家企业生产同质的产品. 产量分别用q1 和 q2表示. 博弈时间顺序如下: Firm 1选择产量 q1 0. Firm 2观察到 q1 ，然后选择产量q2 0. 市场价格是 P(Q)=a –Q, 这里a 是常数，且Q=q1+q2. firm i 生产qi 的成本是Ci(qi)=cqi. 收益函数: u1(q1, q2)=q1(a–(q1+q2)–c) u2(q1, q2)=q2(a–(q1+q2)–c) Game theory-Chapter 2

40 Stackelberg model of duopoly
用逆向归纳法找到子博弈完美纳什均衡 我们首先解决firm 2面对任意q1 0的问题，得到firm 2针对q1 的最优反应. 也就是说, 我们首先解出开始于firm 2的所有子博弈. 然后我们解决firm 1的问题. 也就是说,解出开始于firm 1的子博弈 Game theory-Chapter 2

41 Stackelberg model of duopoly
解决firm 2面对任意q1 0的问题，得到firm 2针对q1 的最优反应. Max u2(q1, q2)=q2(a–(q1+q2)–c) subject to 0  q2  +∞ FOC: a – 2q2 – q1 – c = 0 Firm 2的最优反应, R2(q1) = (a – q1 – c)/2 if q1  a– c = 0 if q1 > a– c Game theory-Chapter 2

42 Stackelberg model of duopoly
解决firm 1的问题. 注意到firm 1也能够解 firm 2的问题. 即, firm 1知道 firm 2对任意q1的最优反应. 所以, firm 1的问题是 Max u1(q1, R2(q1))=q1(a–(q1+R2(q1))–c) subject to 0  q1  +∞ 即, Max u1(q1, R2(q1))=q1(a–q1–c)/2 subject to 0  q1  +∞ FOC: (a – 2q1 – c)/2 = q1 = (a – c)/2 Game theory-Chapter 2

43 Stackelberg model of duopoly
子博弈完美纳什均衡 ( (a – c)/2, R2(q1) ), where R2(q1) = (a – q1 – c)/2 if q1  a– c = 0 if q1 > a– c 即, firm 1选择产量 (a – c)/2, firm 1选择产量q1时 firm 2选择产量 R2(q1). 逆向归纳解是 ( (a – c)/2, (a – c)/4 ). Firm 1选择产量 (a – c)/2, firm 2选择产量 (a – c)/4. Game theory-Chapter 2

44 Stackelberg model of duopoly
Firm 1生产 q1=(a – c)/2 它的利润是 q1(a–(q1+ q2)–c)=(a–c)2/8 Firm 2生产 q2=(a – c)/4 它的利润是 q2(a–(q1+ q2)–c)=(a–c)2/16 总产量是3(a – c)/4. Game theory-Chapter 2

45 Cournot model of duopoly
Firm 1生产 q1=(a – c)/3 它的利润是 q1(a–(q1+ q2)–c)=(a–c)2/9 Firm 2 生产 q2=(a – c)/3 它的利润是 q2(a–(q1+ q2)–c)=(a–c)2/9 总产量是2(a – c)/3. Game theory-Chapter 2

46 Monopoly 假设只有一家企业,即垄断者,生产产品.垄断者解以下问题来决定它的产量 qm.
Max qm (a–qm–c) subject to 0  qm  +∞ FOC: a – 2qm – c = qm = (a – c)/2 垄断者的产量 qm=(a – c)/2 它的利润 qm(a–qm–c)=(a–c)2/4 Game theory-Chapter 2

47 Sequential-move Bertrand model of duopoly (differentiated products)
两家企业: firm 1和firm 2. 每家企业选择它的产品的价格时不知道其他企业的选择. 价格分别用p1和p2表示. 博弈的时间顺序如下. Firm 1选择价格 p1 0. Firm 2观察到 p1 然后选择价格p2 0. 消费者对firm 1 产品的需求量: q1(p1, p2) = a – p1 + bp2. 消费者对firm 2 产品的需求量: q2(p1, p2) = a – p2 + bp1. firm i生产数量为qi的成本是Ci(qi)=cqi. Game theory-Chapter 2

48 Sequential-move Bertrand model of duopoly (differentiated products)
对任何p1 0解 firm 2的问题，得到firm 2对p1的最优反应. Max u2(p1, p2)=(a – p2 + bp1 )(p2 – c) subject to 0  p2  +∞ FOC: a + c – 2p2 + bp1 = p2 = (a + c + bp1)/2 Firm 2的最优反应, R2(p1) = (a + c + bp1)/2 Game theory-Chapter 2

49 Sequential-move Bertrand model of duopoly (differentiated products)
解firm 1的问题. 注意到firm 1也能够解 firm 2的问题. Firm 1知道 firm 2对p1的最优反应. 所以, firm 1的问题是 Max u1(p1, R2(p1))=(a – p1 + bR2(p1) )(p1 – c) subject to 0  p1  +∞ 即, Max u1(p1, R2(p1))=(a – p1 + b(a + c + bp1)/2 )(p1 – c) subject to 0  p1  +∞ FOC: a – p1 + b(a + c + bp1)/2+(–1+b2/2) (p1 – c) = p1 = (a+c+(ab+bc–b2c)/2)/(2–b2) Game theory-Chapter 2

50 Sequential-move Bertrand model of duopoly (differentiated products)
子博弈完美纳什均衡 ((a+c+(ab+bc–b2c)/2)/(2–b2), R2(p1) ), 其中 R2(p1) = (a + c + bp1)/2 Firm 1选择价格 (a+c+(ab+bc–b2c)/2)/(2–b2), firm 1选择价格p1时 firm 2选择价格 R2(p1). Game theory-Chapter 2

51 Dynamic games of complete and perfect information
完美信息 在选择下一次行动前可以观察到所有以前的行动. 参与人做出决策前知道谁行动了，干了什么 Game theory-Chapter 2

52 Perfect information: illustration (sequential matching pennies)
Player 1 两个参与人各有一枚硬币. Player 1先选择是显示 Head还是 Tail. 在观察player 1的选择之后, player 2选择显示Head或 Tail 两个参与人都知道以下规则: 如果两枚硬币一致 (都是heads 或都是 tails) 那么player 2 赢得 player 1的硬币. 否则, player 1赢得 player 2的硬币. H T Player 2 Player 2 H T H T -1, 1 1, -1 1, -1 -1, 1 Game theory-Chapter 2

53 Dynamic games of complete and imperfect information
不完美信息 参与人做出决策前可能并不能确切的知道谁做了什么选择. 例: 在player 1做出选择后 player 2进行她的选择. Player 2需要在不知道 player 1做出什么选择的情况下进行她的决策. Game theory-Chapter 2

54 Imperfect information: illustration
Player 1 Player 2 H T -1, 1 1, -1 两个参与人各有一枚硬币. Player 1先选择是显示 Head还是 Tail. 然后player 2在不知道 player 1选择的情况下选择是显示 Head还是 Tail, 两个参与人都知道以下规则: 如果两枚硬币一致 (都是heads 或都是 tails) 那么player 2 赢得 player 1的硬币. 否则, player 1赢得 player 2的硬币. Player 2 Game theory-Chapter 2

55 Information set Gibbons的定义: 参与人的一个信息集是指满足以下条件的决策节的集合:
在此信息集中的每一个节都轮到该参与人行动, 且 当博弈的进行达到信息集中的一个节, 应该行动的参与人并不知道达到了 (或没有达到) 信息集中的哪一个节. 一个信息集中所有的节点都属于同一个参与人 参与人在信息集中的每一个节点都必须有相同的可行行动集合. Game theory-Chapter 2

56 Information set: illustration(pp.94-95)
Player 1 L R Player 2 L’ R’ 2, 2, 3 3 L” R” 1, 2, 0 3, 1, 2 2, 2, 1 0, 1, 1 1, 1, 2 1, 1, 1 two information sets for player 2 each containing a single node an information set for player 3 containing three nodes an information set for player 3 containing a single node Game theory-Chapter 2

57 Information set: illustration
一个信息集中所有的节点都属于同一个参与人 Player 1 This is not a correct information set C D Player 2 Player 3 E F G H 2, 1, 3 3, 0, 2 0, 2, 2 1, 3, 1 Game theory-Chapter 2

58 Information set: illustration
参与人在信息集中的每一个节点都必须有相同的可行行动集合. An information set cannot contains these two nodes Player 1 C D Player 2 Player 2 E F G H K 2, 1 3, 0 0, 2 1, 1 1, 3 Game theory-Chapter 2

59 Represent a static game as a game tree: illustration
囚徒困境 (图 第一个数字是player 1 的收益, 第二个数字是player 2的收益) Prisoner 1 Prisoner 2 Mum Fink 4, 4 5, 0 0, 5 1, 1 Game theory-Chapter 2

60 Example: mutually assured destruction
两个超级大国, 1 和 2, 卷入了一起挑衅事件. 博弈开始于superpower 1的选择，它或者忽视这个事件(ignore, I ), 得到收益 (0, 0), 或者使事态进一步升级 (escalate, E ). superpower 1 使事态升级后, superpower 2可以后退 (back down, B ), 这会使它丧失颜面，获得收益 (1, -1), 或者它可以选择进行核对抗 (atomic confrontation, A ). 这种情况下, 两个超级大国会同时行动，进行以下博弈. 它们或者选择撤退(retreat, R ) ,或者选择末日(doomsday, D ) ,从而世界被毁灭.如果两国都选择撤退，那么它们会忍受一点小的损失，收益为 (-0.5, -0.5). 如果它们有一方选择末日，那么世界将被毁灭，收益为(-K, -K), 其中K是一个很大的数字. Game theory-Chapter 2

61 Example: mutually assured destruction
1 I E 0, 0 2 B A 1, -1 R D -0.5, -0.5 -K, -K Game theory-Chapter 2

62 Perfect information and imperfect information
如果一个动态博弈中每一个信息集只包含一个节，那么这个博弈被称为完美信息博弈. 如果一个动态博弈中有一些信息集包含的节点多于一个，那么这个博弈被称为不完美信息博弈. Game theory-Chapter 2

63 Strategy and payoff 参与人的一个策略是关于行动的一个完整计划.
它明确了在参与人可能会遇到的每一种情况下对可行行动的选择. 它明确了参与人在她的每个信息集选择什么行动 a strategy for player 1: H Player 1 H T Player 2 Player 2 H T H T -1, 1 1, -1 1, -1 -1, 1 a strategy for player 2: T Player 1’s payoff is 1 and player 2’s payoff is -1 if player 1 plays H and player 2 plays T Game theory-Chapter 2

64 Strategy and payoff: illustration
1 I E 0, 0 2 B A 1, -1 R D -0.5, -0.5 -K, -K a strategy for player 1: E, and R if player 2 plays A, written as ER a strategy for player 2: A, R, if player 1 plays E, written as AR Game theory-Chapter 2

65 Nash equilibrium in a dynamic game
我们也可以使用标准式来表述动态博弈 完全信息动态博弈的纳什均衡集就是它的标准式的纳什均衡的集合 怎样在一个完全信息动态博弈中找到纳什均衡 构建完全信息动态博弈的标准式 在标准式中找到纳什均衡 Game theory-Chapter 2

66 Remove nonreasonable Nash equilibrium
子博弈完美纳什均衡（Subgame perfect Nash equilibrium）是纳什均衡的一个精炼（refinement ） 它可以排除不合理的纳什均衡或不可置信的威胁 我们首先需要定义子博弈（ subgame ） Game theory-Chapter 2

67 Subgame 动态博弈树的一个子博弈 始于一个单节信息集 (一个信息集只包含一个节点), 包含这个单节信息集后的所有节点和边缘
没有对任何信息集形成分割；即如果信息集的一个节点属于这个子博弈，那么这个信息集的所有节点也属于 这个子博弈. Game theory-Chapter 2

68 Subgame: illustration
1 I E 0, 0 2 B A 1, -1 R D -0.5, -0.5 -K, -K a subgame a subgame Not a subgame Game theory-Chapter 2

69 Subgame-perfect Nash equilibrium
在动态博弈中，如果一个纳什均衡的策略在该博弈的每一个子博弈中都构成或推导出一个纳什均衡，那么这个纳什均衡是子博弈完美的. 子博弈完美纳什均衡是一个纳什均衡. Game theory-Chapter 2

70 Find subgame perfect Nash equilibria: backward induction
1 I E 0, 0 2 B A 1, -1 R D -0.5, -0.5 -K, -K a subgame Starting with those smallest subgames Then move backward until the root is reached One subgame-perfect Nash equilibrium ( IR, AR ) Game theory-Chapter 2

71 Find subgame perfect Nash equilibria: backward induction
1 I E 0, 0 2 B A 1, -1 R D -0.5, -0.5 -K, -K a subgame Starting with those smallest subgames Then move backward until the root is reached Another subgame-perfect Nash equilibrium ( ED, BD ) Game theory-Chapter 2

72 Find subgame perfect Nash equilibria: backward induction
Player 1 L R Player 2 L’ R’ 2, 2, 0 3 L” R” 1, 2, 3 3, 1, 2 2, 2, 1 0, 0, 1 1, 1, 2 1, 1, 1 哪个是子博弈完美纳什均衡?(R,L’L’,R’’L’’) 子博弈1的NE是（L,’,R’’）,子博弈2的NE是（L’,L’’） Game theory-Chapter 2

73 Bank runs (2.2.B of Gibbons)
两个投资者, 1 和 2, 每人存入银行一笔存款D. 银行已将这些存款投入一个长期项目.如果在该项目到期前银行被迫对投资者变现,共可收回 2r, 这里 D > r > D/2. 如果银行允许投资到期,则项目共可取得 2R, 这里R>D. 有两个日期，投资者可以从银行提款. Game theory-Chapter 2

74 Bank runs: timing of the game
博弈的时间顺序如下 日期 1 (银行的投资项目到期之前) 两个投资者同时行动 如果两个投资者都提款，则每人可得到r，博弈结束 如果只有一个投资者提款，则她可得到D, 另一个投资者可得到2r-D,博弈结束(注意r>2r-D) 如果两人都不提款，则项目结束后在日期2博弈继续. 日期 2 (银行的投资项目到期之后) 如果两个投资者都提款，则每人可得到R ，博弈结束 如果只有一个投资者提款，则她可得到2R-D, 另一个投资者可得到D,博弈结束（注意2R-D>R） 如果两个投资者都不提款，则银行向每个投资者返还R ，博弈结束. Game theory-Chapter 2

75 Bank runs: game tree 1 W: withdraw NW: not withdraw W NW 2 2 Date 1 W NW W NW r, r D, 2r–D 2r–D, D 1 Date 2 W NW a subgame 2 2 One subgame-perfect Nash equilibrium ( NW W, NW W ) W NW W NW R, R 2R–D, D D, 2R–D R, R Game theory-Chapter 2

76 Bank runs: game tree One subgame-perfect Nash equilibrium ( W W, W W )
1 W: withdraw NW: not withdraw W NW 2 2 Date 1 W NW W NW r, r D, 2r–D 2r–D, D 1 Date 2 W NW a subgame 2 2 One subgame-perfect Nash equilibrium ( W W, W W ) W NW W NW R, R 2R–D, D D, 2R–D R, R Game theory-Chapter 2

77 Tariffs and imperfect international competition (2.2.C of Gibbons)
两个完全相同的国家, 1 和 2, 同时选择它们的关税税率,分别记为t1, t2,. 来自country 1的 Firm 1和来自country 2的 firm 2生产同质的产品供给本国消费和出口. 观察到两国的税率后, firm 1 和 2同时选择用于本国消费和出口的产品数量,分别用(h1, e1)和(h2, e2)表示. 两个国家的市场价格Pi(Qi)=a–Qi, for i=1, 2. Q1=h1+e2, Q2=h2+e1. 两个企业的边际成本为常数c. 每个企业在向其他国家出口时都要支付关税. Game theory-Chapter 2

78 Tariffs and imperfect international competition
Game theory-Chapter 2

79 Tariffs and imperfect international competition
Game theory-Chapter 2

80 Backward induction: subgame between the two firms
Game theory-Chapter 2

81 Backward induction: subgame between the two firms
Game theory-Chapter 2

82 Backward induction: whole game
Game theory-Chapter 2

83 Tariffs and imperfect international competition
Game theory-Chapter 2

84 Repeated game 在一个完全信息动态博弈中，同一个（同时行动）的博弈进程至少进行了两次，并且在下一个进程进行前，所有以前的博弈进程都可被观察到，这样的动态博弈就是重复博弈. 我们将探究重复博弈中参与人的行为. Game theory-Chapter 2

85 Two-stage repeated game
两阶段囚徒困境 两个参与人要把以下同时行动博弈重复进行两次 第二次博弈开始前可观察到第一次进行的结果 整个博弈的收益等于两阶段各自收益的加总. 即贴现因子（discount factor）等于1. Question: what is the subgame perfect Nash equilibrium? Player 2 L2 R2 Player 1 L1 1 , 1 5 , 0 R1 0 , 5 4 , 4 Game theory-Chapter 2

86 Game tree of the two-stage prisoners’ dilemma
1 L1 R1 2 2 L2 R2 L2 R2 1 1 1 1 L1 R1 L1 R1 L1 R1 L1 R1 2 2 2 2 2 2 2 2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 Game theory-Chapter 2

87 Informal game tree of the two-stage prisoners’ dilemma
1 L1 R1 2 2 L2 R2 L2 R2 1 1 1 1 (1, 1) (5, 0) (0, 5) (4, 4) L1 R1 L1 R1 L1 R1 L1 R1 2 2 2 2 2 2 2 2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 Game theory-Chapter 2

88 Informal game tree of the two-stage prisoners’ dilemma
1 L1 R1 2 2 L2 R2 L2 R2 1 1 1 1 (2, 2) (6, 1) (1, 6) (5, 5) L1 R1 L1 R1 L1 R1 L1 R1 2 2 2 2 2 2 2 2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 Game theory-Chapter 2

89 two-stage prisoners’ dilemma
子博弈完美纳什均衡 (L1 L1L1L1L1, L2 L2L2L2L2) Player 1在第1阶段 选择 L1, 并且无论第1阶段结果是什么，第2阶段都选择L1. Player 2在第1阶段 选择 L2,并且无论第1阶段结果是什么，第2阶段都选择L2. Player 2 L2 R2 Player 1 L1 1 , 1 5 , 0 R1 0 , 5 4 , 4 Game theory-Chapter 2

90 two-stage prisoners’ dilemma
子博弈完美纳什均衡 (L1 L1L1L1L1, L2 L2L2L2L2) Player 1在第1阶段 选择 L1, 并且无论第1阶段结果是什么，第2阶段都选择L1. Player 2在第1阶段 选择 L2,并且无论第1阶段结果是什么，第2阶段都选择L2. The payoff (1, 1) of the 2nd stage has been added to the first stage game. Player 2 L2 R2 Player 1 L1 2 , 2 6 , 1 R1 1 , 6 5 , 5 Game theory-Chapter 2

91 Finitely repeated game(p.65)
在一个完全信息动态博弈中，同一个（同时行动）的博弈进程至少进行了有限次，并且在下一个进程进行前，所有以前的博弈进程都可被观察到，这样的动态博弈就是一个有限重复博弈. 如果阶段博弈（同时行动博弈）有惟一的纳什均衡，那么这个有限重复博弈有惟一的子博弈完美纳什均衡. 重复博弈的每一阶段都会实现阶段博弈的纳什均衡. Game theory-Chapter 2

92 What happens if the stage game has more than one Nash equilibrium. （p
两个参与人要把以下同时行动博弈重复进行两次 第二次博弈开始前可观察到第一次进行的结果 整个博弈的收益等于两阶段各自收益的加总. 即贴现因子等于1. 问题: 如果M1, M2被选择，我们能够找到一个子博弈完美纳什均衡吗?或者说,两个参与人在一个子博弈完美均衡中能够合作（cooperate ）吗? Player 2 L2 M2 R2 Player 1 L1 1 , 1 5 , 0 0 , 0 M1 0 , 5 4 , 4 R1 3 , 3 Game theory-Chapter 2

93 Informal game tree 1 L1 R1 M1 2 2 2 L2 R2 M2 L2 R2 L2 R2 M2 M2 (1, 1)
(5, 0) (0, 0) (0, 0) (0, 5) (4, 4) (0, 0) (0, 0) (3, 3) 1 L1 M1 R1 2 2 2 L2 R2 M2 L2 R2 L2 R2 M2 M2 (1, 1) (5, 0) (0, 0) (0, 5) (4, 4) (0, 0) (0, 0) (0, 0) (3, 3) Game theory-Chapter 2

94 Informal game tree and backward induction
1 L1 R1 M1 2 2 2 L2 R2 M2 L2 R2 L2 R2 M2 M2 (1, 1) (5, 0) (4, 4) (0, 0) (0, 5) (0, 0) (0, 0) (0, 0) (3, 3) + (1, 1) (1, 1) (3, 3) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) (1, 1) 1 L1 M1 R1 2 2 2 L2 R2 L2 R2 L2 R2 M2 M2 M2 (1, 1) (5, 0) (0, 0) (0, 5) (4, 4) (0, 0) (0, 0) (0, 0) (3, 3) Game theory-Chapter 2

95 Two-stage repeated game
子博弈完美纳什均衡: player 1在第1阶段选择 M1, 如果第1阶段结果是 ( M1, M2 ), 则第2阶段选择 R1 ,如果第1阶段结果不是 ( M1, M2 ), 则第2阶段选择 L1 player 2在第1阶段选择 M2,如果第1阶段结果是 ( M1, M2 ), 则第2阶段选择 R2 ,如果第1阶段结果不是 ( M1, M2 ), 则第2阶段选择 L2 Player 2 L2 M2 R2 Player 1 L1 1 , 1 5 , 0 0 , 0 M1 0 , 5 4 , 4 R1 3 , 3 Game theory-Chapter 2

96 Two-stage repeated game
子博弈完美纳什均衡: 在第1阶段, player 1选择 M1, player 2选择 M2. 在第2阶段, 如果第1阶段结果为( M1, M2 )，则player 1选择 plays R1 ；如果第1阶段结果不是( M1, M2 )，则player 1选择 L1 如果第1阶段结果为( M1, M2 )，则player 2选择 plays R2 ；如果第1阶段结果不是( M1, M2 )，则player 2选择L2 The payoffs of the 2nd stage has been added to the first stage game. Player 2 L2 M2 R2 Player 1 L1 2 , 2 6 , 1 1 , 1 M1 1 , 6 7 , 7 R1 4 , 4 Game theory-Chapter 2

97 An abstract game: generalization of the tariff game(p.56, 64)
四个参与人: 1, 2, 3, 4. 博弈的时间顺序如下. 阶段1: Player 1 和2 同时从可行行动集（feasible action sets ）A1和A2中分别选择行动a1和a2. 阶段2: 在观察到第一阶段的结果(a1, a2)后, Player 3 和4同时从可行行动集A3 和A4中分别选择行动a3 和 a4. 博弈结束. 收益是ui(a1, a2, a3, a4), 对于 i=1, 2, 3, 4 Game theory-Chapter 2

98 An abstract game: informal game tree
player 1 Player 1’ action set A1 a1 Stage 1 player 2 Player 2’ action set A2 a2 player 3 a3 Player 3’ action set A3 Stage 2 player 4 a4 Player 4’ action set A4 A smallest subgame following (a1, a2) Game theory-Chapter 2

99 Backward induction: solve the smallest subgame
Game theory-Chapter 2

100 Backward induction: back to the root
player 1 Player 1’ action set A1 a1 Stage 1 player 2 Player 2’ action set A2 a2 Stage 2 Game theory-Chapter 2

101 Backward induction: back to the root
Game theory-Chapter 2

102 Tariffs and imperfect international competition (2.2.C of Gibbons)
两个完全相同的国家, 1 和 2, 同时选择它们的关税税率,分别记为t1, t2,. 来自country 1的 Firm 1和来自country 2的 firm 2生产同质的产品供给本国消费和出口. 观察到两国的税率后, firm 1 and 2同时选择用于本国消费和出口的产品数量,分别用(h1, e1)和(h2, e2)表示. 两个国家的市场价格Pi(Qi)=a–Qi, for i=1, 2. Q1=h1+e2, Q2=h2+e1. 两个企业的边际成本为常数c. 每个企业在向其他国家出口时都要支付关税. Game theory-Chapter 2

103 Tariffs and imperfect international competition
Country 1 Firm 1 Q1= h1 + e2 P1(Q1)=a–Q1 Stage 1 Stage 2 Country 2 Firm 2 Q2= h2 + e1 P2(Q2)=a–Q2 t1 t2 这个模型适合前面的抽象模型. Country 1 和 2分别是 player 1 和 2 Firm 1 和 2 分别是player 3 和 4 Game theory-Chapter 2

104 Backward induction: subgame between the two firms
Game theory-Chapter 2

105 Backward induction: subgame between the two firms
Game theory-Chapter 2

106 Backward induction: back to the root
Game theory-Chapter 2

107 Tariffs and imperfect international competition
Game theory-Chapter 2

108 重要定义（p.98） 定义 在第2.1.A节定义的完全且完美信息两阶段博弈中，逆向归纳解为（a1*,R2(a1*)），但子博弈完美纳什均衡为（a1*,R2(a1)）。 定义 在第2.2.A节定义的完全且不完美信息两阶段博弈中，子博弈完美解为（a1*,a2*,a3*(a1*,a2*),a4*(a1*,a2*)）,但子博弈完美纳什均衡为（a1*,a2*,a3*(a1,a2),a4*(a1,a2)） Game theory-Chapter 2

109 Multiple subgame-perfect Nash equilibria: illustration
Player 1 C E D Player 2 F G 1, 0 0, 1 Player 2 H I 2, 1 1, 1 Player 2 J K 1, 3 2, 2 子博弈完美纳什均衡(D, FHK). player 1选 D 如果player 1选C ，player 2选 F,如果player 1选D ， player 2选 H,如果player 1选E ， player 2选 K. Game theory-Chapter 2

110 Infinitely repeated game
在一个完全信息动态博弈中，如果一个同时行动博弈（被称为阶段博弈）进行无限次，并且上一阶段博弈的结果在下一阶段博弈进行前可以被观察到，那么这个完全信息动态博弈就是一个无限重复博弈. 就是说,在阶段 1, 2, 3, ..., t-1, t, t+1, 进行同时行动博弈。前t-1 阶段的所有结果在第t阶段时都可以被观察到. 每个参与人都会用一个贴现因子进行贴现，这里0<  < 1 重复博弈中参与人的收益是参与人从每阶段博弈中获得的收益的现值. Game theory-Chapter 2

111 Present value Game theory-Chapter 2

112 Infinitely repeated game: example
下面的同时行动博弈是无限重复博弈 下一次博弈开始前所有以前的博弈结果都可以被观察到 无限重复博弈每个参与人的收益是她所有阶段得到的收益的现值. 问题: 子博弈完美纳什均衡是什么? Player 2 L2 R2 Player 1 L1 1 , 1 5 , 0 R1 0 , 5 4 , 4 Game theory-Chapter 2

113 Example: subgame 无限重复博弈的每个子博弈等同于整个博弈. 1 L1 R1 2 2 L2 L2 R2 R2 (1, 1)
(5, 0) (0, 5) (4, 4) 无限重复博弈的每个子博弈等同于整个博弈. Game theory-Chapter 2

114 Example: strategy 参与人的策略是一个完整的计划.它依赖于博弈进行的历史.
player i的一个策略: 在每个阶段（或者每个信息集）选择Li player i的其他策略被称为触发策略（trigger strategy ）:在第1阶段选择 Ri； 如果以前所有t-1 阶段的结果均为(R1, R2) ，那么第t阶段选择Ri ，否则第t阶段选择Li. Game theory-Chapter 2

115 Example: subgame perfect Nash equilibrium
检查一下，如果player i 在每一阶段（或者她的每个信息集）都选择Li，这是否是一个子博弈完美纳什均衡. 这可以分以下两步进行. 第1步: 检查这个策略组合是否是无限重复博弈的一个纳什均衡. 如果player 1每个阶段都选择 L1,那么 player 2每个阶段的最优反应都是选择 L2. 如果player 2每个阶段都选择 L2, 那么player 1每个阶段的最优反应都是选择 L1. 所以,它是无限重复博弈的一个纳什均衡. Game theory-Chapter 2

116 Example: subgame perfect Nash equilibrium cont’d
第2步:检查这个无限重复博弈纳什均衡是否在无限重复博弈的每个子博弈中都能推导出一个纳什均衡. 回忆一下：无限重复博弈的每一个子博弈等同于无限重复博弈总体 显然,在每一个子博弈中它都能推导出一个纳什均衡 所以, 它是一个子博弈完美纳什均衡. Game theory-Chapter 2

117 Example: subgame 1 L1 R1 2 2 L2 R2 L2 R2 1 1 1 1 (1, 1) (5, 0) (0, 5)
(4, 4) L1 R1 L1 R1 L1 R1 L1 R1 2 2 2 2 2 2 2 2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 TO INFINITY Game theory-Chapter 2

118 Trigger strategy player i的触发策略:在第1阶段选择 Ri； 如果以前所有t-1 阶段的结果均为(R1, R2) ，那么第t阶段选择Ri ，否则第t阶段选择Li. 检查一下每个参与人都采取触发策略是否存在一个子博弈完美纳什均衡. 这可以分以下两步进行. 第1步: 检查触发策略组合是否是无限重复博弈的一个纳什均衡 第2步: 如果是,检查这个纳什均衡是否在每一个子博弈中都可以推导出一个纳什均衡 Game theory-Chapter 2

119 Trigger strategy: step 1
Stage 1: (R1, R2) Stage 2: (R1, R2) Stage t-1: (R1, R2) Stage t: (R1, L2) Stage t+1: (L1, L2) Stage t+2: (L1, L2) Game theory-Chapter 2

120 Trigger strategy: step 1 cont’d
Stage 1: (R1, R2) Stage 2: (R1, R2) Stage t-1: (R1, R2) Stage t: (R1, L2) Stage t+1: (L1, L2) Stage t+2: (L1, L2) Game theory-Chapter 2

121 Trigger strategy: step 2
Stage 1: (R1, R2) 第2步:检查这个纳什均衡是否在无限重复博弈的每一个子博弈中都可以推导出一个纳什均衡. 回忆一下：无限重复博弈的每一个子博弈等同于无限重复博弈总体 Stage 2: (R1, R2) Stage t-1: (R1, R2) Stage t: (R1, R2) Stage t+1: (R1, R2) Stage t+2: (R1, R2) Game theory-Chapter 2

122 Step 2 cont’d: subgame 1 L1 R1 2 2 L2 R2 L2 R2 1 1 1 1 (1, 1) (5, 0)
(0, 5) (4, 4) L1 R1 L1 R1 L1 R1 L1 R1 2 2 2 2 2 2 2 2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 L2 R2 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 1 1 5 0 0 5 4 4 TO INFINITY Game theory-Chapter 2

123 Trigger strategy: step 2 cont’d
我们有两类（classes ）子博弈: 前面所有阶段的结果都是(R1, R2)之后的子博弈 前面至少有一个阶段的结果不是(R1, R2)之后的子博弈 对第一类子博弈来说，无限重复博弈纳什均衡推导出一个纳什均衡，此时每个参与人仍然选择触发策略 对第二类子博弈来说，无限重复博弈纳什均衡推导出一个纳什均衡，此时参与人永远选择(L1, L2). Game theory-Chapter 2

124 相关重要定义（p.72-p.74） 策略：在有限重复博弈G(T)或无限重复博弈G(∞,δ)中，参与人的一个策略特指在每一阶段，针对其前面阶段所有可能的进行过程，参与人将会选择的行动。 Game theory-Chapter 2

125 相关重要定义（继续） 子博弈：在有限重复博弈G(T)中，由第t+1阶段开始的一个子博弈为G进行T-t次的重复博弈，可表示为G(T-t)。由第t+1阶段开始有许多子博弈，到t阶段为止的每一可能的进行过程之后都是不同的子博弈。在无限重复博弈G(∞,δ)中，由t+1阶段开始的每个子博弈都等同于初始博弈G(∞,δ)，和在有限情况相似，博弈G(∞,δ)到t阶段为止有多少不同的可能进行过程，就有多少从t+1阶段开始的子博弈 Game theory-Chapter 2

126 相关重要定义（继续） 子博弈完美纳什均衡：如果参与人的策略在每一子博弈中都构成纳什均衡，我们则说纳什均衡是子博弈完美的。
Game theory-Chapter 2