博弈论完全信息动态博弈

1、学术型博弈论杜少甫sdu第2章完全信息动态博弈ý 完全信息静态博弈vs 完全信息动态博弈F 信息：completev 局中人、策略集、支付函数均为共同知识F 出手顺序：v静态：同时出手，或不清楚先后顺序v动态：先后出手2School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve C

2、hina博弈的扩展式表述ý策略式表述(Strategic Form)F 用<N, (Si), (Ui)>三元组来描述博弈F 没有显式反映出手时间（隐含在策略集中），更适用于静态博弈。ý扩展式表述(Extensive Form)FF将历史集、信息集等引入，更适用于动态博弈常用树状图几何表示博弈树(Game Tree)vvv局中人出手的顺序局中人的行动空间(action set)局中人出手时所拥有的信息3School of Management, University of Science and Technology of China © 2015/10

3、/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý例：田忌赛马F典型的动态博弈F隐含假设：齐威王先出手，田忌观察后出手。F注：由于前两次选定后，第三次就已确定，相当于分别两次出手。F零和博弈è支付可用田忌的净胜局数表示。齐312田111333222齐3332222311田33231323131131212213-13211-3 -1 -1-3 -1 -1 -1 -1 1 -1 -1

4、 1-14School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)低需求情形高需求情形ý例：房地产开发博弈é-3, -3é4, 48, 0ùú1, 0 ùFF局中人：两开发商A、B

5、4;0, 0úê0,1市场需求可能为“高”，也可能为“低”ë0,80, 0ûëûvv若无人开发，谁也不知道市场需求具体是什么若有人开发，后面的人可能会观察到市场需求F/状态不被完全了解时中人对博弈中某vvv凭借经验、通过调研等方式去“猜”在一定程度上，“听天由命”、“顺其自然”、“神助”/状态完全无法当人对某时，往往采取等概率处理F虚拟局中人(quasi-player)“自然(nature, NA)” or “神(god)”vv假设高、低需求的自然概率分别为1/2牛顿晚年：“宇宙第一原动力”，“引力解释了行星的运动，但却不能解释谁让行

6、星运动起来的。上帝万物，知晓所有做过和能做的事。”5School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)F 行动顺序：v开发商A先行动：“开发D”与“不开发U” ；v自然选择市场需求：“高H”与“低L”；v开发商B观测到A的行动及市场需求情况，

7、再行动。AUD不动路径对应不同支付向量NaNaHBLHBLBBUD(4, 4)UU(1, 0)D(0, 8)DUD(8, 0)(-3, -3)(0, 0) (0,1)(0, 0)6School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý

8、 博弈树F 结点(node)：v 决策结点(decision node) 局中人采取行动的时点 初始结点(initial node)为树根；v 终端结点(terminal node) 博弈行动路径的终点 è 标注支付向量。F 枝(branch)：v 每一枝代表局中人在出手时点的可选行动。7School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to dev

9、elop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 博弈树（续）F 信息集(information set)：v 对于某一特定的局中人而言，所谓信息集就是能够回答以下问题 的某种集合，即：当博弈进行到某个阶段的时候，根据已观察到的情况，局中人所了解的博弈已发生的所有可能行动 In game theory, an information set is a set that, for a particular player, establishes all the possible moves that could have t

10、aken place in the game so far, given what that player has observed so far8School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý博弈树的结点FFX：博弈树所有结

11、点的集合。：定义于X上的二元优先关系(precedence relation)vx1,x2X， x1x2表示“结点x1处在x2之前”，此关系满足非自反性(irreflexivity)： xX， xx不成立传递性(transitive)： x1,x2,x3X， 若x1x2， x2x3，则x1x3不对称性(asymmetric)： x1,x2X,若x1x2， 则x2x1不成立称性(antisymmetry) vs 不对称性注：if a b and b a then a = bvè是严格偏序关系(strict partial order)F注：并非X内任意两结点间均是可比较的v 不动路径上

12、的结点不可比较。9School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 博弈树的结点F 前趋(predecessor)：v对于xX， x'X满足x' x，称x'是x的一个前趋v前趋集：P(x)=x'|

