博弈论第7讲ppt课件.ppt

《博弈论第7讲ppt课件.ppt》由会员分享，可在线阅读，更多相关《博弈论第7讲ppt课件.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上次内容回顾上次内容回顾动态博弈的概念动态博弈的概念完美信息和完全信息（信息集）完美信息和完全信息（信息集）扩展式表示（博弈树）扩展式表示（博弈树）动态博弈的策略式表示动态博弈的策略式表示逆向归纳法（逆向归纳法（Back Induction）承诺的置信（反国家分裂法）承诺的置信（反国家分裂法）子博弈完美均衡子博弈完美均衡斯塔克博格斯塔克博格(Stackelberg)模型模型1子博弈完美均衡与子博弈完美均衡与BI2先动优势？后动优势先动优势？后动优势NIMStep or throw34讨价还价实例讨价还价实例q假设两人就冰激凌的分配讨价还价。冰激凌会随时间而融化。q假设冰激凌重量为100克，每一

2、回合融化10克（即10个回合全部融化）。q假设甲先提议，然后是乙。5讨价还价实例讨价还价实例两回合谈判的均衡结果推导过程：第二回合乙提议之后博弈结束，因此相当于他面临独裁博弈。此时，他会将全部冰激凌分给自己（比例为1）。由于已经化掉1/10，因此，尽管乙得到了全部，但实际上是90克；甲什么也没得到。再回溯到第一回合，为了不使乙反对，甲必须使得乙所获得的冰激凌实际额不低于其第二回合的数量。因此，均衡结果是甲10克，乙90克6讨价还价实例讨价还价实例三回合谈判的均衡结果推导过程：第三回合甲提议之后博弈结束，因此相当于他面临独裁博弈。此时，他会将全部冰激凌分给自己（比例为1）。由于已经化掉2/10，

3、因此，尽管甲得到了全部，但实际上是80克；第二回合中，为了不使甲反对，乙必须使得甲所获得的冰激凌实际额不低于其第三回合的数量，即甲80克，乙10克；再回溯到第一回合，为了不使乙反对，甲必须使得乙所获得的冰激凌实际额不低于其第二回合的数量，即乙10克，甲90克。因此，均衡结果是甲90克，乙10克7讨价还价实例讨价还价实例同学们可以自己推导一下，第9回合和第十回合的均衡结果是多少？8讨价还价实例讨价还价实例q第9回合，甲60克，乙40克；q第10回合，甲乙各50克。q推导过程9和10回合.doc9讨价还价实例讨价还价实例结论：1，低于10回合外，谁最后提议，谁有优势。2，谈判的回合越多，两人的利益

4、分享额越接近平均分配。3，回合足够多得话，平均分配合作利益。10经典案例经典案例(2):讨价还价博弈讨价还价博弈q讨价还价(bargaining)是市场中最常见、普通的事情。也是博弈论中典型的动态博弈问题。q讨价还价模型还可以推广到谈判问题。q这里介绍的是讨价还价最为经典的模型。11经典案例经典案例(2):讨价还价博弈讨价还价博弈q假设有两个人分割一块蛋糕，参与人1先出价(offer)，参与人2可以选择接受(accept)或拒绝(reject)；q如果参与人2接受，博弈结束，蛋糕按参与人1的方案分配。如果参与人2拒绝，参与人2出价，参与人1决定接受或拒绝；q如果参与人1接受，博弈结束，蛋糕按参

5、与人2的方案分配。如果参与人1拒绝，参与人1再出价12经典案例经典案例(2):讨价还价博弈讨价还价博弈q上述过程反复进行，直到一个参与人的出价被另一个参与人接受为止。q这是一个无限期完美信息博弈，参与人1在1, 3, 5,出价，参与人2在时期2,4,6,出价。13经典案例经典案例(2):讨价还价博弈讨价还价博弈q若用x表示参与人1的份额，(1-x)表示参与人2的份额，x1和(1-x1)分别是参与人1出价时参与人1和参与人2的份额，x2和1-x2分别是参与人2出价时参与人1和参与人2的份额。q假定参与人1和参与人2的贴现因子分别为1和2，如果博弈在时期t结束，t是参与人i的出价阶段，则参与人1支

