范里安-博弈论课件.ppt

1、第二十八章博弈论博弈论博弈是什么？n一个博弈博弈包含：n一些参与者参与者n每个参与者的策略策略n每个参与者选择不同决策行为的收益矩阵。收益矩阵。两人博弈的一个例子n参与者A 和 B。nA 可以采取两种行为：“上”和“下”。nB 可以采取两种行为：“左”和“右”。n包含了四种可能决策组合支付的表格称为博弈的收益矩阵收益矩阵。两人博弈的一个例子这是博弈的收益矩阵参与者 B参与者 A左边显示A的收益右边显示B的收益LRUD(3,9)(0,0)(1,8)(2,1)两人博弈的一个例子哪种策略组合结果会最终出现？LRUD(3,9)(0,0)(1,8)(2,1)参与者 B参与者 A纳什均衡n博弈论中的策略组

2、合中，每个参与者的决策都是对其它参与者决策的最佳反应决策时所达到的均衡称为 纳什均衡。纳什均衡。n我们的例子中有两个纳什均衡(U,L)和(D,R)。两人博弈的例子(U,L)和(D,R)为此博弈的纳什均衡。但是我们发现：对两个参与者来说，(U,L)比(D,R)更受偏好。我们是否一定仅会看到(U,L)的博弈均衡结果？LRUD(3,9)(0,0)(1,8)(2,1)参与者 B参与者 A囚徒困境n为了了解帕累托偏好结果是否一定就是一个博弈的结果。考虑一个很有名的囚徒困境囚徒困境博弈问题。囚徒困境这个博弈的可能结果是什么样子？克莱德邦妮(-5,-5)(-30,-1)(-1,-30)(-10,-10)SC

3、SC唯一的纳什均衡为(C,C)，尽管(S,S)能使得邦妮和克莱德的处罚更轻。这个唯一的纳什均衡是无效率的。决策时机n在上面来两个例子中，参与者同时做出他们的决策。n这样的博弈称为同步博弈同步博弈。n但博弈过程也可能表现为参与者按一定顺序作出决策行动。首先行动的参与者称为领导者领导者，后行动的参与者称为追随者追随者。序贯博弈的例子n有时一个博弈可能含有几个纳什均衡，很难确定哪一种均衡结果更有可能发生。n当一个博弈为一个序贯博弈时，那么就有可能其中的一个纳什均衡比其它均衡更有可能发生。序贯博弈的例子假设这个博弈为序贯博弈，A为领导者而B为追随者。我们可以把这个博弈的拓展形式拓展形式写出来。LRUD

4、(3,9)(0,0)(1,8)(2,1)参与者 B参与者 A序贯博弈的例子UDLLRR(3,9)(1,8)(0,0)(2,1)ABBA 先行动B 后行动(U,L)为一个纳什均衡。(D,R)也是一个纳什均衡。这两个均衡哪个更有可能发生？序贯博弈的例子假如A先选择决策U，B后选择策略L；A 所得收益为3。假如A先选择策略D，B后选择策略R；A 所得收益为2。UDLLRR(3,9)(1,8)(0,0)(2,1)ABBA 先行动B 后行动因此(U,L)很可能为均衡结果。序贯博弈的例子LRUD(3,9)(0,0)(1,8)(2,1)参与者 B参与者 A参与者A 已经被考虑了上或者下的决策，但没有把这两种

5、策略联合起来考虑。例如，仅做出单纯的上或下决策。上和下为参与者A的纯策略纯策略。类似地，左和右为参与者B的纯策略纯策略。序贯博弈的例子LRUD(3,9)(0,0)(1,8)(2,1)参与者 B参与者 A因此，(U,L)和(D,R)为纯策略纳什均衡纯策略纳什均衡。是否每一个博弈都至少有一个纯策略纳什均衡？纯策略参与者 B参与者 A这是一个新的博弈。是否存在纯策略的纳什均衡？(1,2)(0,4)(0,5)(3,2)UDLR纯策略(D,R)是否为一个纳什均衡？参与者 B参与者 A(1,2)(0,4)(0,5)(3,2)UDLR(U,L)是否为一个纳什均衡？(U,R)是否为一个纳什均衡？(D,L)是否

6、为一个纳什均衡？不是。不是。不是。不是。因此当采取纯策略时，该博弈没有纳什均衡。但是这个博弈在采取混混合策略合策略时有一个纳什均衡。混合策略n参与者A选择一个概率分布(pU,1-pU)，表示参与者A有pU的概率选择策略上，有1-pU的概率选择策略下；而不是单纯的选择上或者下的策略。n参与者A混合混合了上和下的纯策略。n概率分布概率分布(pU,1-pU)为参与者为参与者A的混合策略。的混合策略。混合策略n类似地，参与者B选择概率分布(pL,1-pL)，表示有pL的概率他会选择左，有1-pL的概率他会选择右。n参与者B混合混合了左和右的纯策略。n概率分布概率分布(pL,1-pL)为参与者为参与者B