13、 x' x, x'XvP(x)=Ø à x为初始结点v直接前趋(immediate predecessor)：某结点直接相连的前趋结点 xX，若存在一个x*P(x)，对于x' P(x), x'x*，均有 x' x*，则称x*为x的直接前趋。直接前趋记为p(x)10School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and prac

14、tice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 博弈树的结点F 后继(successor)：v对于xX， x'X满足x x'，称x'是x的一个后继v后继集：T(x)=x'| x x', x'XvT(x)=Ø à x为终点结点v直接后继(immediate successor)：某结点直接相连的后继结点 xX，若存在x* T(x)，使得p( x*)= x ，则称x*为x的直接后继。 一个结点的后继结点可有多个，x的所有直接后继的集合

15、记为t(x)11School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý博弈树的结点F 初始结点未必唯一，但可转换成一个等价的单初始结点博弈树。F 方法：引入虚拟局中人“自然Na”F 例：ANaAAABBBBBBBB可以假定博弈树初始结

16、点唯一12School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý博弈树性质F有向图(Digraph)：任一枝均是个有向边，自上而下F有闭环(传递性不对称性)不F所有非初始结点的入度(InDegree)为1，出度(OutDegree)

17、为可选择的行动数。v入度直接前趋数 ó 非初始结点的直接前趋唯一v出度直接后继数v非初始结点x入度为1 ó 前趋集P(x)是全序集(totally-ordered set)x1,x2P(x)，则x1 x2和x2 x1有且只有一个成立。前趋集P(x)一条链(Chain)××·13School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and pr

18、actice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý行动顺序的表述F在决策结点中标注局中人（包括“自然”）v 可记局中人集合为N=1,n；自然为0，用N+0= 0,1,n表示包括虚拟局中人在内的所有局中人。x0F函数表述i: XàN+00vi(x)即为在决策结点x处出手的局中人x12x1111v以下图博弈树为例：x22x23x24x21222214School of Management, University of Science and Technology of China 

19、9; 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 支付函数的表述F 博弈树的每个终端结点z唯一决定了某条博弈路径v 关系是严格偏序的(传递性、不对称性)v 任何结点的前趋集是全序的F 可用终端结点z来表示z对应的博弈路径F U(z)=(u1(z), un(z)：博弈路径z所导致的支付向量。15School of Management, University of Sci

20、ence and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 信息集(Information Set)F 对于某一特定的局中人而言，所谓信息集就是能够回答 以下问题的某种集合v 当博弈进行到某个阶段的时候，根据已观察到的情况，局中人所了解的博弈可能已发生的所有可能行动F 在扩展式表述中，通常信息集被定义为局中人出手时

21、的结点集合，因为这样的结点集合可回答上述问题16School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý例：开发动态博弈AUDRightLeftNaNaHBLHBLx32U(1, 0)x31D(4, 4)x34Ux33D(0,8)BBU

22、UDD(8, 0)(-3, -3)(0, 0) (0,1)(0, 0)1. 若在局中人B出手的时候，他清楚地知道在此之前局中人A和虚拟局中人“自然”的行动，那么他就能准确地知道处在博弈树第三层(阶段)的哪个决策结点上此次出手时，局中人B有四个信息集，每个信息集中只有一个决策结点；2. 若局中人B出手的时候，他知道局中人A的行动但不知道“自然选择”，那么他能当前是处在博弈树的Left(x31和x32)还是Right(x33和x34)，但却分不清够知道“x31与x32”或“x33与x34”。这些无法被局中人B区分的结点放在一起集，即此时局中人B的信息集有两个：x31, x32和x33, x34一个

23、信息17School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 信息集(Information Set)F 信息集是决策结点(状态)的集合信息集反映了局中人每次出手时对已发生的情况所掌握的程度v集合中的每个结点对应于某一局中人v中人达

24、到信息集时，局中人无法对信息集中结点加以区别 局中人只知道博弈是否到达信息集中某决策结点(状态)，但却并不确知究竟哪一个。 当信息集中有多个结点时，局中人无法具体哪个结点(状态)当前到达信息集中18School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Con

25、t.)ý 信息集(Information Set)F 完美信息(perfect information)：v在某时点局中人能确定处于某一结点(状态)v信息集只包含一个结点单结点信息集F美信息(imperfect information)：v局中人不能准确的精确位置(状态)。之前所发生的事，故不了解当前在博弈树中v信息集包含多个结点多结点信息集19School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enric