6、付的贴现值是1= 1t-1xi,参与人2支付的贴现值是2= 2t-1(1-xi)14经典案例经典案例(2):讨价还价博弈讨价还价博弈q结合切蛋糕问题，贴现值既可以理解为v资金的时间价值v由于蛋糕由于未被分割出去所造成的自然缩减。v双方的耐心程度。15经典案例经典案例(2):讨价还价博弈讨价还价博弈q问题分析v由于该博弈是无限期博弈，因此，不能直接采用逆推归纳法。v为分析上述问题，先考虑阶段数有限的情形。16经典案例经典案例(2):讨价还价博弈讨价还价博弈q有限阶段讨价还价问题v假定博弈只进行两个时期，在T=2，参与人2出价，如果他提出x2=0,参与人1会接受(假定参与人在接受和拒绝之间无差异时

7、，我们假定他选择接受)。v因为博弈在T=2时，参与人1再没有讨价还价的机会。17经典案例经典案例(2):讨价还价博弈讨价还价博弈v参与人2在T=2时得到的1单位等价于在t=1时的2单位，因此，如果参与人1在t=1时出价1-x1 2,参与人2会接受；v因为参与人1没有必要给参与人2多于他会接受的最低份额，博弈均衡结果是参与人1得到x=x1=1- 2,参与人2得到1-x =218 (a) T=1时参与人1出价情况 (b)T=2时参与人2出价情况 图图2-18 两阶段讨价还价示意两阶段讨价还价示意21-2经典案例经典案例(2):讨价还价博弈讨价还价博弈19经典案例经典案例(2):讨价还价博弈讨价还价

8、博弈q再假定T=3v在最后阶段，参与人1出价，他可以得到的最大份额是x1=1；v因为参与人1在T=3时1单位等价于T =2时的1单位，因此，如果参与人2在T=2时出价x2=1,参与人1将会接受；v因为参与人2在T=2的（1-1）单位等价于T=1时的2（1-1）,因此，如果参与人1在T=1时出价1-x1= 2（1-1），参与人2将会接受。v因此，子博弈精炼均衡结果是x=1- 2（1-1）20q当T=4, 5, 等有限整数值时，仿照前述方法，可以推导出任何给定的T的子博弈精炼纳什均衡。v如果1=2=0，不论T为多少，子博弈精炼均衡的结果是 x =1；就是说，如果两个参与人都是绝对无耐心的，第一个出

9、价的人得到整个蛋糕；v如果2=0，不论1为多少，子博弈精炼均衡结果仍然是x=1;v如果1=0, 20, 子博弈精炼均衡结果是x=1-2经典案例经典案例(2):讨价还价博弈讨价还价博弈21经典案例经典案例(2):讨价还价博弈讨价还价博弈v如果1=2=1, 即双方都有无限耐心，那么，如果T=1,3,5,均衡结果是x=1；如果T=2,4,6,，均衡结果是x=0。v这里的结果可以称之为“后动优势”（last-mover advantage）22经典案例经典案例(2):讨价还价博弈讨价还价博弈v一般说来，如果0i1, i=1,2，均衡结果不仅依赖于贴现因子的相对比率，而且还依赖于博弈时期T和谁在最后阶段

10、出价。然而，这种依存关系随着T的变大而变小v当T趋于无穷时，我们得到“先动优势”：如果1=2=，唯一的纳什均衡结果为x=1/(1+)23q无限阶段讨价还价问题v罗宾斯坦恩(Rubinstein, 1982):在无限期轮流出价博弈中，唯一的子博弈精炼纳什均衡结果是212*11x经典案例经典案例(2):讨价还价博弈讨价还价博弈24q无限阶段讨价还价问题v罗宾斯坦恩(Rubinstein, 1982):在无限期轮流出价博弈中，唯一的子博弈精炼纳什均衡结果是v如果1=2=，则212*11x11*x经典案例经典案例(2):讨价还价博弈讨价还价博弈25经典案例经典案例(2):讨价还价博弈讨价还价博弈v上述