7、的混合策略。的混合策略。混合策略参与者 B参与者 A这个博弈没有纯策略纳什均衡，当有混合策略纳什均衡。混合纳什均衡结果是如何计算的？(1,2)(0,4)(0,5)(3,2)UDLR混合策略参与者 B参与者 A(1,2)(0,4)(0,5)(3,2)U,pUD,1-pUL,pLR,1-pLA选择上策略的预期收益为pL。A选择下策略的预期收益为3(1-pL)。混合策略参与者 B参与者 A(1,2)(0,4)(0,5)(3,2)U,pUD,1-pUL,pLR,1-pL假如 pL 3(1-pL)那么A仅选择上的策略，但是当A采用上的纯策略时没有纳什均衡。假如 pL 4pU+2(1-pU)那么B仅选择左

8、的策略，但是当B仅采用左的策略时不存在纳什均衡。混合策略参与者B参与者 A(1,2)(0,4)(0,5)(3,2)U,pUD,1-pUL,3/4R,1/4B选择左的策略的预期收益为2pU+5(1-pU)。B选择右的策略的预期收益为4pU+2(1-pU)。假如2pU+5(1-pU)=参与者的最佳反应函数为什么？合作博弈；性别战1,28,44,82,1BMWBMW杰克杰克西斯西斯pSBpJB110013/西斯合作博弈；性别战pSBpJB110013/西斯pSBpJB110013/杰克合作博弈；性别战pSBpJB110013/西斯pSBpJB110013/杰克博弈的纳什均衡为什么？合作博弈；性别战p

9、SBpJB110013/西斯杰克博弈的纳什均衡为什么？13/合作博弈；性别战1/3例如,共同观看芭蕾的概率为1/9,共同观看泥土摔跤的概率为4/9,他们观看不同节目的概率为4/9。pSBpJB1100西斯杰克13/博弈的纳什均衡为:(pJB,pSB)=(0,0);例如,(MW,MW)(pJB,pSB)=(1,1);例如,(B,B)(pJB,pSB)=(1/3,1/3);合作博弈；性别战1,28,44,82,1BMWBMW杰克杰克西斯西斯因此，混合策略纳什均衡是否该博弈的一个焦点？焦点？达到纳什均衡 时西斯的预期收益为：4和 8。11(,),33JSBBpp101224812499993 达到纳

10、什均衡 时杰克的预期收益为：，4 8。11(,),33JSBBpp122414421899993 143合作博弈；囚徒困境n同时做出决策的参与者都有占优策略。n唯一的纳什均衡为每个参与者选择的占优策略。n然而每个参与者可以通过合作采取其它策略组合达到比在纳什均衡情况更多的收益。合作博弈；囚徒困境n提姆和汤姆在看守所。每个人可以选择供认罪行(C)或者保持沉默(S)。n两者都供认罪行每人将被判罚5年监禁。n两者都保持沉默每人将被判罚2年监禁。n假如提姆供认罪行而汤姆保持沉默，那么提姆不受处罚而汤姆将要判罚10监禁(反之亦然)。合作博弈；囚徒困境唯一的纳什均衡为：(供认，供认)。供认供认沉默沉默汤姆

11、汤姆提姆提姆沉默沉默供认供认-10,0-2,-2-5,-50,-10但是（沉默，沉默）对于提姆和汤姆来说更好。对于提姆来说供认为占优策略。对于汤姆来说供认为占优策略。合作博弈；囚徒困境可能的措施包括将来的惩罚或者强制实施的合同汤姆汤姆供认供认沉默沉默提姆提姆沉默沉默供认供认-10,0-2,-2-5,-50,-10为了使双方合作从而达到收益最大状态所需的是合理的确保承诺承诺。合作博弈；承诺博弈n同时做决策的博弈的两个合作纳什均衡，其中一个比另一个所得收益要严格地高。n问题是：每个参与者怎么给对方承诺从而使该博弈出现好的纳什均衡结果？合作博弈；承诺博弈n一个普遍的例子为军备竞赛博弈。n印度和巴基斯