26、h theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý 例：F 假设战博弈女FootballOpera先出手FOv完美信息：女方出手时确知已采取的行动Nd0男信息集：Nd0女方信息集：Nd1和Nd2完美信息OFNd1Nd2O女女OFF(0, 0)(0, 0)(2,1)(2,1)20School of Management, University of Science and Technology of China © 2015/10/13To generate

27、ideas and tools to enrich theory and practice, to develop talents and leaders to serve China男2, 10, 00, 01, 2博弈的扩展式表述(Cont.)ý 例：v战博弈美信息：女方出手时不知道已采取的行动信息集：Nd0女方信息集：Nd1, Nd2习惯在博弈树上用虚线将同一信息集下的结点相连Nd0美信息男O在本例中，此美信F息动态博弈事实上就是一个静态博弈Nd1Nd2O女女OFF(0, 0)(0, 0)(2,1)(2,1)21School of Management, University

28、of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)例：房地产开发博弈ýNd0DANdA0UUDNdNdNd11NaNd1211Na12NaNaHLHLHBLHNdLNdB Nd22UNd23D(0,8)B Nd24U(0, 0)Nd21D(4, 4)Nd24U21BBNdBB23UB22UD(4,

29、 4)UDDUU(1, 0)D(0,8)DD(8, 0)(-3, -3) (1, 0)(0, 0) (0,1)(8, 0) (-3, -3)(0, 0) (0,1)(0, 0)若开发商B出手时确知A的行动，但不知道自然选择（即市场需求情况）B的信息集：Nd21, Nd22和Nd23, Nd24确知自然选择，不了解A的行动B的信息集：Nd21, Nd23和Nd22, Nd2422School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and too