11、定理的证明v由于T=,博弈没有最后阶段，不可能使用逆推归纳法。v但根据Shaked, Sutton(1984)，因为从参与人1出价的任何一个阶段开始的子博弈等价于从T=1开始的整个博弈，因此可转换为有限阶段讨价还价问题。v见图2-19。26从任一阶段开始的子博从任一阶段开始的子博弈（弈（t为奇数）为奇数）图图2-19 无限阶段讨价还价问题无限阶段讨价还价问题t=1t=2t=kt=3从从t=1阶段开始的整个博弈阶段开始的整个博弈经典案例经典案例(2):讨价还价博弈讨价还价博弈27v 假定在时期t3时参与人1出价，参与人1能得到的最大份额是M;v 对参与人1而言，t期的M等价于t-1期的1M，参与

12、人2知道在t-1时期的任何x21M的出价将被参与人1接受，因此参与人出价x2= 1M,自己获得1- 1M;v 对于参与人2而言，t-1期的1- 1M等价于t-2期的2 (1- 1M)，参与人知道在t-2期的任何x12)的结局。图图2-24 2-24 修改的性别战修改的性别战 3, 10, 00, 01, 3TBLR1InOut2, 252前向归纳法一例：烧钱博弈前向归纳法一例：烧钱博弈q因此，在第二阶段，参与人1必然要选取策略T.图图2-24 2-24 修改的性别战修改的性别战 3, 10, 00, 01, 3TBLR1InOut2, 253前向归纳法一例：烧钱博弈前向归纳法一例：烧钱博弈q预

13、见到上述情况，参与人2将选择策略L图图2-24 2-24 修改的性别战修改的性别战 3, 10, 00, 01, 3TBLR1InOut2, 254前向归纳法一例：烧钱博弈前向归纳法一例：烧钱博弈q因此，按照前向归纳法逻辑，合理结局是图图2-24 2-24 修改的性别战修改的性别战 3, 10, 00, 01, 3TBLR1InOut2, 255重复博弈和无名氏定理重复博弈和无名氏定理q重复博弈(repeated game)的定义v指同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈(stage game)”。v如两个多次犯罪的“囚徒问题”。q由于动态博弈是相机行动，反映到重复博弈中，就是可

14、以使自己在某个阶段的博弈选择依赖于其他参与人过去的行动历史。56重复博弈和无名氏定理重复博弈和无名氏定理v如囚徒困境的重复博弈的一个策略可以是：“如果这次你选择了坦白，我下次将选择坦白；如果你这次选择了抵赖，我下次将选择抵赖” 。v因此，参与人在重复博弈中的战略空间远远大于和复杂于在每个阶段博弈中的战略空间。57重复博弈和无名氏定理重复博弈和无名氏定理v影响重复博弈均衡结果的主要因素是博弈重复次数和信息的完备性(completeness)。v重复次数对参与人可能会有的影响是：参与人为了获得长远利益而牺牲眼前利益的策略成为可能。v关于完备性，简单地说，但一个参与人的支付函数不为其他参与人所知时，

15、该参与人可能有积极性建立一个“好”的声誉(reputation)以换取长远利益。v在社会行为中，经常可以看到本质不好的人在相当长的时期内干好事的原因。58重复博弈和无名氏定理重复博弈和无名氏定理q有限次重复博弈：连锁店悖论v考虑如图2-25所示的市场进入博弈。v如果进入者先行动，则可表示为完全信息动态博弈的博弈树形式，见图2-26。图中A表示进入者，B表示在位者。图图2-25 市场进入博弈市场进入博弈默许斗争进入40，50-10，0不进入0, 3000,300在位者在位者进入者进入者59v该博弈唯一的子博弈精炼纳什均衡结果是进入者进入，在位者默许，分别得到40和50的支付。不进入进入斗争默许(

16、0,300)(0,300)图2-26 市场进入博弈ABB(40,50) (-10,0)默许斗争重复博弈和无名氏定理重复博弈和无名氏定理60重复博弈和无名氏定理重复博弈和无名氏定理v现在假定同样的市场有20个（可以理解为在位者有20个连锁店），进入者每次进入一个市场，博弈就变成了20次重复博弈。v假定进入者先进入第1个市场，在位者应该作如何反应？v按照一般的认识，在位者应该坚决进行斗争，即便是损失该市场，但可以阻止其他19个市场的进入者的进入。v但按照子博弈精练纳什均衡分析方法，却与上述结论相左。61重复博弈和无名氏定理重复博弈和无名氏定理q分析过程如下：v设想前19个市场已被进入，进入者现在进