12、坦都可以增加他们的核武器存量，这样的成本很高。n对另一个国家有核有时能够得到更高的收益，但是对手方国家的收益降低。n不增加核储备对两个国家最好。合作博弈；承诺博弈增加增加不增加不增加巴基斯坦巴基斯坦印度印度不增加不增加增加增加1,45,53,34,1博弈的纳什均衡为什么？合作博弈；承诺博弈增加增加不增加不增加巴基斯坦巴基斯坦印度印度不增加不增加增加增加1,45,53,34,1该博弈的纳什均衡为(不增加，不增加)和(增加，增加)。哪一个纳什均衡更有可能发生？合作博弈；承诺博弈增加增加不增加不增加巴基斯坦巴基斯坦印度印度不增加不增加增加增加1,45,53,34,1该博弈的纳什均衡为(不增加，不增加

13、)和(增加，增加)。哪一个纳什均衡更有可能发生？假如印度先行动，结果如何？它会采取哪种策略？不增加核储备是不是最好的？合作博弈；斗鸡博弈n同时做出决策的两个合作纳什均衡，在该均衡中每个参与者选择不被对手方选择的策略合作博弈；保证博弈n两个司机进行对向行驶赛车。谁转向谁就是懦夫，谁不转向谁就是男子汉。n假如二者都不转向，就会发生碰撞，两者的收益都很低。n假如二者都转向不会发生碰撞，二者会得到适度的收益。n假如其中一个转向而另一个没有转向，那么转向的人得到很低的收益而没有转向的人获得高收益。合作博弈；保证博弈不转向不转向转向转向DumberDumb转向转向不转向不转向-2,41,1-5,-54,-

14、2该博弈的纳什均衡为什么？合作博弈；保证博弈不转向不转向转向转向DumberDumb转向转向不转向不转向-2,41,1-5,-54,-2该博弈的纯策略纳什均衡为（转向，不转向）和（不转向，转向）。存在一个混合策略纳什均衡，该均衡中每个人选择转向的概率为。Dumb 能否保证他得到4的收益？仅当他能说服Dumber他将会选择不转向。他如何说服Dumber？博弈的几种重要类型n合作博弈n竞争博弈竞争博弈n共存博弈n承诺博弈n讨价还价博弈竞争博弈n同时做出决策的博弈，其中一个参与者的收益增加额正好是另一个参与者收益的减少额。n这些博弈通常称为零和博弈竞争博弈DL21UR2,-20,01,-1x,-x下

15、表是该博弈的一个例子。该博弈能达到什么样的纳什均衡？竞争博弈DL21UR2,-20,01,-1x,-x下表是该博弈的一个例子。该博弈能达到什么样的纳什均衡？假如x 0 那么与下相比上为占优策略。假如x 1 那么与右相比左为占优策略。竞争博弈DL21UR2,-20,01,-1x,-x下表是该博弈的一个例子。该博弈能达到什么样的纳什均衡？假如x 0 那么与下相比上为占优策略。假如x 1 那么与右相比左为占优策略。因此假如 x 0纳什均衡为什么？竞争博弈DL21UR2,-20,01,-1x,-x下表是该博弈的一个例子。该博弈能达到什么样的纳什均衡？假如x 0 那么与下相比上为占优策略。假如x 1 那

16、么与右相比左为占优策略。假如x 0 纳什均衡为(上，左)。竞争博弈DL21UR2,-20,01,-1x,-x下表是该博弈的一个例子。该博弈能达到什么样的纳什均衡？假如x 0 那么与下相比上为占优策略。假如x 1 那么与右相比左为占优策略。假如x 0 纳什均衡为(上，左)。假如0 x 1纳什均衡为什么？竞争博弈DL21UR2,-20,01,-1x,-x假如0 x 1纳什均衡？假如x 0 那么与下相比上为占优策略假如x 1 那么与右相比左为占优策略假如x 1 竞争博弈DL21UR2,-20,01,-1x,-x2选择左的概率为 pL。1 选择上的概率为pU。当 x 1时。竞争博弈DL21UR2,-2

17、0,01,-1x,-x2选择左的概率为 pL。1 选择上的概率为pU。当 x 1时。EV1(U)=2(1-pL).EV1(D)=xpL+1-pL.=1/(1+x)选择下假如pL 1/(1+x)。2 选择左假如pU (x 1)/(1+x)。竞争博弈1:选择上假如pL 1/(1+x);选择下假如pL 1/(1+x).2:选择左假如pU (x 1)/(1+x).pUpUpLpL1211100001/(1+x)(x-1)/(1+x)竞争博弈第二幅图中pL 与pU 对换pUpL1211001/(1+x)pUpL100(x-1)/(1+x)竞争博弈1pUpL100(x-1)/(1+x)1/(1+x)当 x

