第三章完全信息动态博弈

第三章完全信息动态博弈DynamicGamesofCompleteInformation@2009ZhengDaowen,AllRightsReserved动态博弈：参与人的行动有先后顺序，且后行动者在自己行动之前能观测到先行动者的行动。第一节博弈的扩展式表述一、博弈的战略式表述与扩展式表述的区别–博弈的战略式表述只包括三个要素–扩展式表述包括以下六个方面的要素扩展式表述包括以下六个方面的要素：–参与人集合：i=1、2、…，n；并且用大写N代表虚拟的参与人——“自然”；–参与人的行动顺序(Theorderofmoves)：谁在什么时候行动；–参与人的行动空间（Actionset）：在每次行动时，参与人有些什么选择；–参与人的信息集(Informationset)：每次行动时，参与人知道些什么；–参与人的支付函数：在行动结束后，每个参与人得到些什么；–外生事件（即自然的选择）发生的概率。二、博弈树假定在某个城市，有两家房地产商A、B，各自准备开发一栋同等规模的写字楼，需要投资都是1亿元。市场调查表明：如果两栋楼同时出售，市场需求大时，每栋售价1.4亿；需求较小时，每栋售价7千万。如果市场上只有一栋楼出售，需求较大时，售价为1.8亿，需求小时，售价为1.1亿。ANN小大1/2BB大不开发不开发不开发不开发不开发开发开发开发开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)开发BB1/2小1/21/2图2.1房地产开发博弈（一）博弈树的构件1、结(nodes)–分类：决策结(decisionnodes)；终点结(terminalnodes)。–特性：•传递性(transitive)：x1x2，x2x3;→x1x3。•不对称性(asymmetric):x1x2;x2≮x1。•半序的(partialorder)或局部有序的。xx′x″–前列集(thesetofpredecessors)•用P(x)表示–后续集(thesetofsuccessors)•用T(x)表示2、枝(branches)–枝是从一个决策结到它的直接后续结的连线；–每一枝代表参与人的一个行动选择；–可选择的行动集合A(x)和该结点的直接后续集合t(x)之间存在一一对应关系。3、信息集(informationsets)Playeri’sinformationsetatanyparticularpointofthegameisthesetofdifferentnodesinthegametreethatheknowsmightbetheactualnode,butbetweenwhichhecannotdistinguishbydirectobservation.–同一信息集，同一参与人；–在同一信息集合中，参与人不知道自己究竟处于哪个决策结。单结信息集(singletons)和多结信息集。（二）同一信息集的表示方法–用博弈树来表述–用数学式表述ANN小大1/2BB大不开发不开发不开发不开发不开发开发开发开发开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)开发BB1/2小1/21/2同一信息集的表示法：知道参与人A的选择，但不知道自然的选择ANN小大1/2BB大不开发不开发不开发不开发不开发开发开发开发开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)开发BB1/2小1/21/2同一信息集的表示法：知道自然的选择，但不知道参与人A的选择用数学式表述–H代表所有信息集的集合；–h代表一个特定的信息集，即h∈H；–h(x)表示包含决策结x的信息集，它表示在x点决策的参与人i不确定他是处在x，还是处在其它x’∈h(x)。如果x’∈h(x)，那么x∈h(x’)。同一信息集满足下列条件：)()()3()()()2()(),()1(xAxAxixixPxxPx且（三）完美信息动态博弈完美信息博弈(Gameofperfectinformation)–是指所有信息集都为单结的博弈，完美信息博弈意味着在博弈中没有任何两个人同时行动，并且所有后行动者能确切地知道前行动者选择了什么行动，所有参与人都能观测到自然的选择或行动。（四）参与人在博弈树中的顺序1、排序的基本原则一个参与人在决策之前知道的事情必须出现在该参与人的决策结之前。2、自然人的排序–如果参与人不能观测到虚拟人——自然的行动，自然的决策结置于该参与人的前后都一样；–自然的信息集总是假定为单结。NAA小BB大不开发不开发不开发不开发不开发开发开发开发开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)BB1/21/2开发不开发开发NBB小AA大不开发不开发不开发不开发不开发开发开发开发开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)AA1/21/2开发不开发开发(-8,-8)(0,-10)(-10,0)(-1,-1)ABB抵赖抵赖抵赖坦白坦白坦白(-8,-8)(0,-10)(-10,0)(-1,-1)BAA抵赖抵赖抵赖坦白坦白坦白（五）完美回忆完美回忆（Perfectrecall）是指没有参与人会忘记自己以前知道的事情，所有参与人都知道自己以前的选择。完美记忆应满足以下要求：如果:(1)x2∈h(x1)，即x2和x1属于同一信息集；(2)x∈P(x1)，即x是x1的前列集；(3)i(x)=i(x1)，即x和x1都是i的决策结；那么，存在一个x″(也可能是x本身)，满足下列关系：x″∈h(x);x″∈P(x2);在x点为到达x1的行动同在x″点为达到x2的行动一样。参与人记住以前知道的所有事情。xx″x1x2DDUU11反映完美记忆的要求参与人不具有完美记忆的两例子N11DDUU12LLRR参与人1不记得自己前面的选择。不满足同一行动假设。参与人1在第一次决策时知道自然的选择，但是在参与人2行动后，参与人1再次选择时却忘记了自然最初的选择。不满足同一信息假设。两个决策结对应两个信息集122DRRULL1第二节扩展式表述的纳什均衡一、动态博弈的纯战略式表述A(-3,-3)(1,0)(0,1)(0，0)BB不开发不开发不开发开发开发开发开发否，开发开发，开发；不开发，不开发开发，不开发；不开发，开发开发否，不开发开发-3，-3-3，-31，01，0不开发0，10，00，10，0厂商B厂商A相关代号：si---纯战略，是参与人i相机行动的计划ui---支付函数。hk+1---thehistoryattheendofstagek,whichisthesequenceofactionsinthepreviousperiods:hk+1=(a1,a2,……,ak)Hi为第i个参与人的信息集的集合参与人i的行动集合。在信息集hi的行动集合。si:Hi→Ai参与人i的一个纯战略是从信息集合Hi到行动集合Ai的一个映射。Si在每一个信息集hi上的行动空间A(hi)的笛卡尔积(CartesianProduct)。)(iHhihAAii)(ihA)(iHhihASii＃Si表示参与人i可选择的纯战略的总数所有参与人的一个纯战略组合s=(s1,…，si,……，sn)决定了博弈树上的一个路径。每一个战略组合（即博弈树上的一个路径）决定一个支付向量u=(u1,…,un)iiHhi)A(hSi＃＃（一）纯战略均衡如果对于任意一个参与人i，si*使ui(si，s*-i)取得极大值，即那么，战略组合s*是扩展式博弈的一个纳什均衡。issusiiSsiii),,(maxarg**（二）行为战略均衡1、“行为战略”（behaviorstrategies）是指参与人在每一信息集上随机地选择行动的概率。一个行为战略规定了对应每一个信息集的行动集合上的概率分布，且不同信息集上的概率分布是独立的。bi表示参与人i的一个行为战略。△(A(hi))表示在行动集合A(hi)上的概率分布))((iHhihAbii△2、行为战略纳什均衡：如果对于，没有任何参与人可以通过选择其它行为战略增加自己的期望效用，则就是一个行为战略纳什均衡。),,(**1*nbbb),,(**1*nbbb1h″22hDULLRR四个纯战略：{L,L},{L,R},{R,L},{R,R};行为战略：b2={(1/2,1/2),(1/2,1/2)};设混合战略为：σ2=（σ21,σ22,σ23,σ24）3、等价性定理（Kuhn,1953）：在完美回忆博弈中，任何混合战略σi等价于一个唯一的行为战略bi，任何一个行为战略bi等价于每一个从该行为战略构造的混合战略σi。σi（ai│hi）表示参与人i在信息集hi选择行动ai的概率。4、定理(Zermelo,1913;Kuhn,1953):任何一个有限的完美信息博弈都有一个纯战略纳什均衡。12DU(2,2)L(3,1)R(0,0)用逆向归纳法(Backwardinduction)求解LRU2,22,2D3,10,0参与人2参与人1第三节子博弈完美纳什均衡一、动态博弈中的子博弈子博弈(Subgame)是指在一个用扩展式表述的多阶段动态博弈中，从某个阶段或决策结开始的后续阶段构成的博弈。它必须有一个初始信息集，且具备进行博弈所需要的各种信息。定义：一个扩展式博弈的子博弈G由一个决策结x和所有该决策结的后续结T(x)（包括终点结）组成，它满足下列条件：（1）x是一个单结信息集，即h(x)={x}（2）对于所有的x1∈T(x),如果x＂∈h(x1)，那么x＂∈T(x)二、逆向归纳法(BackwardInduction)它就是从动态博弈的最后一个阶段或最后一个子博弈开始，逐步向前倒退以求解动态博弈的方法。它是重复剔除劣战略方法在扩展式博弈上的应用或扩展：从最后一个决策结开始依次剔除掉每个子博弈的劣战略，最后生存下来的战略组合即为一个纳什均衡。三、子博弈完美纳什均衡SubgamePerfectNashEquilibrium1、定义：如果动态博弈中各参与人的战略在动态博弈本身和所有子博弈中都构成一个纳什均衡，则称该战略组合为一个子博弈完美纳什均衡。),,,,(***1*nissss如果扩展式博弈的战略组合，（1）是原博弈的纳什均衡；（2）是在每一个子博弈上的纳什均衡，那么，它就是一个子博弈完美纳什均衡。构成子博弈纳什均衡的战略不仅在均衡路径的决策结上是最优的，而且在非均衡路径的决策结上也是最优的。四、承诺行动与子博弈纳什均衡“承诺行动”(commitment)是指为改变博弈结果而采取的措施。一个参与人通过某项措施减少自己的选择机会，以保证自己不选择某些行动，从而改变竞争对手的最优选择，这样的措施即是完全承诺(totalcommitment)，如“破釜沉舟”。如果一个承诺只是增加某个行动的成本而不是使该行动完全没有可能，这样的承诺是不完全承诺。1、法律诉讼(NuisanceSuits)—SimpleExtortionPlayers:aplaintiffandadefendantTheorderofplay–Theplaintiffdecideswhethertobringsuitagainstthedefendantatcostc–Theplaintiffmakesatake-it-or-leave-itsettlementofferofs0–Thedefendantacceptsorrejectsthesettlementoffer.–Ifthedefendantrejectstheoffer,theplaintiffdecideswhethertogiveuporgototrialatacostptohimselfanddtothedefendant.–Ifthecasegoestotrial,theplaintiffwinsamountxwithprobabilityγandotherwisewinsnot