30、ls to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý信息集FFFH：信息集的集合h：某一特定信息集 hH。h(x)：含有决策结点x的信息集若两结点x, x'同属一个信息集，即 x, x'h ó x'h(x), xh(x')，则xP(x')， xT(x')； x'P(x)， x'T(x) 同一信息集内的决策结点不互为前趋、后继i(x)=i(x') 同一信息集内的决策结点

31、同属一个局中人记A(.)为决策结的行动空间，A(x)=A(x') 同一信息集内的决策结点的行动空间一致 可通过前面例子验证vvv故只需信息集定义行动空间，可引入A(h)表示信息集h的行动空间。23School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(

32、Cont.)信息集ý虚拟局中人“自然”的信息集总可认为是单结点的自然在局中人后行动 ó 自然在局中人前行动，但未被观察到v 自然选择是随机的（可能服从某种概率分布）ANaUDLHNaNaAAHBLDUHBLDUBBBBBBUD(4, 4)U(1, 0)UD(0, 8)DUUDD(4, 4)UU(1, 0)D(0, 8)DUD(8, 0)(-3, -3)(0, 0) (0,1)(0, 0)(8, 0)(-3, -3)(0, 0) (0,1)(0, 0)完美信息博弈形式美信息博弈形式注：同一博弈可通过不同博弈树表述24School of Management, Universi

33、ty of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China博弈的扩展式表述(Cont.)ý静态博弈的扩展式表述F局中人同时出手F博弈树可从任何一个局中人的决策结点开始F局中人出手时互不了解行动选择 è 每个局中人只有一个信息集F例：徒困境A招供B沉默招供沉默AABB招供沉默招供沉默招供沉默招供沉默(0, -8) (-8

34、, 0)(-1, -1)(-8, 0) (0, -8)(-5, -5)(-1, -1)(-5, -5)25School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China完美记忆(Perfect Recall)ý完美记忆：每个局中人均忘记以前已获取的任何信息。F每个局中人能牢

35、记先前已采取过的行动；F每个局中人能牢记先前已掌握的事情。vPerfect recall refers to the assumption that, at every opportuto act, each Playerremembers what he did in prior moves, and each player remembers everythingthat he knew before. Effectively, the assumption is one that players never forgetinformation once it is acquired ()

36、ý完美信息：每个局中人在任一行动时点均了解博弈所有以往的历史F 博弈树中每个结点都是一个信息集F出现多个局中人同时出手的情况v注：若博弈中出现多个局中人同时出手情形，事实上可转换为美信息博弈。完美信息必然完美记忆，完美记忆未必完美信息26School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders t

37、o serve China关于完美记忆的例子AADDUUBBBBRARRARLLALLAAAAA美记忆第一次出手采取的行动完美记忆但美信息A第二次出手时忘记了A第二次出手时仍记得以前的出手，但不了解B所采取的行动ADUBBRARLLAAA在下围棋或时，参与者BBBBBBBB经常会忘记以前的行动美记忆B在第一次出手时知道A第一次出手时的选择；但在第二次出手时却把这一信息忘记了27School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and too

38、ls to enrich theory and practice, to develop talents and leaders to serve China扩展式博弈的Nash均衡Aý例：质量选择博弈(Turocy & vonStengel, 2001)高低F局中人A：服务供应商；局中人B：服务消费者BBv局中人A先出手，选择提供高/低质量的服务不买买不买买v局中人B根据局中人A的选择，决定买或不买(2, -0.5) (0, 0)(1, 0)(1.5, 2)F双方策略集：vSA高，低； SB(买，买)，(买，不买)，(不买，买)，(不买，不买)vè先出手者不了解后

39、出手者选择策略行动vè在完美信息动态博弈中，后出手者了解先出手者选择策略行动v后出手者的策略：先出手者的不动均有相应的应对行动策略（x，y）ó sA=高? x : y28School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China扩展式博弈的Nash均衡

40、3;例：质量选择博弈(Turocy & vonStengel, 2001)AF用策略式博弈的双矩阵表述高低BB不买买不买买(2, -0.5) (0, 0)(1, 0)(1.5, 2)Nash均衡1.2.策略组合：(高, (买, 不买) 和 (低, (不买, 不买)行动组合： (高, 买)、 (低, 不买)可见：策略式博弈的分析方法同样适用于动态博弈29School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enr

41、ich theory and practice, to develop talents and leaders to serve China(买，买)(买，不买)(不买，买)(不买，不买)高1.5, 21.5, 20, 00, 0低2, -0.51, 02, -0.51, 0扩展式博弈的Nash均衡ý 逆向归纳法(Backward Induction)F又称“Kuhn方法”F适用对象：完全且完美信息动态博弈vPerfect： 后出手者了解历史 最后出手者无后续阶段牵制，能够作出准确的选择；vComplete： 所有局中人的策略、支付为共同知识 先出手者虽然不知道后出手者的具体行动，但

42、却知道后出手者对己方行动的反应，及其所带来的支付30School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China扩展式博弈的Nash均衡ý 逆向归纳法(Backward Induction)F从树叶向树根方向逆推：v 枝加粗：由粗树枝形成的行动路径为均衡路径v 剪枝：完整

43、的行动路径为均衡路径AA高高低低BBBB不买买不买买不买买不买买(2, -0.5) (0, 0)(1, 0)(2, -0.5) (0, 0)(1, 0)(1.5, 2)(1.5, 2)博弈Nash均衡(用行动组合表示)：（高，买）思考：为什么用策略式博弈的双矩阵划线法与用扩展式博弈的逆向归 纳法得出的结果有所不同？31School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practi

44、ce, to develop talents and leaders to serve China扩展式博弈的Nash均衡在于：ý“扩展式表述ó策略式表述”并不意味着“博弈树ó双矩阵”v在静态博弈中，双矩阵能够反映策略式博弈的全部信息(局中人、策略、支付)；v而在动态博弈中，双矩阵丢失了部分博弈信息(策略部分)双矩阵中所列的“策略”虽能够反映后出手者对先出手者的应对方案；却丢失了各方出手顺序的信息，即：没反映出“后出手者能够观察到先 出手者的行动，并将应对方案付诸实施”双矩阵中，型如(买，不买)这样的动态策略被静态化了。NE(逆向归纳法) NE(划线法)32Sch

45、ool of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China扩展式博弈中的策略ý参数符号FHi：局中人i的信息集集合；hiHi为某一信息集；FAi:局中人i的所有可选行动集合；局中人i在信息集hi下的可选行动集A º UA(h )iihi ÎHiF局中人i的

46、每一个纯策略都是从信息集到行动集的ó反映了处于某信息: Hi ® Aisi集的局中人如何行动A= Õhi ÎHi高SA(h )低iiF局中人i的纯策略空间：BB不买买不买买(2, -0.5) (0, 0)(1, 0)(1.5, 2)33School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and trich theory and practice, to develop talents and leade

47、rs to serve China行为策略Behavioral Strategyý前文提到，同一信息集内决策结点的行动空间一致，故只需考虑每个信息集所对应的行动空间即可ý行为策略(Behavioral Strategy)F局中人对的每个信息集所对应的所有可能行动所赋予的某一概率分布，且不同信息集下相互vA behavioral strategy assigns to each information set of a player a probabilitydistribution over the actions available at this information

48、 setHi = hi1 ,L, hik F假设局中人i有k个信息集，信息集的集合为A(h ) = a ,L, a 1Lv其任一信息集hij对应的行动空间就为A(hij)，假设ijijijv局中人在此行动空间上设定一个概率分布bij，反映出他在此信息集下的行动态度Î ìüLå( p ,L, p ) | p³0, l = 1,L, L,p= 1ý1Lllbijíijijijijîþl =1= (bi1 ,L, bik )则局中人i的某一行为策略可表示为biv34School of Management, U

49、niversity of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China行为策略 Behavioral Strategyý动态博弈的行为策略的内涵类似于静态博弈的混合策略Aý右图描述了局中人A和B的一种行为策略F 局中人A有一个信息集，行为策略(0.3, 0.7)0.30.7高低BB0.5不买0.5买0.6不买0.4买

50、F 局中人B有两个信息集，行为策略(0.5, 0.5),(0.6, 0.4)(2, -0.5) (0, 0)(1, 0)(1.5, 2)ý定理4.1 (Kuhn, 1953)：在完美记忆博弈中，行为策略等价于混合策略。F 关于Kuhn定理和行为策略，见附录4.1ý本课程只简单介绍行为策略概念，着行为策略的更深入讨论略。35School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theor

51、y and practice, to develop talents and leaders to serve China扩展式博弈的简化策略式ý 例图博弈F 局中人A第一次出手为U时，博弈结束F 出手为D时，马上又与局中人B展开一个静态博弈ADU为方便起见，可用局中人的各次行B动的向量来描述纯策略RLAèA有四个纯策略(U,u),(U,d),(D,u),(D,d)Audud36School of Management, University of Science and Technology of China © 2015/10/13To generate id

52、eas and tools to enrich theory and practice, to develop talents and leaders to serve China扩展式博弈的简化策略式ý定义：两个纯策略是等价的，若它们在其他局中人所有纯策略下都能产生相同的结果(结果分布)。F 显然，若局中人A第一次出手选择了U，那么他的第二阶段信息集是 不可达的，因而(U,u)和(U,d)是等价的ý扩展式博弈的简化策略式就是将等价纯策略合并（只保留一个而舍弃其他）而得到的。F 简化后，局中人A的(U,u)和(U,d)可合并为(U,u)或(U,d)或直接用UA只有三个纯策略

53、U,(D,u),(D,d)37School of Management, University of Science and Technology of China © 2015/10/13To generate ideas and tools to enrich theory and practice, to develop talents and leaders to serve China承诺与威胁ý动态博弈中先出手局中人是否应该相信后出手局中人的某种行动选择？à性问题F 承诺(Promise)：若后出手局中人选择的某一行动对先出手局中人是有利的，则此行动选择对先出手局中人来说是一种“承诺”；F 威胁(Threat)：若不利的，则“威胁”ý定义：F 某一局中人发出一个