重复博弈

重复博弈1中科院博弈论课程-乔晗重复博弈•囚徒困境：合作对双方都有利，个体理性决定了不合作的结果•现实社会：存在大量合作人类文明是合作的结果社会进步通过合作取得•社会合作程度越高，就越发达，人们生活福利越好•如何走出囚徒困境，把不合作转变为合作？2中科院博弈论课程-乔晗3重复博弈•重复博弈是一种完全信息动态博弈，其中一个同样结构的博弈至少重复两次，并且先前的博弈结果可以被观测到.中科院博弈论课程-乔晗重复博弈•一次性囚徒困境：只考虑眼前利益•重复博弈：合作可能是最好的选择•重复博弈使理性人走出囚徒困境•非合作博弈得出合作的结果：博弈论的伟大成就4•重复博弈(repeatedgame)：同样结构的博弈重复多次，其中的每次博弈被称为“阶段博弈”(stagegame).中科院博弈论课程-乔晗重复博弈的三个特征1.阶段博弈之间没有物理上的联系，即前一阶段博弈的结果不改变后一阶段的结构（比如剪刀、石头、布的重复）；2.所有参与人观察到博弈过去的历史；3.参与人的总支付（报酬）是所有阶段博弈支付的贴现值之和（局中人关心的不仅是现阶段收益，还包括未来收益，因而有积极性做出不同于一次性博弈的最优选择）。5中科院博弈论课程-乔晗重复博弈分类•有限次重复博弈：博弈在某一特定的时刻（或次数）后结束•无限次重复博弈：博弈一直会进行下去，没有结束博弈有可能结束，但局中人不知道什么时候结束6中科院博弈论课程-乔晗重复博弈的策略空间•重复博弈之所以会导致合作，是因为改变了局中人的策略空间•一次性博弈：合作，不合作•两阶段博弈：{合作，合作}{合作，不合作}{不合作，合作}{不合作，不合作}•三阶段博弈？•N阶段博弈？7中科院博弈论课程-乔晗•单阶段博弈：局中人的选择无法建立在对手前阶段行动的基础上•重复博弈：过去的行动历史可以被观察到，局中人的选择可以建立在其他局中人过去行动的基础上如：过去你欺骗我，这次我不与你合作过去合作愉快，这次还选择合作•过去的行动历史多样，每个人的策略空间扩大，使得合作成为可能8重复博弈的策略空间中科院博弈论课程-乔晗囚徒困境博弈重复多次，策略举例：•All-D:不论过去什么发生，总是选择不合作；•All-C:不论过去什么发生，总是选择合作；•合作-不合作交替进行；（合作程度）•tit-for-tat：从合作开始，之后每次选择对方前一阶段的行动；（针锋相对）•triggerstrategies:从合作开始，一直到有一方不合作，然后永远选择不合作。（触发）……9重复博弈的策略空间局中人2合作不合作局中人1合作3,3-1,4不合作4，-10，0中科院博弈论课程-乔晗重复博弈的策略空间•重复博弈中，局中人可以选择的策略空间变大•新策略的出现使得局中人可以对对方过去的行动进行报复或报答，从而使得合作成为可能•双方都选“总是不合作”，合作不会出现•双方都选“总是合作”，合作会出现吗？10中科院博弈论课程-乔晗•双方“总是合作”不是Nash均衡：给定一方选择“总是合作”，另一方的最优选择是“总是不合作”•怎样的策略既满足个体理性，又能导致合作出现？11重复博弈的策略空间局中人2合作不合作局中人1合作3,3-1,4不合作4，-10，0中科院博弈论课程-乔晗两种策略•理论和实践证明，有两种策略是人们最普遍使用，也最有可能导致合作行为产生。•针锋相对（tit-for-tat）策略：每一次行动都建立在对手前一次行动的基础上，比如：开始合作，如果你今天不合作，我明天就不与你合作，如果你明天又选择合作，我后天就与你合作以牙还牙，以眼还眼•触发（triggerstrategy）策略:一开始我跟你合作，如果你与我合作，我就会一直合作下去，但只要有一次你不合作，我就永远不合作冷酷策略，即使对方不小心犯错误，也会导致合作破裂12中科院博弈论课程-乔晗合作的价值与耐心•贴现率：明天的1元钱今天值多少？0δ=1(1)未来支付的价值(2)博弈继续的概率(3)两者的结合：明天的1元钱等于今天的a元钱明天得到1元钱的可能性为b则δ=ab•一般化解释：未来收益的重要程度中科院博弈论课程-乔晗13•贴现率δ：可以笼统的理解为“耐心”•未来收益的重要性：与人的年龄、健康、婚姻家庭、宗教信仰等因素有关•59岁现象:滥用职权是因为更加重视眼前利益导致•婚姻美满、家庭幸福的人更重视未来收益•相信“来世回报”的人更重视未来利益•宗教：有利于促进社会成员合作中科院博弈论课程-乔晗14合作的价值与耐心无名氏定理（folktheorem）•在无限期重复博弈中，如果每个局中人都对未来足够重视，即δ足够大，那么任何程度的合作都可以作为一个精炼Nash均衡结果出现。•合作程度：整个博弈中合作出现的频率100%合作：每一次都合作0%合作：每一次都不合作中科院博弈论课程-乔晗1516两阶段重复博弈•两阶段的囚徒困境两个局中人进行静态博弈两次第一次博弈的结果在第二次博弈开始前可以被观测到整个博弈的支付是局中人在两个阶段支付之和，即贴现率为1.局中人2L2R2局中人1L11,15,0R10,54,4中科院博弈论课程-乔晗17两阶段囚徒困境的博弈树1L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R21+11+11+51+01+01+51+41+411115+10+15+50+05+00+55+40+40+15+10+55+00+05+50+45+44+14+14+54+04+04+54+44+4中科院博弈论课程-乔晗18两阶段囚徒困境的博弈树1L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2115005441111(1,1)(5,0)(0,5)(4,4)115005441150054411500544中科院博弈论课程-乔晗19两阶段囚徒困境的博弈树1L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2115005441111(2,2)(6,1)(1,6)(5,5)115005441150054411500544中科院博弈论课程-乔晗20两阶段的囚徒困境局中人2L2R2局中人1L11,15,0R10,54,4中科院博弈论课程-乔晗第二阶段的支付(1,1)加到第一阶段的博弈中：局中人2L2R2局中人1L12,26,1R11,65,521两阶段的囚徒困境•子博弈精炼纳什均衡(L1L1L1L1L1,L2L2L2L2L2)局中人1在阶段一选择L1，无论阶段1结果如何，在阶段2选择L1.局中人2在阶段一选择L2，无论阶段1结果如何，在阶段2选择L2.局中人2L2R2局中人1L12,26,1R11,65,5中科院博弈论课程-乔晗22两阶段囚徒困境的博弈树1L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2L1R12L2R22L2R2115005441111(2,2)(6,1)(1,6)(5,5)115005441150054411500544中科院博弈论课程-乔晗23有限次重复博弈•若阶段博弈有唯一的纳什均衡，则有限次重复博弈有唯一的子博弈精炼纳什均衡.Nash均衡在博弈的每个阶段都会出现.•有限次重复不会改变囚徒困境的结果中科院博弈论课程-乔晗24阶段博弈的Nash均衡不唯一时会发生什么？两个局中人把以下静态博弈重复两次在第二次博弈开始前可以观测到第一次博弈的结果整个博弈的支付是两个阶段博弈支付之和，即贴现率为1问题：能否找到一个包含策略M1和M2的子博弈精炼纳什均衡？或者是问：两个局中人能否在子博弈精炼纳什均衡中出现合作？局中人2L2M2R2局中人1L11,15,00,0M10,54,40,0R10,00,03,3中科院博弈论课程-乔晗25博弈树（部分）1L1R122L2R2M2L2R2M2L2R2M22L1R122L2R2M2L2R2M2L2R2M22M1(1,1)(5,0)(0,5)(4,4)(0,0)M1(0,0)(0,0)(0,0)(3,3)1(1,1)(5,0)(0,5)(0,0)(0,0)(0,0)(0,0)(3,3)(4,4)中科院博弈论课程-乔晗26非标准博弈树和逆向回归法1L1R122L2R2M2L2R2M2L2R2M22L1R122L2R2M2L2R2M2L2R2M22M1(1,1)(5,0)(0,5)(4,4)(0,0)M1(0,0)(0,0)(0,0)(3,3)1(1,1)(5,0)(0,5)(0,0)(0,0)(0,0)(0,0)(3,3)(4,4)(1,1)(1,1)(1,1)(3,3)(1,1)(1,1)(1,1)(1,1)(1,1)+中科院博弈论课程-乔晗27两阶段重复博弈局中人2L2M2R2局中人1L12,26,11,1M11,67,71,1R11,11,14,4•子博弈精炼纳什均衡:在阶段1，局中人选择M1,局中人2选择M2.在阶段2,当第一阶段结果为(M1,M2)时，局中人1选择R1，或当第一阶段结果非(M1,M2)时，选择L1当第一阶段结果为(M1,M2)时，局中人1选择R2，或当第一阶段结果非(M1,M2)时，选择L2第二阶段的支付加到第一阶段博弈中.中科院博弈论课程-乔晗奖惩与合作•局中人的奖惩能力体现在第二次博弈时，局中人可以在两个报酬不等的NE中选择•如果对方在第一次博弈中合作，就在第二次博弈时选择报酬高的NE回报对方；•如果对方在第一次博弈中不合作，就在第二次博弈时选择报酬低的NE惩罚对方。中科院博弈论课程-乔晗28•但是，（3，3）帕累托优于（1，1），会导致重新谈判•最后一个阶段，局中人容易达成协议选择（R1，R2）•逆推到前一阶段，局中人知道最后一个阶段无法实施惩罚，合作也难以实现•惩罚的可信性很重要中科院博弈论课程-乔晗29奖惩与合作局中人2L2M2R2局中人1L11,15,00,0M10,54,40,0R10,00,03,3301,15,00,00,00,00,54,40,00,00,00,00,03,30,00,00,00,00,04,½0,00,00,00,00,0½,4L2M2R2P2Q2L1M1R1P1Q1另一个案例:两阶段重复博弈假设阶段博弈发生两次，第二阶段博弈开始前可以观测到第一阶段的结果.中科院博弈论课程-乔晗311,15,00,00,00,00,54,40,00,00,00,00,03,30,00,00,00,00,04,½0,00,00,00,00,0½,4L2M2R2P2Q2L1M1R1P1Q1另一个案例:两阶段重复博弈4个NE:(L1,L2),(R1,R2),(P1,P2),(Q1,Q2)假设阶段博弈发生两次，第二阶段博弈开始前可以观测到第一阶段的结果.中科院博弈论课程-乔晗32进一步假设局中人预期第二阶段结果如下所示:若第一阶段结果为(M1,M2)则选择(R1,R2)若第一阶段结果为(M1,w)，则选择(P1,P2)其中w≠M2若第一阶段结果为(x,M2),则选择(Q1,Q2)其中x≠M1若第一阶段结果为(y,z),则选择(R1,R2)其中y≠M1,z≠M2那么((M1,M2),(R1,R2))是一个子博弈精炼纳什均衡中科院博弈论课程-乔晗4,45½,43,33,33,34,5½7,74,½4,½4,½3,3½,46,63,33,33,3½,43,37,3½3,33,3½,43,33,33½,7L2M2R2P2Q2L1M1R1P1Q1•如果博弈中，可信的惩罚措施足够多，重复博弈就可能出现一次博弈时不会出现的合作行为，即使博弈重复次数是有限的中科院博弈论课程-乔晗3334无限次重复博弈•一个无限次重复博弈是一个完全信息的动态博弈，其中一个同样结构的博弈，即阶段博弈，被重复无限次，并且前一阶段博弈在下一阶段博弈开始前可以被观测到.•更准确的说，同时行动博弈发