不完全信息博弈和贝叶斯均衡ppt课件

第三章：不完全信息静态博弈第三章：第三章：主要内容：一、不完全信息博弈和贝叶斯纳什均衡二、贝叶斯均衡的应用三、贝叶斯博弈与混合战略均衡四、机制设计理论与显示原理主要内容：主要内容：第一节第一节 不完全信息博弈不完全信息博弈和贝叶斯均衡和贝叶斯均衡 一、贝叶斯博弈 二、海萨尼转换 三、贝叶斯博弈的战略式描述 四、贝叶斯纳什均衡第一第一节节 不完全信息博弈不完全信息博弈和和贝贝叶斯均衡叶斯均衡 一、一、贝贝叶斯博弈叶斯博弈一、一、贝叶斯博弈叶斯博弈完全信息（complete information）：每个参与人对其他参与人的支付函数有准确的了解支付函数有准确的了解；否则，为不完全信息（incomplete information）。完美信息（perfect information）：在博弈过程的任何时点每个参与人都能观察并察并记忆之前各局中人所之前各局中人所选择的行的行动，否则为不完美信息（imperfect information）。一、一、贝贝叶斯博弈完全信息（叶斯博弈完全信息（complete informati前面两章我们讨论了完全信息博弈问题，但在现实生活中我们遇到更多的可能是不完全信息博弈问题。例如：在企业的新产品开发过程中，企业对市场的需求可能并不清楚；在连锁店博弈中，潜在的进入者可能并不知道连锁店在市场上的盈利情况，等等。像这种博弈开始开始时就存在事前不确定性的博弈就存在事前不确定性的博弈问题是不完全信息博弈问题。前面两章我前面两章我们讨论们讨论了完全信息博弈了完全信息博弈问题问题，但在，但在现实现实生活中我生活中我们们遇到更遇到更40，50-10，030，80-10，1000，300 0，3000，400 0，400 高成本情况高成本情况 低成本情况低成本情况 默许默许 斗争斗争 默许默许 斗争斗争进入进入不进入不进入进入者进入者 在位者在位者市场进入博弈：不完全信息市场进入博弈：不完全信息在位者的成本有两种类型，而进入者并不知道在位者的成本类型。40，50-10，030，80-10，1000，3000，3显然，在这种情形下，进入者有关在位者的成本信息是不完全的。当在位者具有不同的成本时，所表现出来的博弈情形是不同的，对应的均衡也是不一样的。高成本情形：（进入，默许）（不进入，斗争）低成本情形：（不进入，斗争）显显然，在然，在这这种情形下，种情形下，进进入者有关在位者的成本信息是不完全的。入者有关在位者的成本信息是不完全的。斗鸡博弈斗鸡博弈两个所谓的勇士举着长枪，准备从独木桥的两端冲上桥中央进行决斗。每位勇士都有两种选择：冲上去(用U表示)，或退下来(用D表示)。若两人都冲上去，则两败俱伤；若一方上去而另一方退下来，冲上去者取得胜利(至少心理上是这样的)，退下来的丢了面子；若两人都退下来，两人都丢面子。斗斗鸡鸡博弈两个所博弈两个所谓谓的勇士的勇士举举着着长枪长枪，准，准备备从独木从独木桥桥的两端冲上的两端冲上桥桥中中存在两个纯战略Nash均衡(U，D)和(D，U)，也就是一个人冲上去，另一个就必须退下来。当一个理性的参与人预测到对方将会冲上去时，明智的选择就是退下来；而当预测到对方将会选择退却时，就应该大胆地冲上去。-4,-42,-2-2,20,0UD21UD存在两个存在两个纯战纯战略略Nash均衡均衡(U，D)和和(D，U)，也就是，也就是现在考虑这样的情形：假设参与人可能有这样的两种性格特征(类型)“强硬”(用s表示)或“软弱”(用w表示)。所谓“强硬”的参与人是指那些喜欢争强好胜、不达目的誓不罢休的决斗者；而“软弱”的参与人是指那些胆小怕事、遇事希望息事宁人的决斗者。可以想象，当具有不同性格特征的决斗者相遇时，表现出来的博弈情形将会不同。斗鸡博弈：不完全信息斗鸡博弈：不完全信息现现在考在考虑这样虑这样的情形：假的情形：假设设参与人可能有参与人可能有这样这样的两种性格特征的两种性格特征(类类型型当参与人都为强硬者时博弈存在两个纯战略Nash均衡(U，D)和(D,U)。当参与人都当参与人都为为强强硬者硬者时时博弈存在两个博弈存在两个纯战纯战略略Nash均衡均衡(U当参与人1为强硬者参与人2为软弱者时博弈存在唯一的Nash均衡(U,D)。当参与人当参与人1为为强强硬者参与人硬者参与人2为软为软弱者弱者时时博弈存在唯一的博弈存在唯一的Nash均均当参与人1为软弱者参与人2为强硬者时博弈存在唯一的Nash均衡(D,U)。当参与人当参与人1为软为软弱者参与人弱者参与人2为为强强硬者硬者时时博弈存在唯一的博弈存在唯一的Nash均均当参与人都为软弱者时博弈存在唯一的Nash均衡(D,D)。当参与人都当参与人都为软为软弱者弱者时时博弈存在唯一的博弈存在唯一的Nash均衡均衡(D,D(1)参与人都为强硬者(2)参与人1为强硬者参与人2为软弱者(3)参与人1为软弱者参与人2为强硬者(4)参与人都为软弱者(1)参与人都参与人都为为强强硬者硬者(2)参与人参与人1为为强强硬者参与人硬者参与人2为软为软 强硬强硬 软弱软弱 U D U DU D U D1 2 1，1 0，0 1，0 0，2 0，0-4，-4 0，-2-4，-4 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U D U U D D强硬强硬 软弱软弱斗鸡博弈：不完全信息斗鸡博弈：不完全信息 强强硬硬 软软弱弱 1 2在“斗鸡博弈”中，虽然在博弈开始之前每位决斗者都知道自己的性格特征，但对对手的性格特征往往不甚了解。在这种情况下即使所有的决斗者都看到了上面的四个战略式博弈，但对决斗者来讲，仍存在着所谓的事前不确定性，即博弈开始之前就不知道的信息。具体而言，这意味着当博弈真正开始的时候，对到底体现为哪一种博弈形势并不清楚。在在“斗斗鸡鸡博弈博弈”中，中，虽虽然在博弈开始之前每位决斗者都知道自己的性然在博弈开始之前每位决斗者都知道自己的性对于“强硬”的参与人1来讲，虽然他看到了上面的战略式博弈，但他不知道对手是“强硬”的还是“软弱”的，所以博弈开始之前他无法确定博弈是根据(1)还是(2)进行。这意味着“强硬”的参与人1面临着事前无法确定的信息。同样，“软弱”的参与人1也会面临类似的问题。此时，“斗鸡博弈”就是一个不完全信息博弈问题。对对于于“强强硬硬”的参与人的参与人1来来讲讲，虽虽然他看到了上面的然他看到了上面的战战略式博弈，但略式博弈，但从这一例子来看，博弈的参与人均存在两种不同的类型，即强硬和软弱；由于参与人1不知道对手究竟是“强硬”的还是“软弱”的，因此，此时参与人1就好像在与两个决斗者进行决斗，一个是“强硬”的，另一个是“软弱”的；当一个参与人并不知道在与谁博弈时，博弈的规则是无法定义的，如何处理不完全信息导致的这一问题？从从这这一例子来看，博弈的参与人均存在两种不同的一例子来看，博弈的参与人均存在两种不同的类类型，即型，即强强硬和硬和软软为了解决该问题，海萨尼提出了Harsanyi转换。海萨尼指出，引入虚拟参与人自然，由自然先决定参与人的不同类型，将不完全信息博弈转换为不完美信息博弈。二、海二、海萨尼（尼（Harsanyi）转换为为了解决了解决该问题该问题，海，海萨萨尼提出了尼提出了Harsanyi转换转换。二、海。二、海萨萨尼尼为了解释Harsanyi转换的具体含义，我们对“斗鸡博弈”进行简化。假设参与人1是“强硬”的决斗者，参与人2可能是“强硬”的也可能是“软弱”的，参与人1不知道参与人2的类型，但参与人2知道自己的类型，而且这一假设为所有的参与人所知道。为为了解了解释释Harsanyi转换转换的具体含的具体含义义，我，我们对们对“斗斗鸡鸡博弈博弈”进进Harsanyi转换对于简化的“斗鸡博弈”，Harsanyi转换是这样处理的：在原博弈中引入一个“虚拟”的参与人“自然”(nature，用N表示)，构造一个参与人为两个决斗者和“自然”的三人博弈。Harsanyi转换对转换对于于简简化的化的“斗斗鸡鸡博弈博弈”，HarsanyiHarsanyi转换“自然”首先行动决定参与人2的性格特征(即选择参与人2是“强硬”的还是“软弱”的)，“自然”的选择参与人1不知道，但参与人2知道。参与人2的特征Harsanyi转换转换“自然自然”首先行首先行动动决定参与人决定参与人2的性格特征的性格特征(在“自然”选择后，参与人1和2再进行“斗鸡博弈”。在在“自然自然”选择选择后，参与人后，参与人1和和2再再进进行行“斗斗鸡鸡博弈博弈”。在新构造的三人博弈中，“自然”的支付不必考虑。参与人1和2的支付由“斗鸡博弈”决定。在新构造的三人博弈中，在新构造的三人博弈中，“自然自然”的支付不必考的支付不必考虑虑。参与人。参与人1和和2的的如果“自然”选择参与人2的性格特征是“强硬”的，则意味着参与人1与“强硬”的参与人2进行决斗，博弈进入决策结x1，其支付由(1)决定；如果如果“自然自然”选择选择参与人参与人2的性格特征是的性格特征是“强强硬硬”的，的，则则意味着参与意味着参与如果“自然”选择参与人2的性格特征是“软弱”的，则意味着参与人1与“软弱”的参与人2进行决斗，博弈进入决策结x2，其支付由(2)决定。如果如果“自然自然”选择选择参与人参与人2的性格特征是的性格特征是“软软弱弱”的，的，则则意味着参与意味着参与海萨尼通过引入“虚拟”参与人，将博弈的起始点由x1或x2提前至x0，从而将原博弈中参与人的事前不确定性转变为博弈开始后的不确定性。这种通过引入“虚拟”参与人来处理不完全信息博弈问题的方法称为 Harsanyi转换。海海萨萨尼通尼通过过引入引入“虚虚拟拟”参与人，将博弈的起始点由参与人，将博弈的起始点由x1或或x2提前提前在Harsanyi转换中规定：参与人关于“自然”选择的推断为共同知识。也就是说，两个决斗者不仅同时一起看到了“自然”随机选择参与人2的性格特征，而且同时一起看到了“自然”以一定的概率分布随机选择参与人2的性格特征。在在Harsanyi转换转换中中规规定：参与人关于定：参与人关于“自然自然”选择选择的推断的推断为为在应用Harsanyi转换时，需要注意以下问题：1)“自然”的选择。在一般的不完全信息博弈问题中，Harsanyi转换规定“自然”选择的是参与人的类型(type)。除了根据参与人的支付来划分参与人的类型以外，还可以根据参与人的行动空间，甚至根据参与人掌握信息的多少(或程度)来划分参与人的类型。在在应应用用Harsanyi转换时转换时，需要注意以下，需要注意以下问题问题：1用ti表示参与人i的一个特定的类型，Ti表示参与人i所有类型的集合(亦称类型空间，type space)，即 ，t=(t1,tn)表示所有参与人的类型组合，t-i=(t1,ti-1,tn)表示除参与人i之外其他参与人的类型组合。所以，t=(ti,t-i)。用用ti表示参与人表示参与人i的一个特定的的一个特定的类类型，型，Ti表示参与人表示参与人i所有所有类类型型用 表示参与人i在知道自己类型为ti的情况下，关于其他参与人类型的推断(即条件概率)，则2)参与人关于“自然”选择的推断：用p(t1,tn)表示定义在参与人类型组合上的一个联合分布概率函数。用用 表示参与人表示参与人i在知道自己在知道自己类类型型为为ti的情的情假设pss=0.2，psw=0.3，pws=0.25，pww=0.25。其中，pss：决斗者1和决斗者2同时强硬的概率；psw：决斗者1强硬、决斗者2软弱的概率；pws：决斗者1软弱、决斗者2强硬的概率；pww：决斗者1软弱、决斗者2软弱的概率；虽然决斗者1不知道决斗者2 的类型，但由于决斗者1知道自己的类型，因此他可以根据贝叶斯公式推知决斗者2的类型分布。假假设设pss=0.2，psw=0.3，pws=0.25，pww例如根据贝叶斯规则，“强硬”的决斗者1可以推知：决斗者2是“强硬”的概率为 决斗者2是“软弱”的概率为“软弱”的决斗者1可以推知：决斗者2是“强硬”的概率为 决斗者2是“软弱”的概率为 例如根据例如根据贝贝叶斯叶斯规则规则，“强强硬硬”的决斗者的决斗者1可以推知：可以推知：不完全信息博弈：完全信息博弈在不完全信息上的拓展，我们又将其称为贝叶斯博弈；贝叶斯博弈：静态贝叶斯博弈和动态贝叶斯博弈；三、贝叶斯博弈的战略式描述不完全信息博弈：完全信息博弈在不完全信息上的拓展，我不完全信息博弈：完全信息博弈在不完全信息上的拓展，我们们又将其又将其贝叶斯博弈的定义贝叶斯博弈包含以下五个要素：(1)参与人集合 ；(2)参与人的类型集合T1,T2；(3)参与人关于其他参与人类型的推断 ,；(4)参与人类型相依的行动集A(t1),A(tn)；(5)参与人类型相依的支付函数 ,。贝贝叶斯博弈的定叶斯博弈的定义贝义贝叶斯博弈包含以下五个要素：叶斯博弈包含以下五个要素：贝叶斯博弈中的战略在贝叶斯博弈 中，参与人i的一个战略是从参与人的类型集Ti到其行动集的一个函数si(ti)；它包含了当自然赋予i的类型为ti时，i将从可行的行动集Ai(ti)中选择的行动。贝贝叶斯博弈中的叶斯博弈中的战战略在略在贝贝叶斯博弈叶斯博弈 用 表示给定其他参与人的战略 ，类型为ti的参与人i选择行动ai时的期望效用，则 其中，对 ，为给定t-i时由s-i所确定的其他参与人的行动组合用用 表示表示给给定其他参与人的定其他参与人的战战略略 贝叶斯博弈的时间顺序如下：(1)“自然”选择参与人的类型组合t=(t1,tn)，其中，参与人i观测到“自然”关于自己类型ti的选择；虽然参与人i观测不到“自然”关于其他参与人类型t-i的选择，但参与人i具有关于其他参与人类型的推断 ；(2)参与人同时选择行动，每个参与人i从行动集Ai(ti)中选择行动ai(ti)；(3)参与人i得到 。贝贝叶斯博弈的叶斯博弈的时间顺时间顺序如下：序如下：“自然自然”选择选择参与人的参与人的类类型型组组合合t=(“斗鸡博弈”的贝叶斯模型参与人为决斗者1和2；用s表示决斗者是“强硬”的，w表示决斗者是“软弱”的，所以T1=T2=s,w。用pxy表示“自然”选择类型组合(x,y)的概率，并假设pxy为共同知识，则决斗者1关于其对手类型的推断为p1(y|x)。决斗者1关于类型相依的行动空间A1(x)=U,D，决斗者2关于类型相依的行动空间A2(y)=U,D。每位决斗者i的支付由前面的图决定。“斗斗鸡鸡博弈博弈”的的贝贝叶斯模型参与人叶斯模型参与人为为决斗者决斗者1和和2；在贝叶斯博弈中，对于一个理性的参与人i，当他只知道自己的类型ti而不知道其他参与人的类型时，给定其他参与人的战略s-i，他将选择使自己期望效用(支付)最大化的行动 ，其中四、贝叶斯纳什均衡在在贝贝叶斯博弈中，叶斯博弈中，对对于一个理性的参与人于一个理性的参与人i，当他只知道自己的，当他只知道自己的类类型型纯战略贝叶斯Nash均衡 贝叶斯博弈 的纯战略贝叶斯Nash均衡是一个类型相依的行动组合 ，其中每个参与人在给定自己的类型ti和其他参与人的类型相依行动 的情况下最大化自己的期望效用。也就是，行动组合 是一个纯战略贝叶斯Nash均衡，如果对 ，纯战纯战略略贝贝叶斯叶斯Nash均衡均衡 贝贝叶斯博弈叶斯博弈 贝叶斯博弈纳什均衡的存在性定理 一个有限的贝叶斯博弈一定存在贝叶斯Nash均衡。贝贝叶斯博弈叶斯博弈纳纳什均衡的存在性定理什均衡的存在性定理 一个有限的一个有限的贝贝叶斯博弈一定存叶斯博弈一定存类型1类型2左 右左 右3，12，03，02，10，14，00，04，1上 下 甲乙静态贝叶斯博弈均衡举例：表中甲、乙同时行动，甲只有一种类型，但乙有两种类型：2=1，2；甲不了解对方是哪一种类型，但他相信对方为1，2的概率各为1/2。求解均衡。类类型型 1类类型型 2左左 右左右左 乙：如果为1，有占优战略为“左”；如果为2，有占优战略为“右”甲：由于甲相信对方为两种类型的可能性各为1/2，故甲考虑选“上”和“下”分别给他带来的期望收益；结果选“上”，期望支付为5/2，选“下”，期望支付为2，因而甲的最佳选择是“上”。纳什均衡为s1*=上；s2*(1)=左，s2*(2)=右。乙：如果乙：如果为为 1，有占，有占优战优战略略为为“左左”；如果；如果为为 2，有占，有占优战优战略略为为贝叶斯Nash均衡的求解：先以简化的“斗鸡博弈”为例。强硬强硬 软弱软弱 U D U DU D U D1 2 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U D 强硬强硬贝贝叶斯叶斯Nash均衡的求解：先以均衡的求解：先以简简化的化的“斗斗鸡鸡博弈博弈”为为例。例。用p表示决斗者1关于决斗者2的类型的推断，即决斗者1认为决斗者2为强硬的概率为p。(x,(y,z)：x表示当决斗者2选择该方格所对应的战略时，决斗者1选择该方格所对应的战略规定的行动所得到的期望支付；y和z分别表示当决斗者1选择该方格所对应的战略时，“强硬”决斗者2和“软弱”决斗者2选择该方格所对应的战略规定的行动所得到的期望支付。用用p表示决斗者表示决斗者1关于决斗者关于决斗者2的的类类型的推断，即决斗者型的推断，即决斗者1认为认为决斗决斗给定决斗者1选择战略U，“软弱”决斗者2选择行动D的期望支付为0，选择行动U的期望支付为-4，行动D优于行动U；给定决斗者1选择战略D，“软弱”决斗者2选择行动D的期望支付为1，选择行动U的期望支付为0，所以，行动D优于行动U。这意味着战略U为软弱决斗者2的劣战略。给给定决斗者定决斗者1选择战选择战略略U，“软软弱弱”决斗者决斗者2选择选择行行动动D的期望支付的期望支付-4,-42,-2-2,20,0 U21UD-4,-42,0-2,00,1 D D U-4,-42,-2-2,20,0 U21UD 2，0 D D0，1-4,-42,-2-2,20,0 U21UD-4下面根据p的大小，求解博弈的纯战略贝叶斯 Nash均衡。1)假设 ，无论决斗者2选择战略(U,D)还是(D,D)，决斗者1的最优行动都是U。给定决斗者1的选择U，“强硬”决斗者2的最优行动为D。所以，博弈存在惟一的纯战略贝叶斯Nash均衡决斗者1选择行动U，“强硬”决斗者2选择行动D，“软弱”决斗者2选择行动D。情形情形1 1：给定决斗者：给定决斗者1 1认为决斗者认为决斗者2 2为强硬的概率为为强硬的概率为p p下面根据下面根据p的大小，求解博弈的的大小，求解博弈的纯战纯战略略贝贝叶斯叶斯 Nash均衡。情形均衡。情形2)假设 ，博弈存在如下两个纯战略贝叶斯Nash均衡：(1)决斗者1选择行动U，“强硬”决斗者2选择行动D，“软弱”决斗者2选择行动D；(2)决斗者1选择行动D，“强硬”决斗者2选择行动U，“软弱”决斗者2选择行动D。2)假假设设 ，博弈存在如下两个，博弈存在如下两个纯战纯战求解另一种情形下“斗鸡博弈”的 贝叶斯Nash均衡 强硬强硬 软弱软弱 U D U DU D U D 1，1 0，0 1，0 0，2 0，0-4，-4 0，-2-4，-4 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U D U U D D强硬强硬 软弱软弱求解另一种情形下求解另一种情形下“斗斗鸡鸡博弈博弈”的的 求解另一种情形下“斗鸡博弈”的 贝叶斯Nash均衡假设“强硬”决斗者1关于决斗者2的类型推断 ；“软弱”决斗者1关于决斗者2的类型推断 ；“强硬”决斗者2关于决斗者1的类型推断 ；“软弱”决斗者2关于决斗者1的类型推断 ；求解另一种情形下求解另一种情形下“斗斗鸡鸡博弈博弈”的的 强硬强硬 软弱软弱 U D U DU D U D 1，1 0，0 1，0 0，2 0，0-4，-4 0，-2-4，-4 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U U D D U U D D强硬强硬 软弱软弱 强硬强硬 软弱软弱 U D U DU D U D 1，1 0，0 1，0 0，2 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U U D D D D 强硬强硬 软弱软弱 强强硬硬 软软弱弱 1，1 强硬强硬 软弱软弱 U D U DU D U D 1，1 0，0 1，0 0，2 0，1-2，0 0，0 -2，2 2，0-4，-4 2，-2-4，-4 U U D D D D 强硬强硬 软弱软弱 强硬强硬 软弱软弱 U D D U D D 1，1 1，0 0，2 0，1 0，0 -2，2 2，0 2，-2-4，-4 U U D D D D 强硬强硬 软弱软弱 强强硬硬 软软弱弱 1，1 强硬强硬 软弱软弱 U D D U D D 1，1 1，0 0，2 0，1 0，0 -2，2 2，0 2，-2-4，-4 U U D D D D 强硬强硬 软弱软弱 强硬强硬 软弱软弱 U D D U D D 1，1 1，0 0，2 2，0 2，-2-4，-4 U U D D 强硬强硬 软弱软弱U是是强硬的硬的决斗者决斗者1的的占占优策略策略 强强硬硬 软软弱弱 1，1 1，0 强硬强硬 软弱软弱 U D D U D D 1，1 1，0 0，2 0，1 0，0 -2，2 2，0 2，-2-4，-4 U U D D D D 强硬强硬 软弱软弱对于强硬的决斗者1而言，有因此，因此，U是是强硬硬的决斗者的决斗者1的占的占优策略。策略。强强硬硬 软软弱弱 1，1 1，0 强硬强硬 软弱软弱 U D D U D D 1，1 1，0 0，2 2，0 2，-2-4，-4 U U D D 强硬强硬 软弱软弱因此，因此，强硬的决斗者硬的决斗者2选择U和和D无差无差别。对于强硬的决斗者2而言，有 强强硬硬 软软弱弱 1，1 1，0 所以，该博弈存在如下两个纯战略Nash均衡：“强硬”的决斗者1选择行动U，“软弱”的决斗者1选择行动D；“强硬”的决斗者2选择行动U，“软弱”的决斗者2选择行动D。“强硬”的决斗者1选择行动U，“软弱”的决斗者1选择行动D；“强硬”的决斗者2和“软弱”的决斗者2选择行动D。所以，所以，该该博弈存在如下两个博弈存在如下两个纯战纯战略略Nash均衡：均衡：