重复博弈囚徒困境

1、1.6 重复博弈一、有限重复博弈 定义： 对于完全信息博弈 ，其中 I(1,2,n)为参与者集合， 为所有参与者的策略空间， 为所有参与者的收益函数，如果G在时间上()不断重复，并且在下一次博弈G开始前，所有以前博弈的历史都被观察到，那么它构成的动态博弈就称之为重复博弈，G就为重复博弈中的阶段博弈。如果G重复进行T次，那么G(T)就表示重复进行T次的有限重复博弈。如果G重复进行 次，那么G( )就表示无限重复博弈。 1二、序贯博弈与重复博弈 1、序贯博弈：参与人在前一个阶段的行动选择决定随后的子博弈结构，从后一个决策节开始的博弈不同于从前一个决策节开始的博弈。 2、重复博弈：简单地说，就是同样

2、结构的博弈重复多次，其中的每次博弈称为“阶段博弈”。阶段博弈可以是静态博弈，也可以是动态博弈； 3、重复博弈的三项特征：（1）阶段博弈之间没有“物质上”的联系；序贯博弈涉及到物质上的联系。（2）所有参与人观测到博弈过去的历史；（3）参与人的总支付是所有阶段博弈支付的贴现值之和或加权平均值。24、参与人在某一阶段的博弈选择依赖于其他参与人过去的行动历史，所以，参与人在重复博弈中的战略空间远远大于和复杂于在每一个阶段博弈中的战略空间。这一点意味着，重复博弈可能带来一些“额外的”均衡结果，这些均衡结果在一次性博弈中是从来不会出现的。5、影响重复博弈均衡结果的主要因素是博弈的重复次数。重复次数的重要性

3、来源于参与人在短期利益和长远利益之间的权衡。 32.51 有限次重复博弈：连锁店悖论例1：见下图市场进入博弈，假定同样的市场有20个，其均衡会与单个市场不同吗？ 均衡1：进入者总是选择进入，在位者选择默许； 均衡2：在位者选择斗争，进入者总是选择不进入。40，50-10，00，3000，300 在位者 默许 斗争进入者 进入不进入图1 市场进入博弈4定理1、如果阶段博弈G有惟一的纳什均衡，则对任意有限的T，重复博弈G(T)有惟一的子博弈完美纳什均衡，即G的纳什均衡结果在每一个阶段重复进行。 注意：此定律的一个重要条件是：单阶段博弈存在“唯一”的纳什均衡。例2：重复博弈举例 1、参与人：商人1，

4、 商人2； 2、行动空间：都是诚信、欺骗； 3、博弈次数：两次； 4、支付函数： 见图2所示。4，40，55，01，1 商人1 诚信 欺骗商人2诚信欺骗图2 信用困境（1）5 逆推到第一阶段，将第二阶段的纳什均衡收益代入，则如图3所示。 有限重复博弈纳什 均衡是（欺骗，欺骗） 此题解释了现实中 存在的一类现象 普遍的欺诈行为；没有解释另一类现象广泛的合作。 为了在理论上容纳合作解，博弈论主要从三个方面来加以发展： 一是引入多重均衡； 二是引入无限重复博弈； 三是引入信息不完全。 5，51，66，12，2 商人1 诚信 欺骗商人2诚信欺骗图3 信用困境（2）62.52 无限重复博弈 1、合作解要

5、在有限重复博弈申出现要求阶段博弈G必须存在多重纳什均衡，但在无限重复博弈中这一条件并不是必需的：即使阶段博弈G只存在惟一纳什均衡，无限重复博弈中也可以存在子博弈完美纳什均衡解，其中没有任何一个阶段结果是G的纳什均衡。显然这和定理1 相对立，根本的原因就在于博弈可以进行无限期。如果博弈是无限的，那么长远利益就要好于短期利益。 2、解开连锁店难题的办法之一是引入信息的不完全性，或者博弈重复无限次，或者重复未知的次数。7（一）数学分析假设利率r，则贴现率为：1/（1+r），贴现因子 ，一般的有1/（1+r）= ； 有了贴现因子，我们就能比较无限博弈中的不同收益值。 收益值计算法如下：如果未来的收益系

6、列为： 其收益流现值为：如果每一期的收益都是R，则贴现值为：8例4：仍考察信用困境博弈1、单阶段博弈是：（欺骗，欺骗）2、无限重复博弈中子博弈精练纳什均衡有可能为：每一阶段都是合作：（诚信，诚信）；3、此博弈的可能完美均衡： 触发策略，又叫冷酷战略；4，40，55，01，1 商人1 诚信 欺骗商人2诚信欺骗图6 信用困境（1）9（二）证明冷酷战略战略表述：在第一阶段选择诚信，且如果所有前面t一1阶段的结果都是(诚信，诚信)，则在第t阶段，选择诚信，否则选择欺骗，并永久欺骗下去。 1、先证明此战略是纳什均衡：即如果给定参与者j的策略为触发策略，那么参与者i的最优反应也是触发策略，即触发策略是彼此

7、策略的最优反应。假设 与1足够接近的条件下，我们用计算来证明；10 参与者j在某阶段选择欺骗将会使当期得到5的收益，但却会触发参与者i的永远不合作策略，于是未来每一阶段的收益都将成为1。 收益现值为： 如果采取合作，设V为j在无限博弈中的最优反映的收益现值，则有： a、 故： b、 当且仅当下式成立，选择诚信才是最优的。4，40，55，01，1 商人1 诚信 欺骗商人2诚信欺骗图6 信用困境（1）（1）（2）112、再证明此战略是子博弈精练纳什均衡 无限重复博弈的每一子博弈都等同于原博弈，而触发策略是无限重复信用博弈的纳什均衡，因而它同样是任意一个子博弈的纳什均衡，根据完美均衡的定义可知触发策