18、 1时，当1选择上概率为(x 1)/(x+1)2 选择左的概率为1/(1+x)时存在唯一纳什均衡。博弈的几种重要类型n合作博弈 n竞争博弈n共存博弈共存博弈n承诺博弈n讨价还价博弈共存博弈n同时做出决策的博弈，该博弈用来对不同种类的人之间相互反应的行为来进行建模。n一个重要的例子为鹰派-鸽派博弈。共存博弈；鹰派-鸽派博弈n鹰派意味着具有进攻性n鸽派意味着不具有进攻性n两只熊来到了一个捕鱼产地。每只熊都可以与对方搏斗来将其驱赶开从而能得到更多的鱼，但其在搏斗中要受伤。或者它容忍另一只熊的存在，分享捕鱼，避免受伤。共存博弈；鹰派-鸽派博弈注意到完全的和平共存不是纳什均衡8,04,40,8鹰派鹰派鸽

19、派鸽派鹰派鹰派鸽派鸽派熊熊 2熊熊 1-5,-5是否存在纯策略纳什均衡？存在(鹰派,鸽派)和(鸽派,鹰派)是否存在一个混合策略纳什均衡？共存博弈；鹰派-鸽派博弈1 选择鹰派的概率为p1H 2 选择鹰派的概率为p2H 参与者的最佳反应函数为什么？EV1(H)=-5p2H+8(1-p2H)=8-13p2H.EV1(D)=4-4p2H.8-13p2H 4-4p2H as p2H 4/9.=8,04,40,8鹰派鹰派鸽派鸽派鹰派鹰派鸽派鸽派熊熊 2熊熊 1-5,-5是否存在一个混合策略纳什均衡？共存博弈；鹰派-鸽派博弈熊 1熊 2p2Hp1H11004/9p1Hp2H11004/9共存博弈；鹰派-鸽派

20、博弈熊 1熊 2p1Hp2H11004/9p1Hp2H11004/9共存博弈；鹰派-鸽派博弈p1Hp2H11004/9假如每只熊选择鹰派的概率为4/9，该博弈存在一个混合策略纳什均衡。共存博弈；鹰派-鸽派博弈8,0-5,-54,40,8鹰派鹰派鸽派鸽派鹰派鹰派鸽派鸽派熊熊 2熊熊 1对于每只熊，混合策略纳什均衡的预期收益为：，该值介于-5和+4之间。这是否为纳什均衡焦点焦点？162025181(5)8481818181 博弈的几种重要类型n合作博弈 n竞争博弈n共存博弈n承诺博弈承诺博弈n讨价还价博弈承诺博弈n该博弈为序贯博弈n一个参与者在另一个参与者之前选择决策。n第一个参与者的决策不可撤销

21、且能被第二个参与者观察到。n第一个参与者知道他的决策将被第二个参与者知道。承诺博弈参与者1在参与者2选择决策之前作出决策。5,95,57,65,4122abecdf博弈树博弈的方向参与者1有两种决策a 和 b。参与者2在a之后有两种决策c 和 d在b之后有两种决策e 和 f。承诺博弈5,95,57,65,4122abecdf参与者2声称假如参与者1选择策略a，他将选择策略c，这样的承诺是否可信？可信承诺博弈5,95,57,65,4122abecdf参与者2声称假如参与者1选择策略b，他将选择策略e，这样的承诺是否可信？可信可信承诺博弈5,95,57,65,4122abecdf参与者1会如何选择

22、决策？参与者1应该选择决策 b。承诺博弈5,35,57,65,4122abecdf改变该博弈承诺博弈5,35,57,65,4122abecdf参与者2声称假如参与者1选择策略a，他将选择策略c，这样的承诺是否可信？不可信。假如参与者1选择决策a 参与者2的最佳决策为d。参与者1该如何做？还是选择决策 b。承诺博弈改变该博弈7,35,12122abecdf5,915,5承诺博弈参与者1能否得到15的收益？5,97,35,12122abecdf15,5假如参与者1选择a参与者2会选择c，参与者得到的收益仅为5。假如参与者1选择b参与者2会选择f 参与者得到的收益仅为5。承诺博弈假如参与者1能够改变

23、收益以致参与者2在a之后选择d变得可信，那么参与者1的收益将从5上升至15，新增收益10.5,97,35,12122abecdf15,5承诺博弈5,910,107,35,12122abecdf假如参与者1将收益量5给参与者2，那么参与者2的承诺变得可信。参与者1不能得到15的收益。承诺博弈5,910,107,35,12122abecdf可信纳什均衡称为子博弈完美子博弈完美。这个博弈的子博弈完美，为什么？它要求每个参与者所做的决策必须是理性的。承诺博弈5,910,107,35,12122abecdf可信纳什均衡称为子博弈完美子博弈完美。这个博弈的子博弈完美，为什么？它要求每个参与者所做的决策必须