17、入第20个市场。因为在最后阶段，选择斗争已没有任何威慑意义，在位者最优选择是默许，进入者将选择进入。v现在考虑第19个市场。因为无论在位者选择什么行动，第20个市场上的均衡结果不受影响（因为进入者知道第20各市场上在位者将选择默许），在位者最优选择仍然是默许。62重复博弈和无名氏定理重复博弈和无名氏定理v如此一直倒推回去，我们得到这个博弈的唯一子博弈精炼均衡是在位者在每一个市场上都选择默许，进入者在每一个市场上选择进入。v这就是所谓的“连锁店悖论”(chain-store paradox, Selten,1978)63重复博弈和无名氏定理重复博弈和无名氏定理q囚徒困境问题与市场进入博弈类似，只

18、要博弈的重复次数是有限的，最后阶段博弈的唯一纳什均衡是两个囚徒都选择坦白，且“总是坦白”是唯一的子博弈精炼均衡。q上述结果可以一般化为下述定理。v定理：令G是阶段博弈，G(T)是G重复T次的重复博弈(T ei的v （in V），存在一个贴现因子 *1，使得对于所有的 *, v=(v1,v2,vn)是一个特定的子博弈精炼纳什均衡结果。75重复博弈和无名氏定理重复博弈和无名氏定理q简单地说，无名氏定理说的是，在无限次重复博弈中，如果参与人有足够的耐心（足够大），那么，任何满足个人理性的可行的支付向量都可以通过一个特定的子博弈精炼均衡得到。q在无名氏定理中，阶段博弈的纳什均衡a*及其支付向量e=(e

19、1,e2,en)是达到任何精炼均衡结果v的惩罚点（或称为纳什威胁点，Nash Threat Point）。76重复博弈和无名氏定理重复博弈和无名氏定理q以囚徒困境问题为例，a*=(坦白，坦白)，e=(-8,-8)。q正是由于害怕触发阶段博弈纳什均衡，参与人才有积极性保持合作。77重复博弈和无名氏定理重复博弈和无名氏定理q无名氏定理中的可行支付集合Vv可用未来支付的贴现值之和代表支付函数，如同前面的证明中使用的那样。v也可用平均支付(average-payoffs)表示支付函数。111itt78重复博弈和无名氏定理重复博弈和无名氏定理q无名氏定理中的可行支付集合Vv可用未来支付的贴现值之和代表支

20、付函数，如同前面的证明中使用的那样。v也可用平均支付(average-payoffs)表示支付函数。v无名氏定理中的支付指的是平均支付。vV=(v1,v2,vn)是可行支付向量，如果它是阶段博弈G的纯战略支付的凸组合。v所有可行支付向量构成可行支付集合V。79v 以囚徒问题为例，红线围成的区域即为囚徒困境问题的可行支付集合。v 四个角点是纯战略组合下的支付，由四个角点构成的闭区域为有混合策略组合下可能的支付向量。v 纳什威胁点为e=(-8,-8)。无名氏定理的含义即为：如果足够接近于1，由点(-8,-8)两条垂直线围成的可行集合上的任意一点都可以是子博弈精炼纳什均衡结果。-10, 0-1, -1-8, -8图图2-28 囚徒困境问题的可囚徒困境问题的可行支付集合行支付集合-10, 0重复博弈和无名氏定理重复博弈和无名氏定理找出全部子博弈；求解子博弈精练纳什均衡和博弈的结果。80