第四章 重复博弈

第四章重复博弈Chapter4RepeatedGames郑道文@2010ZhengDaowen,AllRightsReserved•第一节重复博弈的概念•第二节有限次重复博弈•第三节无限次重复博弈第一节重复博弈的概念一、序贯博弈(Sequentialgames)序贯博弈是指参与人在前一阶段的行动选择决定随后的子博弈结构的动态博弈。从后一个决策结开始的子博弈不同于从前一个决策结开始的子博弈。或者说，同样结构的子博弈只出现一次。二、重复博弈(Repeatedgames)1、定义重复博弈是指同种结构的博弈多次重复进行构成的博弈过程。属于动态博弈阶段博弈(Stagegame)。2、特点：（1）各个阶段博弈相同---博弈的参与人、参与人的可选策略、规则和支付函数。（2）阶段博弈之间没有“物质上”（或实质上）的联系。即前一阶段的博弈不改变后一阶段的博弈。（3）所有参与人都能观察到博弈过程。（4）参与人的总收支是所有阶段博弈收支的贴现值之和。3、影响均衡结果的主要因素（1）博弈重复的次数存在长短期利益的权衡：博弈重复多次，参与人就会为了长远利益而牺牲眼前利益，从而选择不同的战略。由此可以解释合作行为和社会规范。（2）信息的完备性“声誉”(Reputation)的影响：当一个参与人的支付函数（特征）不为其它参与人所知晓时，该参与人可能有积极性建立一个“好”声誉（reputation）以换取长远利益。第二节有限次重复博弈一、有限次重复博弈的概念1、定义给定一个博弈G，重复进行T次，并且在每次重复之前博弈的参与人都能观察到此前博弈的结果，这样的博弈过程称为G的一个“T次重复博弈”，记为G(T)。而G则称为G(T)的原博弈。G(T)中的每次重复称为G(T)的一个阶段。2、特征–子博弈–战略：相机行动规则。在重复博弈的每个阶段上，参与人的一个战略就是该参与人在博弈的每一阶段上针对各种情况制定的一个相机行动计划。–路径：一般动态博弈与重复博弈的区别--重复博弈比较复杂。如果原博弈有n种策略组合，重复两次就有n2条博弈路径，重复T次就有nT条路径。–收支：是各阶段收支的和。有时也计算各阶段博弈的“平均收益”。二、有限次重复博弈—猜硬币两人零和、静态博弈；重复的零和博弈不会创造出任何新的利益；博弈双方根本不存在合作的可能性；所有以零和博弈为原博弈构成的重复博弈中，参与人正确的战略就是在每次重复博弈中都采用一次性博弈的纳什均衡策略。三、有限次重复博弈—囚徒的困境假设：有两个惯犯，每次判刑都不是很重。在刑满释放之后再作案，作案之后再判刑；刑满释放之后又作案，如此反复。他们反复作案之后接受隔离审查过程就是一个重复博弈的过程。坦白不坦白坦白-5，-50，-8不坦白-8，0-1，-1重复两次：逆向归纳法求解乙甲坦白不坦白坦白-10，-10-5，-13不坦白-13，-5-6，-6重复两次的囚徒困境博弈相当于独立进行两回的一次性囚徒困境博弈，其总的收益等于两次独立博弈的收益之和。乙甲四、定理（子博弈完美纳什均衡）假设原博弈G有唯一的纯战略纳什均衡，则对任意正整数T(∞)，（即有限次的）重复博弈G(T)有唯一的子博弈完美纳什均衡解，且它的子博弈完美纳什均衡就是所有参与人在每个阶段博弈中都选择原博弈G的纳什均衡策略。参与人在G(T)中的总收支为参与人在G中收支的T倍；平均每阶段的收支等于原博弈的收支。五、原博弈有两个纳什均衡的重复博弈原博弈有多个纯策略纳什均衡的情况下，重复博弈就可能有多个子博弈完美纳什均衡路径；重复次数越多，这种均衡路径也越多；并且，原博弈的非均衡策略组合在重复博弈中有可能构成子博弈完美纳什均衡的一部分。1、假设：–两厂商1和2同时面临两个市场发展机会A和B。–每个厂商的能力都是有限的，只能选择一个市场来发展，即它们的可选策略为A或B。–收益矩阵如表所示：ABA3，31，4B4，10，0厂商2厂商12、一次性的静态博弈两个纯策略的纳什均衡：(A,B)和(B,A)；一个混合战略纳什均衡：厂商1和2都以相同的概率(0.5)在A和B之间随机选择，双方期望收益为0.25×(3+4+1+0)=2。3、两次重复博弈子博弈完美纳什均衡是无条件重复原博弈的某个纳什均衡或者是几个纳什均衡交替使用。（1）轮流去两个市场①厂商1在第一阶段去A，第二阶段去B；厂商2第一阶段去B，第二阶段去A。均衡路径为第一次博弈(A,B)，第二次(B,A)。每阶段平均收益为(4+1)/2=2.5②厂商1在第一阶段去B，第二阶段去A；厂商2第一阶段去A，第二阶段去B。均衡路径为第一次博弈(B,A)，第二次(A,B)。每阶段平均收益为(4+1)/2=2.5（2）连续两次出现原博弈的同一个纯策略纳什均衡第一次为（A,B），第二次为（A,B）；厂商1和2在各阶段的平均收益为（1，4）。第一次为（B,A），第二次为（B,A）；厂商1和2在各阶段的平均收益为（4，1）。（3）两厂商重复采用混合战略它们都以相同的概率（0.5）随机选择去A市场和B市场，平均期望收益为2。（4）一次采用纯战略纳什均衡，另一次采用混合战略均衡：•第一次是纯策略均衡(A,B)，第二次是混合战略均衡；–平均期望收益为（1.5，3）。•第一次是纯策略均衡(B,A)，第二次是混合战略均衡；–平均期望收益为（3，1.5）。•第一次是混合战略均衡，第二次是纯战略均衡(A,B)；–平均期望收益为（1.5，3）。•第一次是混合战略均衡，第二次是纯战略均衡(B,A)；–平均期望收益为（3，1.5）。4、三次重复–三次重复博弈中，除了有与上述类似的均衡战略组合外，还有以下战略可以构成子博弈完美纳什均衡•厂商1的战略：第一阶段博弈选A；第二阶段的行动选择取决于第一阶段的结果第三阶段无条件选B。•厂商2的战略：第一阶段选A；第二阶段无条件选B;第三阶段的行动选择取决于第一阶段的结果•因此，三阶段重复博弈的子博弈完美纳什均衡路径为：(A,A)→(A,B)→(B,A)(A,A)→A;(A,B)→B;(A,A)→A;(B,A)→B;“触发战略”(Triggerstrategy)：利用后续阶段博弈的制约作用达成均衡的战略。七、民间定理(TheFolktheorem)，又叫无名氏定理：如果原博弈有均衡收益组合优于w，那么在该博弈的多次重复中，任何可行的个体理性收益都可以通过一个子博弈完美纳什均衡的平均收益来实现。(1,1)(4,1)(1,4)(3,3)0厂商1的收益厂商2的收益可行的、个体理性收益区间帕累托前沿第三节无限次重复博弈(InfinitelyRepeatedGame)一、无限次重复博弈及其收益（1）无法直接运用普通的逆向归纳法；（2）参与人在各阶段收益的总和趋向于无穷大。贴现系数δ是后一阶段收益折算成前一阶段收益的比例系数，用公式表示为：假设某参与人在无限次重复博弈的一个均衡路径上各阶段博弈的收益为πt，则该参与人无限次重复博弈的总收益（即各阶段收益的贴现值）为11113221tttPV定义：给定一个博弈G，无限次重复进行G博弈的过程称为G的“无限次重复博弈”，记为G(∞,δ)，其中δ是参与人收益的贴现系数（是所有参与人共同的贴现系数）。并且在进行第t阶段（第t次重复）博弈之前，参与人都能看到(t-1)阶段博弈的结果。各参与人在G(∞,δ)中的收益等于各阶段收益的贴现值。二、无限次重复的囚徒困境1、无限次重复博弈和有限次重复博弈的区别–在有限次重复博弈的各阶段博弈中参与人采用原博弈的纳什均衡策略。–无限次重复博弈中，有可能出现对双方都有利的合作博弈均衡结果。2、囚徒困境的收支矩阵（效用）DCD1,15,0C0,54,4参与人2参与人1D—defect;C—cooperate3、触发战略：（又叫冷酷战略grimstrategies）（1）开始选择抵赖；（2）选择抵赖直到有一方选择坦白，然后永远选择坦白。即在第一阶段选择C；在第t阶段，如果前t-1次的结果都是(C,C)，则继续选择C，否则选择D。上述触发战略是一个子博弈完美纳什均衡。4、子博弈完美纳什均衡参与人2的收益：（1）参与人2不合作（2）参与人2合作15111532U144VVV（3）参与人合作的条件：V≥U411514当时，参与人2对参与人1触发战略的最优反应战略是选C；因博弈的对称性，参与人1对参与人2触发战略的最优反应战略也是选C。触发战略组合是整个无限次重复博弈的一个子博弈完美纳什均衡41三、无限次重复博弈的无名氏定理1、可实现的收支可实现的收益(Feasiblepayoffs)是阶段博弈各种纯策略组合收益的加权平均所构成的收支数组，其中，权数是非负，总和为1。不同的权数结构就可构成不同的可实现收益。(4,4)(5,0)(0,5)(1,1)0参与人1的收益参与人2的收益2、平均收益平均收益是无限次重复博弈中参与人在各阶段博弈收益贴现值的平均数。定义：如果有一个常数π，作为无限次重复博弈每个阶段博弈的收益，其贴现值与另一无限次重复博弈的各阶段收益数列π1，π2，…相同的贴现值相等，则π为π1，π2，…的平均收益。给定贴现系数δ，如果每阶段收益为π，则无限次重复博弈的现值为如果每阶段收益各不相同，分别为π1，π2，…，则无限博弈的贴现值为111ttt111ttt11)1(ttt设G是一个n人参与的完全信息静态博弈（原博弈）；是G的一个纳什均衡战略组合（既可以是纯战略，也可以是混合战略）；e=（e1,…，en）是决定的收益组合；是G的一个任意可实现的收益组合。如果对于任意参与人i都成立，当δ趋近于1时，则无限重复博弈G(∞,δ)中一定存在一个子博弈完美纳什均衡路径，能实现参与人的平均收益3、民间（或无名氏）定理*a*a),,,(21nvvvviiev),,,(21nvvvv(4,4)(5,0)(0,5)(1,1)0参与人1的得益参与人2的得益TheFolkTheoremforInfinitelyRepeatedGamesIftheplayersaresufficientlypatient,thenanyfeasible,individuallyrationalpayoffscanbeenforcedbyanequilibrium.Thus,inthelimitofextremepatience,repeatedplayallowsvirtuallyanypayofftobeanequilibriumoutcome.0(πc,πc)π1πmπ2πm子博弈完美纳什均衡可实现的收益纳什威胁点垄断经营的最大利润双头垄断四、无限次重复的古诺模型（一）假设：（1）市场总产量为Q=q1+q2，其中q1、q2分别表示厂商1和2的产量；（2）市场出清的价格为P=P(Q)=8-Q;（3）厂商无固定成本，边际成本为2；两厂商一次性博弈存在唯一的纳什均衡策略组合（2，2）。–其均衡产量qc=2被称为“古诺产量”。–纳什均衡的总产量4大于垄断产量qm=3如果两厂商个生产垄断产量的一半（qm/2=1.5），双方就可以获得更高的收益。在一次性博弈中，不会出现合作博弈的结果。如果两厂商无限次重复博弈，厂商就有可能采用触发战略，达到子博弈完美纳什均衡。（二）触发战略1从第一阶段开始生产垄断产量的一半；一旦发现对方偏离该产量，自己就生产古诺产量2，直到永远，以此相报复；否则，继续生产1.5的产量。在无限次重复博弈中，双方采用上述触发战略是一条子博弈完美纳什均衡路径:每一阶段上采用策略组合（1.5，1.5）；双方每阶段的收益1.52qm5.42*m触发战略构成子博弈完美纳什均衡的条件：(1)合作博弈的收益贴现值(2)非合作博弈的贴现值厂商2第一阶段不合作的利润q2=2.25,π2=5.062515.4)1(5.42222222)5.4(2)5.18(qqqqq140625.