24、是理性的。承诺博弈5,910,107,35,12122abecdf可信纳什均衡称为子博弈完美子博弈完美。这个博弈的子博弈完美，为什么？它要求每个参与者所做的决策必须是理性的。承诺博弈5,910,107,35,12122abecdf可信纳什均衡称为子博弈完美子博弈完美。这个博弈的子博弈完美，为什么？它要求每个参与者所做的决策必须是理性的。博弈的几种重要类型n合作博弈n竞争博弈n共存博弈 n承诺博弈n讨价还价博弈讨价还价博弈讨价还价博弈n两个参与者对于大小为1的一个饼的分配进行讨价还价。结果如何？n两种方法：n纳什讨价还价模型n鲁宾斯坦讨价还价模型。策略讨价还价n参与者在3个阶段决定如何分配饼，在

25、其它时刻什么都得不到。n参与者A 下期收益的折现率为.n参与者B 下期收益率的折现率为.n参与者轮流提出分配方案，参与者A在第一期先提出分配方案。n假如接受分配方案的参与者接受该方案，那么博弈结束。否则该博弈下期继续进行。策略讨价还价01A01B01ABBAx1(x1,1-x1)YNx2x3(x3,1-x3)(x2,1-x2)(0,0)YYNN第1期:A 分配x1B 做出反应第 2期：B 分配 x2.A 做出反应第 3期：A 分配 x3.B 做出反应策略讨价还价01ABx3YN第3期：A分配x3B 做出反应B对x3如何反应？(x3,1-x3)(0,0)假如1 x3 0则接受；也即当x3 1时接

26、受。知道这一点，A会如何分配？x3=1.=1接受x3=1策略讨价还价01A01B0ABAx1(x1,1-x1)YNx2(x2,1-x2)YN第1期:A 分配 x1.B 做出反应第2期:B 分配 x2.A 做出反应BYN第3期:A 分配 x3=1.B 接受(1,0)(0,0)x3=1策略讨价还价01B0AAx2(x2,1-x2)YN第 2期:B 分配 x2.A 做出反应BYN第3期:A 分配x3=1.B 接受在第3期 A 得到的分配量为1。在第2期，在回应B的分配量x2的时候，A得到1的现值为多少？(1,0)(0,0)A得到1的现值为。策略讨价还价(x2,1-x2)01BAx2YN第 2期：B

27、分配 x2.A 做出反应在第3期 A 得到的分配量为1。在第2期，在回应B的分配量x2的时候，A得到1的现值为。B 最多能分配给A多少？x2=.(,1-)第2期：B 分配x2=.A 接受x3=1策略讨价还价01A01B0ABAx1(x1,1-x1)YNYN第1期：A 分配 x1.B 做出反应BYN第3期：A 分配 x3=1.B 接受第2期：B分配x2=.A 接受x2=(,1-)(1,0)(0,0)策略讨价还价01A01BBAx1(x1,1-x1)YNYN第1期:A 分配 x1.B 做出反应第2期：B 分配x2=.A 接受x2=(,1-)在第2期 A 会接受.这样B在第2期会得到1-。在第1期对

28、于B来说1-的现值为多少？(1-)。(1-)。在第1期最多能向 B分配多少？策略讨价还价01A01BBAx1(1-(1-),(1-)YNYNx2=(,1-)在第2期 A 会接受.这样B在第2期会得到1-。在第1期对于B来说1-的现值为多少？(1-)。在第1期最多能向 B分配多少？1 x1=(1-)；也即x1=1-(1-)。B 会接受。第1期:A 分配 x1.B 做出反应第2期：B 分配x2=.A 接受x3=1策略讨价还价01A01B0ABAYNYN第1期:A 分配x1=1-(1-).B 接受BYNx2=(,1-)(1-(1-),(1-)x1=1-(1-)(1,0)(0,0)第2期：B 分配x2=.A 接受第3期：A 分配 x3=1.B 接受策略讨价还价n注意该博弈在第1期马上结束。n参与者 A得到了1-(1 )单位的分配量。参与者 B得到了(1 )单位的分配量。n谁的分配量大？nx1=1-(1 )1/2(1-)假如，参与者B比A来说过于没有耐心，参与者A 比参与者B得到的份额多。策略讨价还价n假设该游戏可以无限进行下去(无限期)。使用相同的推理方法所得结果表明子博弈完美会导致参与者1和参与者2分别得到：n 和 单位份额n参与者1的分配额上升当 和 。参与者2的分配额上升当 和 。111)1(