第6章-博弈理论专题.ppt

第六章博弈理论专题,第一节零和博弈和非零和博弈第二节相关均衡第三节重复博弈第四节消耗战博弈第五节抢先博弈,第一节零和博弈和非零和博弈,在零和博弈（Zero-SumGame）中，博弈一方获益必然意味着博弈另一方的损失，博弈各方的收益和损失相加总和永远为“零”。赌博是典型的零和博弈。与零和博弈不同，在非零和博弈（Non-Zero-SumGame）中博弈各方的收益总和不是零。博弈一方的收益并不建立在博弈另一方损失的基础上。博弈双方有可能达到“双赢”的结果。,国际贸易早期的重商主义理论认为：国际贸易是零和博弈。贸易顺差国家的福利水平增长建立在贸易逆差国家福利水平下降的基础上。因此，重商主义者认为一个国家应该尽可能的多出口、少进口。亚当斯密（AdamSmith）指出：财富来自生产领域而非流通领域，基于两国生产技术绝对差异的国际贸易是双赢的，能提高贸易参与国双方的福利水平。因此，政府没有必要干预国际贸易，应该实行自由贸易政策。不管是逆差国家还是顺差国家，都能从国家贸易中受益。,零和博弈和非零和博弈示意图,第二节相关均衡,相关均衡（CorrelatedEquilibrium）的概念首先由经济学家罗伯特奥曼（RobertAumann）提出。在他发表于1974年的文章中，奥曼指出：在相关均衡中，博弈参与者得到的收益可能高于混合策略纳什均衡。例如：考虑如下完全信息静态博弈,在上表所示的完全信息动态博弈中，存在纯策略纳什均衡和混合策略纳什均衡。根据“划横线法”，博弈的两个纯策略纳什均衡：（L，V）和（R，U）。博弈还存在一个混合策略纳什均衡。可以证明：在混合策略纳什均衡中：参与者1选择策略L的概率为p=2/3；参与者2选择策略U的概率为q=2/3；参与者1选择策略L或策略R均能得到收益14/3；参与者2选择策略U或策略V均能得到收益14/3。,相关均衡,设计了这样的机制：考虑一个外生随机变量X，该随机变量X可能的取值为1、2、3，且P(X=1)=P(X=2)=P(X=3)=1/3当随机变量实现取值后：博弈参与者1会得到的信息是：X是否取值是1。博弈参与者2会得到的信息是：X是否取值是2。当随机变量的取值实现后：如果参与者1被告知随机变量X的值为1，那么参与者1选择策略R；如果参与者1被告知随机变量X的值不为1，那么参与者1选择策略L。如果参与者2被告知随机变量X的值为3，那么参与者2选择策略V；如果参与者2被告知随机变量X的值不为3，那么参与者2选择策略U。,在这种机制下，参与者1和参与者2的策略决策不再完全独立。参与者1和参与者2的决策均和随机变量X的取值相关。也就是说：参与者1和参与者2的策略选择是“相关”的。这种情况下的均衡称为“相关均衡”。,随机变量X不同取值情况下的博弈均衡,由于P(X=1)=P(X=2)=P(X=3)=1/3博弈参与者1的预期收益5博弈参与者2的预期收益5在相关均衡下，两名博弈参与者的收益均为5。在混合策略纳什均衡中，博弈双方的收益均为14/3。因此，在相关均衡中，两名博弈参与者的收益均高于混合策略纳什均衡的收益。在混合策略纳什均衡中，各博弈参与者按照一定的概率分布随机选择自己的策略。然而在相关博弈中，博弈参与者并不是随机选择自己的策略，而是根据随机变量X的取值进行策略选择。,性别博弈与相关均衡,根据“划横线法”，可以博弈的两个纯策略纳什均衡：（看足球，看足球）和（听昆曲，听昆曲）。博弈还存在一个混合策略纳什均衡。,性别博弈的支付矩阵,可以证明：在混合策略纳什均衡中：男方选择“看足球”的概率为p=2/3；女方选择“看足球”的概率为q=2/3；男方选择策略“看足球”或“听昆曲”均能得到收益2/3；女方选择策略“看足球”或“听昆曲”均能得到收益2/3。考虑这样的机制设计每到周末，这对男女朋友通过扔一个均匀硬币来决定各自的策略。如果硬币正面朝上，男方选择“看足球”，女方选择“看足球”。如果硬币反面朝上，男方选择“听昆曲”，女方选择“听昆曲”。,在相关均衡下，两名博弈参与者的收益均为3/2。在混合策略纳什均衡中，博弈双方的收益均为2/3。在相关均衡中，两名博弈参与者的收益均高于混合策略纳什均衡的收益。从直观上说，在性别博弈中，相关均衡的推理过程和思维模式比混合策略纳什均衡的推理过程和思维模式更符合人们的习惯,专栏：罗伯特奥曼简介,罗伯特奥曼（RobertAumann）1930年出生于德国法兰克福，犹太人。1938年随家人迁往美国纽约，幸运的躲过了纳粹对犹太人的残酷迫害。奥曼1950年获得纽约城市学院数学学士学位，1955年获得麻省理工学院纯数学博士学位，其博士论文研究的是代数拓扑学中的纽结理论（KnotTheory）。1956年，奥曼进入以色列耶路撒冷希伯莱大学任教至今。,现任耶路撒冷希伯来大学理性分析中心教授、纽约州立大学斯坦尼分校经济系和决策科学院教授、以色列数学俱乐部主席、美国经济联合会荣誉会员等。他还担任国际对策论杂志、数理经济学杂志、经济学理论杂志、运筹学数学等多家专业杂志社的编辑。奥曼第一个提出了博弈论中“相关均衡”的概念。在非合作博弈中，相关均衡比传统的纳什均衡更具灵活性。奥曼在“重复博弈”研究领域也做出了杰出贡献。奥曼第一个系统性定义了博弈中的“共同知识”。,奥曼使用博弈论分析犹太法典中的“塔木德难题”，解决了长期悬而未决的遗产分割问题。奥曼把这篇文章献给了他在战场上死去的儿子萨蒙（Shlomo）。由于在博弈论领域的突出贡献，奥曼和美国经济学家托马斯谢林（ThomasSchelling）分享了2005年诺贝尔经济学奖。,专栏：“塔木德难题”及奥曼的解决方案,塔木德是一部犹太教经典著作，地位仅次于圣经，是犹太教口传律法汇编。创作于2世纪至6世纪。整书反映7世纪前犹太教的宗教信仰、口传律法、伦理规范和社团生活的历史发展。在塔木德妇女部婚书卷里记载了这样一个财产分配的故事。“犹太教规定：一个人死后，他的妻妾有权继承他的财产。假设一个人有三个伴侣：分别是妻子、妾和婢女。如果这个人的遗产超过600金。那么妻子有权要求继承300金，妾有权要求得到200金，婢女有权要求得到100金。如果这个人的财产不足600金，怎样将有限的财产在妻子、妾和婢女之间分配呢？,犹太教规定的分配方案如上表所示,犹太教遗产分配方案,按照惯常的思维方式：当遗产超过600金时，妻子可分得300金，妾得到200金，婢女得到100金。说明妻子、妾和婢女在继承遗产上享有的权利比例为：3:2:1。那么当遗产不足600金时，妻子应得遗产的3/6；妾应得遗产的2/6；婢女应得遗产的1/6。但是塔木德中的分配方案与此直观逻辑不符。怎样解释塔木德中这个与直觉看似相悖的遗产分配方案，成为几千年来学者们十分疑惑的问题。通常将此问题称为“塔木德难题”。,奥曼通过对塔木德的深入阅读，利用现代博弈理论完美的解决了困扰了学者们多年的“塔木德”难题。奥曼在塔木德损害部中门卷中找到了这样一个故事：“甲、乙两个人共同抓着一件大衣来到法官面前。如果甲、乙二人都宣称自己拥有这件大衣的全部所有权，那么甲乙两人分别得到这件大衣的二分之一。如果甲宣称自己拥有这件大衣的全部所有权、乙宣称自己拥有这件大衣的二分之一所有权，那么法官将宣判给甲大衣所有权的四分之三，给乙大衣所有权的四分之一”。,根据这个故事，奥曼仔细思索了古代犹太律法原则后，总结出了古代犹太律法的三个原则：第一：仅分割具有争议的财产。对没有争议的财产不予分割。第二：宣称拥有更多财产权力的一方最终得到的收益不少于宣称拥有较少财产权力的一方。第三：对有争议财产进行分配时，当财产诉求者超过两人时，将所有提出财产诉求者按其诉求金额排序。最小者自成一组，剩下所有诉求者组成另一组，争议财产在两组间公平分配。根据这样的分配原则，可以解释对争执大衣的分配原则。,明确了“大衣分配原则”后，即可将这种思路应用于解决“塔木德难题”。在“塔木德难题”中，如果遗产仅有100金，由于妻子、妾和婢女都宣称有权力得到这100金。因此，将这100金平均分配。妻子、妾和婢女均得到33.3金。,如果遗产有200金，那么由于婢女宣称自己只拥有100金的继承权，因此剩余的100金已经可以明确分配给妻子和妾。将妻子和妾看成一个整体，不妨称为“妻妾集团”。“妻妾集团”需要与婢女分割婢女宣称自己有权继承的那100金。由于婢女和“妻妾集团”均宣称拥有这100金的继承权。因此婢女和“妻妾集团”各得50金。婢女的财产继承结束。“妻妾集团”此时总共拥有150金。由于妻子和妾都宣称拥有这150金的继承权，因此这150金在妻子和妾之间平均分配，每人得到75金。因此当遗产为200金时，分配结果为：妻子得到75金，妾得到75金，婢女得到50金。,如果遗产有300金，那么由于婢女宣称自己只拥有100金的继承权，因此剩余的200金已经可以明确分配给妻子和妾。“妻妾集团”需要与婢女分割婢女宣称自己有权继承的那100金。婢女和“妻妾集团”各得50金。婢女的财产继承结束。“妻妾集团”此时总共拥有250金。由于妾宣称自己拥有200金的继承权，因此其中50金可以明确分配给妻子。妻子和妾只需要分割妾宣称自己有权继承的那200金。妻子和妾各得100金。妾的财产继承结束。妻子总计得到150金。因此当遗产为300金时，分配结果为：妻子得到150金，妾得到100金，婢女得到50金。,根据“大衣分配原则”中的犹太律法思想，通过利用现代博弈的观点，奥曼解决了困扰学者多年的“塔木德难题”。“塔木德”难题的成功破解一方面显示了现代博弈理论的强大解释力和奥曼的高超技巧，另一方面也揭示出古代犹太民族的智慧深度和精湛思维。,第三节重复博弈,重复博弈（RepeatedGame）是一类特殊的完全信息动态博弈。在重复博弈中存在一个重复多次的基础博弈（BaseGame）。基础博弈又常被称为阶段博弈（StageGame）。基础博弈被重复有限次的博弈称为有限次重复博弈。相应的，基础博弈被重复无限次的博弈称为无限次重复博弈或无穷次重复博弈。与重复博弈相对应，非重复博弈也常被称为单一阶段博弈（SingleStageGame）或单次博弈（SingleShotGame）。单次博弈、有限次重复博弈、无限次重复博弈的求解思路和均衡往往存在很大区别。,一、有限次重复博弈,“锤头、剪刀、布”博弈的支付矩阵,“锤头、剪刀、布”博弈没有纯策略纳什均衡，但存在一个混合策略纳什均衡。,如果将“锤头、剪刀、布”博弈从博弈一次转化为博弈多次。即博弈参与者进行多轮相同的博弈。在每次博弈中，博弈参与者的策略是否会发生变化呢？定理：在有限次重复博弈中，如果单次博弈为零和博弈，那么增加博弈次数不会改变博弈均衡。简单重复多次“锤头、剪刀、布”博弈，不会改变两名博弈参与者的策略选择。两名博弈参与者在每次博弈中，都按照单次博弈的混合策略纳什均衡行动。,“囚徒困境”博弈的纯策略纳什均衡：（坦白、坦白）。,“囚徒困境”博弈的支付矩阵,定理：在有限次重复博弈中，如果单次博弈存在唯一的纯策略纳什均衡，则有限次重复博弈的唯一均衡是：各博弈参与者在每阶段都采用该纯策略纳什均衡中的策略。有限次重复博弈不过是一次性博弈的简单重复。由于（坦白、坦白）是“囚徒困境”博弈唯一的纯策略纳什均衡，因此在任意有限次重复博弈“囚徒困境”中，两名嫌疑人每次博弈都必然选择“坦白”策略。,二、连锁超市悖论,莱茵哈德泽尔滕（ReinhardSelten）1978年发表了著名的“连锁超市悖论（TheChainStoreParadox）”。假设市场中有一个连锁超市，不妨称其为博弈参与者A。连锁超市在20个城市中有自己的店面。将这20个城市进行编号，分别记为1,2,20。在每一个城市都有一个潜在的进入者。潜在进入者逐渐积累资本。只有当潜在进入者积累的资本达到一定数量时，潜在进入者才有可能进入市场。,不妨将城市k中的潜在进入者称为博弈参与者k，k=1,2,20。因此，博弈共有21个参与者：连锁超市（参与者A）和20个潜在进入者。在初始时，假设20个潜在进入者都没有足够的资本进入市场。但随着时间的推移，潜在进入者积累的资本逐渐增多。假设城市1的潜在进入者将首先积累到足够的资本额进入市场，其次是城市2中的潜在进入者，最后是城市20中的潜在进入者。,当城市k中的潜在进入者积攒了足以进入市场的资本后，他有两个策略选择：“进入”和“不进入”。当博弈参与者k选择“不进入”时，在城市k中的博弈结束。当博弈参与者k选择“进入”时，参与者A有两个策略选择：“斗争”和“默许”。,“连锁超市悖论”的基础博弈,根据“连锁超市悖论”的基础博弈。当潜在进入者选择“不进入”时，博弈结束。潜在进入者得到收益1。连锁超市独享垄断利润，得到收益5。当潜在进入者选择“进入”时，连锁超市具有两个策略选择。当连锁超市选择“斗争”策略时，潜在进入者和连锁超市均得到收益0。当连锁超市选择“默许”策略时，潜在进入者和连锁超市均得到收益2。,“连锁超市悖论”的基础博弈的策略型表达式,连锁超市和潜在进入者之间的重复博弈是一个动态博弈。博弈共有九种情况。,博弈进行到城市2时的博弈树,情形一：如果潜在进入者1选择“不进入”，那么轮到潜在进入者2进行策略选择。如果潜在进入者2选择“不进入”，那么连锁超市在城市1和城市2均保持其垄断地位。在每个城市均得到收益5，总计得到收益10。两个城市的潜在进入者均得到收益1。即：潜在进入者1、连锁超市、潜在进入者2的收益为（1，10，1）。情形二：如果潜在进入者1选择“不进入”、潜在进入者2选择“进入”，那么连锁超市需要选择自己在城市2的策略。如果连锁超市在城市2选择“斗争”，那么连锁超市在城市1得到收益5，在城市2得到收益0，总计得到收益5。潜在参与者1得到收益1，潜在参与者2得到收益0。即：潜在进入者1、连锁超市、潜在进入者2的收益为（1，5，0）。,情形三：如果潜在进入者1选择“不进入”、潜在进入者2选择“进入”、连锁超市在城市2选择“默许”，那么连锁超市在城市1得到收益5，在城市2得到收益2，总计得到收益7。潜在参与者1得到收益1，潜在参与者2得到收益2。即：潜在进入者1、连锁超市、潜在进入者2的收益为（1，7，2）。情形四：如果潜在进入者1选择“进入”，那么连锁超市需要选择自己在城市1的策略。如果连锁超市在城市1选择“斗争”，那么连锁超市在城市1得到收益0，潜在参与者1得到收益0。在城市2，潜在进入者2进行策略选择。如果潜在进入者2选择“不进入”，那么连锁超市在城市2得到收益5，潜在进入者2得到收益1。即：潜在进入者1、连锁超市、潜在进入者2的收益为（0，5，1）。,情形五：如果潜在进入者1选择“进入”、连锁超市在城市1选择“斗争”，那么连锁超市在城市1得到收益0，潜在参与者1得到收益0。在城市2，如果潜在进入者2选择“进入”，连锁超市选择“斗争”，那么连锁超市在城市2得到收益0，潜在进入者2得到收益0。连锁超市在两个城市中总计得到收益0。即：潜在进入者1、连锁超市、潜在进入者2的收益为（0，0，0）。情形六：如果潜在进入者1选择“进入”、连锁超市在城市1选择“斗争”，那么连锁超市在城市1得到收益0，潜在参与者1得到收益0。在城市2，如果潜在进入者2选择“进入”，连锁超市选择“默许”，那么连锁超市在城市2得到收益2，潜在进入者2得到收益2。即：潜在进入者1、连锁超市、潜在进入者2的收益为（0，2，2）。,情形七：如果潜在进入者1选择“进入”，连锁超市在城市1选择“默许”，那么连锁超市在城市1得到收益2，潜在参与者1得到收益2。在城市2，潜在进入者2进行策略选择。如果潜在进入者2选择“不进入”，那么连锁超市在城市2得到收益5，潜在进入者2得到收益1。连锁超市在两个城市中总计得到收益7。即：潜在进入者1、连锁超市、潜在进入者2的收益为（2，2，0）。情形八：如果潜在进入者1选择“进入”、连锁超市在城市1选择“默许”，那么连锁超市在城市1得到收益2，潜在参与者1得到收益2。在城市2，如果潜在进入者2选择“进入”，连锁超市选择“斗争”，那么连锁超市在城市2得到收益0，潜在进入者2得到收益0。即：潜在进入者1、连锁超市、潜在进入者2的收益为（2，2，0）。,情形九：如果潜在进入者1选择“进入”、连锁超市在城市1选择“默许”，那么连锁超市在城市1得到收益2，潜在参与者1得到收益2。在城市2，如果潜在进入者2选择“进入”，连锁超市选择“默许”，那么连锁超市在城市2得到收益2，潜在进入者2得到收益2。连锁超市在两个城市中总计得到收益4。即：潜在进入者1、连锁超市、潜在进入者2的收益为（2，4，2）。在了解了m=2时的连锁超市博弈后，便不难理解m等于任意自然数的连锁超市博弈的博弈模式。,“连锁超市悖论”的由来,可以通过两种思路求解“连锁超市悖论”的均衡。第一种思路是根据“逆向归纳法”，由最后一期博弈均衡开始，从后向前，找到整个博弈的均衡。第二种思路是通过“威慑原理（TheDeterrenceTheory）”，寻找博弈的均衡解。原则上两种思路找到的均衡应该相同，但实际并非如此，这构成了“连锁超市悖论”。,“连锁超市博弈”是一个有限次重复博弈。博弈的次数与城市个数相等。不失一般性，假设城市数目为20。按照“逆向归纳法”的求解思路，首先考察第20个城市的博弈情况。在第20个城市中，潜在进入者20与连锁超市进行单阶段博弈。根据完全且完美信息动态博弈的求解方法，在第20个城市中，潜在进入者20将选择“进入”，连锁超市会选择“默许”。,根据“逆向归纳法”求解“连锁超市博弈”,根据“逆向归纳法”，从后向前倒推一期。在第19个城市，潜在进入者19的最优策略也是“进入”，连锁超市的最优策略是“默许”。，依此类推，在第1个城市，潜在进入者1的最优策略也是“进入”，连锁超市的最优策略是“默许”。对于任意的k，k=1,2,20，都有：潜在进入者k选择“进入”，连锁超市选择“默许”。在这样的均衡下，每个潜在进入者均得到收益2，连锁超市得到收益40。,根据“威慑原理”，连锁超市不一定会选择“默许”策略。试想这样的情形：在第1个城市，潜在进入者1选择了“进入”，但连锁超市选择了“斗争”。在这种情况下，潜在进入者1得到收益0。如果潜在进入者1选择“不进入”，至少可以得到收益1。潜在进入者1进入市场后，非但没有得到收益2，反而仅得到收益0。可以用“偷鸡不成反蚀一把米”来形容潜在进入者1的境遇。,根据“威慑原理”求解“连锁超市博弈”,在城市1的博弈结束后，进入到在城市2的博弈阶段。城市1中的潜在进入者1的境遇对城市2的潜在进入者具有威慑作用。潜在进入者2会担心：自己选择“进入”后，如果连锁超市选择“斗争”，那么自己也会面临得不偿失的窘境。如果潜在进入者2仍然坚持选择“进入”，而连锁超市再一次选择“斗争”，那么发生在城市1和城市2的博弈结果对后面将要发生的博弈会产生震慑作用。,不妨假设，在前5个城市中，潜在进入者均选择“进入”，而连锁超市也无一例外的选择了“斗争”，那么前五个城市传递出来的博弈信息已经足以令后面的潜在进入者感到震慑。之后进行博弈的潜在进入者很有可能放弃“进入”策略，转而选择“不进入”。在这种情况下，前5个城市的潜在进入者得到收益0，后面15个城市的潜在进入者得到收益1。连锁超市在前5个城市中得到收益0，在后面15个城市中得到收益5。因此连锁超市在20个城市中总计得到收益75。,根据“逆向归纳法”求解出的“连锁超市博弈”的均衡为：对于任意的k，k=1,2,20，都有：潜在进入者k选择“进入”，连锁超市选择“默许”。在这样的均衡下，每个潜在进入者均得到收益2，连锁超市得到收益40。在“威慑原理”下，只要潜在进入者选择“进入”，连锁超市就选择“斗争”，连锁超市通过自己的强势行为以达到震慑后面的潜在进入者的目的。可以证明：只要连锁超市能成功吓退9个城市中的潜在进入者，连锁超市得到收益就会高于按照“逆向归纳法”得到的均衡中的收益。,三、无限次重复博弈,在单阶段“囚徒困境”博弈中，两名嫌疑人必然选择“坦白”策略。在有限次重复博弈的“囚徒困境”博弈中，两名嫌疑人也必然选择“坦白”策略。无穷次重复博弈“囚徒困境”的博弈规则：甲乙两名嫌疑人预期到二人将进行无限次“囚徒困境”博弈。因此二人约定：两人先验的认为对方会坚守承诺，选择“不坦白”。一旦发现对方选择了“坦白”策略，那么自己将在未来永远选择“坦白”作为报复。这样的机制能否保证两名嫌疑人信守“不坦白”的承诺，相互忠诚呢？,如果要使嫌疑人甲在第一次博弈时选择“不坦白”，必须满足不等式无穷次重复博弈“囚徒困境”中如果两名嫌疑人均只顾眼前、不管将来，那么两名嫌疑人也必然选择“坦白”策略。如果两名嫌疑人都非常重视未来的收益，那么有可能两人会同时选择“不坦白”策略。,第四节消耗战博弈,消耗战（WarofAttrition）博弈可以看成是“斗鸡博弈”的一种演化形式。,“斗鸡博弈”的支付矩阵,消耗战博弈：两名博弈参与者在独木桥上迎面对峙。时间在一分一秒的流逝，两名博弈参与者比拼的是彼此的耐力。如果两人同时前进，那么两人都会从独木桥上掉下，这是双方都不愿发生的结果。因此，两人只能进行消耗战。哪一方首先坚持不住退却了，那么另一方就获得了消耗战的胜利，获胜方得到奖额V。退却的一方一无所获，白白消耗了体力和精力进行对峙。,消耗战博弈的定义,消耗战博弈有两个纯策略纳什均衡：（甲选择“永不退却”、乙选择“总是退却”）和（甲选择“总是退却”、乙选择“永不退却”）。消耗战博弈还存在一个混合策略纳什均衡。甲随机选择自己的策略，使得乙在t=k时选择“退却”策略和乙在t=k+1时选择“退却”策略得到的收益相等。乙随机选择自己的策略，使得甲在t=k时选择“退却”策略和甲在t=k+1时选择“退却”策略得到的收益相等。,消耗战博弈的均衡,例1：甲乙二人在独木桥上对峙，周围有无数围观群众。甲乙二人谁在消耗战中坚持到最后、赢得胜利，谁就被赋予“英雄”称号。这等价于很大，那么甲乙二人都会努力坚持，不轻言放弃。反之，如果甲乙二人在独木桥上相遇，两人都没什么急事，谁先通过独木桥对二人来说没什么太大区别。这等价于很小，那么不管是甲还是乙都很有可能选择“退却”。例2：在奖金很高或荣誉很高的比赛中，比赛双方在竞争中都不会轻易认输。而在奖金较低或影响较小的比赛中，比赛双方都比较容易松解，暗自放弃比赛。,消耗战博弈实例,“先发优势”在人们日常的经济生活中普遍存在。“抓钱博弈（