8、略是一个子博弈精练纳什均衡。在无限重复信用困境的触发策略纳什均衡中，当博弈进行到t阶段时，存在两个可能的历史过程：(1)所有以前阶段的结果都是(诚信，诚信)的子博弈；(2)至少有一个前面阶段的结果不是(诚信，诚信)的子博弈。如果参与者在整个博弈中采取触发策略，则：(1)参与者在第一类子博弈中的最优策略同样是触发策略，我们已证明它是整个博弈的一个纳什均衡；(2)参与者在第二类子博弈中的最优策略是永远单纯重复阶段博弈的均衡(欺骗，跃骗)，它本身就是阶段博弈G的纳什均衡。这就证明了无限重复信用困境中的冷酷战略纳什均衡是子博弈精练的。 12（三）以牙还牙战略也是此博弈的子博弈精练纳什均衡，可类似以上进

9、行证明。 1、先后悔比后后悔好； （1）0阶段欺骗，1阶段后悔的收益现值 (3) （2）0阶段欺骗，t阶段后悔的收益现值 (4)132、后悔要比永远欺骗好； （3）式大于（1）式：当贴现因子为 1/4时，参与者j选择后悔，以求得重新合作要优于永远欺骗。 3、证明永远诚信比欺骗之后再后悔要优 ，等于证明（2）式大于（3）式；4、结论：当贴现因子 接近1(1/4)，以牙还牙策略组合是重复无限信用博弈的纳什均衡。 14（四）无名氏定理 当贴现因子充分接近1，无限重复信用博弈存在合作解，那么是否所有的无服重复博弈G( )都存在合作解?这就引出了无名氏定理。无名氏定理：令G为一个n人阶段博弈， 为以G为

10、阶段博弈的无限次重复博弈， 是G的一个纳什均衡（纯战略或混合战略）， 是 决定的支付向量， 是一个任意可行的支付向量，V是可行支付向量集合。那么，对于任何满足 的 ，存在一个贴现因子 使得对于所有的 ， 是一个特定的子博弈精练纳什均衡结果。 子博弈精练纳什均衡的多重性是无限次重复博弈的普遍问题。15（五）对无名氏定理的三点说明：1、惩罚点（纳什威胁点）：在上述定理中，阶段博弈的纳什均衡 可能是混合战略均衡也可能是纯战略均衡；由 决定的支付向量 是达到任何精练均衡的结果v的惩罚点。2、可行支付： 称为一个可行支付向量，如果它是阶段博弈G的纯战略支付的凸组合；所有可行支付向量构成可行支付集合V。

11、凸组合：假设 为参与者选择纯策略组合下所有可能收益组合的集合（r为向量），向量 中的任意一个元素 ，且 那么， 就称之为凸组合。 16 例如“信用困境”的所有纯战略收益的凸组合如图7的阴影部分 其纳什威胁点是e=(1,1)。无名氏定理告诉我们，如果 足够接近于1，由过点（1,1）的两条垂直线围成的可行集合上的任意点都可以是一个子博弈精练纳什均衡的结果。3、平均支付：假设贴现因子为 ，无穷收益系列为： ，其贴现值之和为： ； 另假设有无穷收益系列： ，其贴现值之和为： ；要求 成为无穷序列 的平均支付，要求： 因此有：即：平均支付是贴现值之和的标准化（标准化因子是 ）可行收益集合(1,1)(5,

12、0)(4,4)(0,5)企业1收益企业2收益o17例：无限重复库诺特双头垄断下的共谋1、在纳什均衡下，库诺特均衡产量： 库诺特均衡利润：2、在垄断情况下：垄断产量： 垄断利润：3、无穷次重复博弈，考虑冷酷战略： 首先选择生产 ，继续选择生产 ； 直到有一个企业选择生产： ，然后生产： （1）给定企业 j 坚持冷酷战略，证明其为纳什均衡： 企业 i 坚持合作，每期利润为： 如果企业 i 选择短期最优产量： 当期利润为： 但随后的利润流量为：18如果下列条件满足，企业 i 会选择合作均衡： 解得：（2）证明其为子博弈精练纳什均衡； （略）（3）讨论 a、此博弈也有多个精练纳什均衡，“总选择库诺特均

13、衡产量”就是一个精练纳什均衡；若产量选择： 都是冷酷战略精练均衡的一个特定结果。 b、其可行支付集与子博弈 精练均衡可达到的支付集 如图7所示19c、保留支付（最小最大支付）： 是当其他参与人试图给参与人 i 最大惩罚时参与人 i 能保证自己得到的最大支付；d、个人理性支付：指大于保留支付的支付；202.53 参与人不固定时的重复博弈 消费者市场交易就是一个典型的例子。厂商是长期的固定参与人，重复提供产品；而消费者是不固定的，假设一次博弈只有一个厂商，一个消费者，且只买一件产品，支付矩阵如图8。 （1）在一次性博弈中，均衡结果为（不购买，低质量） （2）在重复博弈中均衡结果为（购买，高质量）；条件是 （3）此例说明消费者偏好大商场买东西而不信赖走街窜巷的小商贩的原因