博弈论与信息经济学
第6章 完全且完美信息动态博弈
——重复/超级博弈
-连锁店悖论-无名氏定理
经济学院 丁言强
内容提要
重复博弈与战略空间
有限次重复博弈：连锁店悖论
无限次重复博弈
冷酷战略与针锋相对战略
无名氏定理
阿伯罗定理: 两期战略
序贯博弈与重复博弈
序贯博弈的特征是，参与人在前一个阶段的行动选择决定随后的子博弈的结构，因此，从后一个决策结开始的子博弈不同于从前一个决策结开始的子博弈，或者说，同样结构的子博弈只出现一次。
动态博弈的另一种特殊但是非常重要的类型是所谓的“重复博弈”，就是同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈”。
在每个阶段博弈，参与人可能同时行动，也可能不同时行动，在后一种情况下，每个阶段博弈本身就是一个动态博弈。
重复博弈的3个基本特征
重复博弈可能是不完美信息博弈，也可能是完美信息博弈，但在博弈论中一般指的是前一种情况。
(1)阶段博弈之间没有“物质上”的联系，即前一阶段的博弈不改变后一阶段博弈的结构；
(2)所有参与人都观测到博弈过去的历史；
(3)参与人的总支付是所有阶段博弈支付的贴现值之和或加权平均值。
重复博弈的战略空间
战略是一套完备的相机行动规则，它必须说明在每一种可能的状态下参与人的行动选择，即使参与人并不预期这种状态真的会出现。
因为可以观察到其他参与人过去行动的历史，一个参与人可以使自己在某个阶段博弈的选择依赖于其他参与人过去的行动历史。
所以，参与人在重复博弈中的战略是定义在博弈历史上的每个阶段博弈中的行动选择规则，即从博弈历史到行动空间的映射。
重复博弈的战略空间
参与人在重复博弈中的战略空间远远大于且复杂于在每一个阶段博弈中的战略空间。
比如说，即使囚徒困境博弈只重复5次，每个囚徒的纯战略数量大于20亿个，战略组合的数量更多。
所以，重复博弈可能带来一些“额外的”均衡结果，这些均衡结果在一次博弈中是从来不会出现的。这正是分析重复博弈的意义所在。
??? = 262
2,147,483,648 = 231
5
1073741824 = 230
32768 = 215 = 214 * 2
4
16384 = 214
128 = 27 = 26 * 2
3
64 = 26 = 23 * 23
8 = 23 = 22 * 2
2
4 = 22 = 21 * 21
2 = 21
1
战略组合数
各参与人的战略数
轮次
5轮重复囚徒困境博弈的战略与战略组合
重复博弈均衡的影响因素
影响重复博弈均衡及结果的主要因素是博弈重复的次数和信息的完备性。
重复次数的重要性来自于参与人在短期利益和长远利益之间的权衡。
当博弈只进行一次时，每个参与人只关心一次性的支付；但是，如果博弈重复多次，参与人可能会为了长远利益而牺性眼前利益，从而选择不同的均衡战略。
这是重复博弈分析给出的一个强有力的结果，它为现实中观测到的许多合作行为和社会规范提供了解释。
重复博弈均衡的影响因素
完备信息的重要性在于，当一个参与人的支付函数(特征)不为其他参与人所知时，该参与人可能有积极性建立一个好声誉以换取长远利益。
本节我们只讨论重复次数对均衡及结果的影响，有关信息的完备性的影响，我们将在第4章讨论。
有限次重复博弈：
连锁店悖论
在一次性博弈中，如果进入者先行动，这个博弈的唯一子博弈精炼纳什均衡结果是进入者进入，在位者默许，分别得到40和50的支付。
有限次重复博弈：
连锁店悖论
现在假定同样的市场有20个(可以理解为在位者有20个连锁店)，进入者依次进入每一个市场，博弈就变成了20次重复博弈。
假定进入者先进入第1个市场，在位者应该如何反应呢? 也许，尽管从一个市场上看，在位者的最优选择是默许；但因为现在有20个市场要保护，为了阻止进入者进入其他19个市场，在位者是不是应该选择斗争呢？
逆向归纳法
在这个博弈中，在位者选择斗争的唯一原因是希望斗争能起到一种威慑作用，使进入者不敢再进入下一个市场。但是，在有限次重复博弈中，斗争并不是一个可置信的威胁。
设想前19个市场已被进入，进入者现在要进入第20个市场。因为在最后阶段，选择斗争已没有任何威慑意义，在位者的最优选择是默许，进入者将选择进入。
逆向归纳法
现在考虑第19个市场。因为不论在位者选择什么行动，第20个市场上的均衡结果不受影响(因为进入者知道在第20个市场上在位者将选择默许)，在位者的最优选择仍然是默许。
如此一直倒推回去，得到这个博弈的唯一子博弈精炼均衡是在位者在每一个市场上都选择默许，进入者在每一个市场上都选择进入。这就是所谓的“连锁店悖论”(Selten,1978年)。
在位者总是选择斗争，进入者总是选择不进入是这个博弈的一个纳什均衡，但不是子博弈精炼均衡。
囚徒困境重复博弈
囚徒困境与市场进入阻挠博弈类似，只要博弈重复的次数是有限的，在最后阶段，博弈的唯一纳什均衡是两个囚徒都选择坦白。
逆向归纳法意味着，总是坦白是其唯一的子博弈精炼均衡。
有限次重复博弈
均衡存在性定理-2
定理: 令G是阶段博弈，G(T)是G重复T次的重复博弈(T)。如果G有唯一的纳什均衡，重复博弈G(T)的唯一子博弈精炼纳什均衡结果是阶段博弈G的纳什均衡重复T次(即每个阶段博弈出现的都是一次性博弈的均衡结果)。
也就是说，只要博弈的重复次数是有限的，重复本身并不改变囚徒困境的均衡结果。
最优选择的多样性
与单阶段博弈不同的是，在重复博弈中，总是坦白并不是参与人的占优战略，因为它并不是对于任何给定的对手战略的最优反应；
另外，最优选择的唯一性只在均衡路径上是如此，因为在均衡路径上总是出现坦白，抵赖实际上从来不会出现；
在非均衡路径上，参与人可以选择抵赖， 比如说，如果囚徒j选择“总是坦白”，那么，“坦白直到对方选择抵赖,然后总是抵赖”也是囚徒i的最优选择之一。
阶段博弈有多个纳什均衡-1
阶段博弈纳什均衡的唯一性是一个重要条件。如果纳什均衡不是唯一的，上述定理就不一定成立，也就是会存在不同于阶段博弈的子博弈精炼均衡。
导致这种结果的原因是，当阶段博弈有多个纳什均衡时，参与人可以使用不同的纳什均衡惩罚第一阶段的不合作行为或奖励第一阶段的合作行为，而这一点在阶段博弈只有唯一纳什均衡时是办不到的。
如果这个博弈只进行一次，有三个纳什均衡:(M1, L)，
(U, M2)和混合战略((3/7U，4/7M1)，(3/7L, 4/7M2))，
支付向量分别是:(4，3)，(3, 4)和(12/7，12/7)，
帕累托最优结果(D，R)不能达到。
参与人1
2
2
2
U
D
M1
L
R
M2
L
R
M2
L
R
M2
(0,0) (3,4) (6,0) (4,3) (0,0) (0,0) (0,6) (0,0) (5,5)
静态博弈，有三个纳什均衡:(M1, L)，(U, M2)
和混合战略((3/7U，4/7M1)，(3/7L, 4/7M2))。
参与人2
1
1
1
L
R
M2
U
D
M1
U
D
M1
U
D
M1
(0,0) (3,4) (6,0) (4,3) (0,0) (0,0) (0,6) (0,0) (5,5)
静态博弈，有三个纳什均衡:(L，M1)，(M2，U)
和混合战略((3/7L,4/7M2),(3/7U，4/7M1))。
阶段博弈有多个纳什均衡
但是，如果这个博弈重复两次，下列战略组合是一个子博弈精炼纳什均衡(假定贴现因子7/9): “在第一阶段选择(D，R)；如果第一阶段的结果是(D，R)，在第二阶段选择(M1，L)或(U, M2)，如果第一阶段的结果不是(D，R), 在第二阶段选择混合战略((3/7U，4/7M1)，(3/7L，4/7M2))”。
贴现因子=1/(1+r)，r是贴现率。r越小，越大，参与人越有耐心。
用逆向归纳法证明两阶段
重复博弈的子博弈精炼均衡
根据构造，第二阶段的战略组合是纳什均衡。
在第一阶段博弈，给定参与人2选择R，如果参与人1不选择D而选择U，支付增加1单位；但这个偏离的后果是他在第二阶段的支付由4单位下降为12/7，这样，如果1(4-12/7)(即7/16)，参与人1将没有积极性偏离。同样，如果7/9,参与人2将没有积极性偏离。
因而，第一阶段参与人选择的是纳什均衡。
所以，如果7/9，上述战略组合是子博弈精炼纳什均衡，它不同于阶段博弈的均衡。
无限次重复博弈
解开连锁店难题的办法之一是引入信息的不完全性。在第4章我们将看到，即使博弈重复的次数是有限的，如果信息是不完全的，囚徒困境博弈的均衡结果也可能与一次博弈不同。
这里，我们先证明，当博弈重复无穷多次而不是有限次时，存在着完全不同于一次博弈的子博弈精炼均衡。
考虑囚徒困境博弈。假定博弈重复无穷次。我们证明，如果参与人有足够的耐心，(抵赖，抵赖)是一个子博弈精炼纳什均衡结果。
冷酷战略
“冷酷战略”(grim strategy):(l)引诱：开始选择抵赖；(2)惩罚：选择抵赖直到有一方选择了坦白，然后永远选择坦白。
根据这个战略，一旦一个囚徒在某个阶段博弈中自己选择了坦白，之后他将永远选择坦白。
“冷酷战略”又称为触发战略“(triggering strategy)，因为任何参与人的一次性不合作将触发永远的不合作。
参与人不仅没有改正错误的机会，而且受到惩罚即受损，虽然冷酷，却使双方保持合作。
冷酷战略是一个纳什均衡
我们首先证明冷酷战略是一个纳什均衡。假定囚徒j选择上述冷酷战咯，冷酷战略是不是囚徒i的最优战略呢?因为博弈没有最后阶段，我们不能运用逆向归纳法求解。
令为贴现因子(假定两人的贴现因子相同)。如果i在博弈的某个阶段首先选择了坦白，他在该阶段得到0单位的支付，而不是-1单位的支付，因此他的当期净得是1单位。
但他的机会主义行为触发囚徒j的“永远坦白”的惩罚，因此i随后每个阶段的支付都是-8。
冷酷战略是一个纳什均衡
如果下列条件满足，给定j没有选择坦白，i将不会选择坦白:
0+(-8)+2(-8)+… -1+(-1)+2(-1)+…
-8/(1-) -1/(1-)
1/8
如果1/8，给定j坚持冷酷战略，并且没有首先坦白，i不会选择首先坦白。
现在假定j首先选择了坦白，那么i是否有积极性坚持冷酷战略以惩罚j的不合作行为呢?
冷酷战略是一个纳什均衡
给定j坚持冷酷战略，j一旦坦白将永远坦白；
如果i坚持冷酷战略，j一旦坦白，i将永远坦白，他随后每阶段的支付是-8；但如果他选择任何其他战略，他在任何单阶段的支付不会大于-8(如果选择坦白，他达到-8；如果选择抵赖，他达到-10)。所以，
不论为多少，i有积极性坚持冷酷战略。
类似地，给定j坚持冷酷战略，即使i自己首先选择了坦白，坚持冷酷战略(惩罚自己)也是最优的。所以，冷酷战略是一个纳什均衡。
冷酷战略是子博弈精炼均衡
现在证明这个纳什均衡是子博弈精炼均衡，即在每一个子博弈上构成纳什均衡。
因为博弈重复无限次，从任何一个阶段开始的子博弈与这个博弈的结构相同。在冷酷战略纳什均衡下，子博弈可以分为两类: 在类型A，没有任何参与人曾经坦白；在类型B，至少有一个参与人曾经坦白。
我们已经证明，冷酷战略在A类型子博弈中构成纳什均衡。在B类型子博弈中，根据冷酷战略，参与人只是重复单阶段博弈的纳什均衡，它当然也是整个子博弈的纳什均衡。
冷酷战略是子博弈精炼均衡
由此我们证明，如果1/8，即参与人有足够的耐心，冷酷战略是无限次囚徒博弈的一个子博弈精炼纳什均衡，帕累托最优(抵赖，抵赖)是每一个阶段的均衡结果，囚徒走出了一次性博弈时的困境。
这一结果的原因是，如果博弈重复无穷次，且每个人有足够的耐心，任何短期机会主义行为的所得都是微不足道的，参与人有积极性为自己建立一个乐于合作的声誉，同时也有积极性惩罚对方的机会主义行为。
子博弈精炼均衡的多重性
当然，囚徒困境博弈还有许多其他子博弈精炼均衡。
特别地，如同在一次性博弈中，在每个阶段博弈，两人都选择坦白也是一个子博弈精炼均衡，并且，是唯一的一个当期行动独立于过去行动历史的均衡。
子博弈精炼均衡的多重性是无限次重复博弈的普遍问题。
针锋相对战略
在冷酷战略下，参与人没有改正错误的机会，所以确实是很冷酷的，但冷酷战略的结果是双方都没有背叛对方的积极性，因而是友善的。
如果一个战略使参与人有积极性改正错误，这个战略就不大可能是一个精炼均衡。
“针锋相对”(tit-for-tat)战略就是这样一个例子。针锋相对战略是: 开始选择抵赖；在t阶段选择对手t-1阶段的选择。
针锋相对战略
如果参与人j坚持针锋相对战略，参与人i没有积极性首先坦白。因为如果他抵赖，他可以连续达到较高的支付-1；而如果他首先坦白，然后再转向针锋相对战略，他的支付交替为0和-10。
但是，针锋相对战略不是精炼均衡，因为，如果参与人j首先坦白，参与人i并没有积极性惩罚他。如果惩罚，他交替得到0和-10；如果原谅，在一次得到-10后，他连续得到-1。
类似地，参与人i也没有积极性惩罚自己。
阶段博弈纳什均衡
一个基本的事实: 如果a*是一个阶段博弈的纳什均衡，那么，“每个参与人i总是选择ai*”一定是一个子博弈精炼纳什均衡。
因为在这个战略下，其他参与人未来的选择独立于参与人i现在的选择，所以，参与人i现在的最优选择是最大化当期的支付。
无名氏定理
无名氏定理(Friedman,James W.,1971): 令G为一个n人阶段博弈，G(,)为以G为阶段博弈的无限次重复博弈，a*是G的一个纳什均衡(纯战略或混合战略)，e=(e1,e2,…,en)是a*决定的支付向量,=(1,2,…,n)是一个任意可行的支付向量，V是可行支付向量集合。
那么，对于任何满足iei的V(i)，存在一个贴现因子*1，使得对于所有的*， =(1,2,…,n)是一个特定的子博弈精炼纳什均衡结果。
无名氏定理
无名氏定理是说，在无限次重复博弈中，如果参与人有足够的耐心，即足够大，那么，任何满足个人理性的可行支付向量都可以通过一个特定的子博弈精炼均衡得到。
在上述定理中，阶段博弈的纳什均衡a*决定的支付向量e=(e1,e2,…,en)是达到任何精炼均衡结果的惩罚点或称为纳什威胁点。在囚徒困境博弈中，a*是(坦白，坦白)， e=(-8,-8)。
正是由于害怕触发阶段博弈纳什均衡，参与人才有积极性保持合作。
可行支付集合V
如果博弈重复无限次，或者每次结束的概率足够小，如果充分接近于l，任何个人理性可行支付向量都可以作为子博弈精炼纳什均衡结果出现。
重复博弈的支付函数：可以用未来支付的贴现值之和，也可以用贴现值的平均值来代表支付函数。
=(1,2,…,n)称为一个可行支付向量，如果它是阶段博弈G的纯战略支付的凸组合，即加权平均值。
所有可行支付向量构成可行支付集合V。
阴影部分是囚徒
困境博弈的可行
支付集合。这里，
四个角点是纯战
略组合下的支付
向量，每两个角
点之间的边线或
对角线由相应混
合战略组合下的
支付向量构成，
所有其他点(内
点)是多于两个
纯战略支付的加
权平均。
子博弈精炼均衡支付集合
在囚徒困境中，纳什威胁点是e=(-8,-8)。无名氏定理告诉我们，如果足够接近于l，由过点(-8,-8)的两条垂线围成的可行支付集合(交叉线填满的部分)上的任何点都可以是一个子博弈精炼纳什均衡结果。
图是库诺特重复博弈的可行支付集合，由两条正坐标轴和直线1+2=M围成，(1c,2c)是纳什威胁点，子博弈精炼均衡可达到的支付集是由过点(1c,2c)的两条垂直线围成的可行集部分(交叉线填满的部分)。
保留支付
在无名氏定理中，其他参与人惩罚一个不合作者的办法是转向阶段博弈纳什均衡a*。
但纳什均衡支付并不一定是博弈中一个参与人会受到的最大惩罚。一个参与人会受到的最大惩罚决定于他的保留支付。
保留支付定义为: i= min(max ui(ai,a-i))
a-i ai
保留支付是当其他参与人试图给参与人i最大惩罚时参与人i能保证自己得到的最大支付，因而又称为参与人i的“最小最大支付”。
保留支付
显然，iei，即参与人i的保留支付不会大于纳什均衡支付，因为否则的话ai*不是参与人i的最优选择(与纳什均衡矛盾)。
在囚徒困境中，通过选择“坦白”，参与人i总可以保证自己得到-8，因而，保留支付等于纳什均衡支付。
在库诺特博弈中，一个企业不能保证自己得到纳什均衡利润(通过生产纳什均衡产量)，它能保证的只是零利润(选择不生产)，因此，保留利润严格小于纳什均衡利润(在伯川博弈中，保留利润等于纳什均衡利润，二者均为0)。
个人理性支付，
个人理性可行支付
大于保留支付的支付称为个人理性支付。这个概念的涵义是，如果要一个参与人在无限次重复博弈中有任何兴趣“合作”的话，他从中得到的支付不应该小于他的保留支付。
定义V=(:ii)为个人理性支付集合，=VV为个人理性可行支付集合(就是说由满足个人理性的可行支付向量组成)。
在图中，是交叉线标出的阴影区域，在图中，是由正坐标轴和直线1+2=M围成的整个阴影区域。
弗登伯格和马司肯定理
因为iei，大于弗里德曼定理中可达到的精炼均衡支付集合。
弗登伯格和马司肯(Fudenberg和Maskin，l986)证明，弗里德曼定理中的e=(e1,e2,…,en)可以用=(1,2,…,n)代替。
就是说，如果足够接近于1，所有的都是一个特定的子博弈精炼纳什均衡结果，即使iei。
简单地说，每一个个人理性可行支付向量都可以在精炼均衡中达到。图的整个阴影区域都是精炼均衡结果。
帕累托合作均衡结果
帕累托合作均衡结果是指参与人能得到的最大支付，处于可行支付集合的上边界。在库诺特博弈中，帕累托合作均衡结果是垄断利润，在囚徒困境中，帕累托合作均衡结果(-1,-1)。
根据无名氏定理，只有当足够接近于1时，帕累托合作均衡结果才会出现。这是因为，如果很小，从下一阶段开始的惩罚不足以阻止参与人在现阶段的机会主义行为。
阿伯罗定理
上述结论成立的前提是，对不合作行为的惩罚以阶段博弈纳什均衡支付为限。
如果有更严厉的惩罚手段，即使不够大，古诺寡头竞争博弈的垄断利润均衡也可能出现。
阿伯罗(Abreu,1986)证明，冷酷战略并不是保证最大合作的战略，最大合作战略是使用最严厉的可信惩罚。
“可信惩罚”是指惩罚战略本身必须是一个子博弈精炼均衡；“最严厉”是指使不合作者得到最低可能的支付。
两期战略
在古诺博弈中，两个企业开始都生产垄断产量的一半qM/2。在t阶段，如果前一阶段(t-1)两个企业都生产qM/2或q，继续生产qM/2；否则，生产q(最大惩罚产量，大于库诺特均衡产量)。
这一战略规定了一个一次性惩罚期和一个潜在的无穷次合作期(故又称为“两期战略”): 在惩罚期，企业生产q；在合作期，企业生产qM/2。
如果任何一个企业在合作期不合作，惩罚期开始；同样，如果任何一个企业在惩罚期不生产惩罚产量，惩罚期重新开始；如果没有任何企业在惩罚期不惩罚，合作期开始。
两期战略
在=1/2时，如果选择3(a-c)/8q(a-c)/2，两期战略可以保证垄断利润均衡作为子博弈精炼均衡结果出现(最大惩罚产量q严格大于库诺特产量qic=(a-c)/3)。对比之下，如果企业使用冷酷战略，=1/2不能产生垄断利润均衡结果。
如果参与人选择q=(a-c)/2，在惩罚期，每个企业的利润都是0，这是这个博弈中可能达到的最严厉的惩罚，如果惩罚真的发生，它是一把两刃刀，不仅不合作者受到惩罚，而且合作者也受到惩罚。
胡萝卜加大棒
但因为参与人的行为是可观测的，在均衡路径，没有参与人会偏离合作，惩罚实际上不能发生。
严厉的目的是阻止不合作行为的发生而不是惩罚本身，尽管惩罚威胁必须是可信的。
多重均衡的困境
子博弈精炼纳什均衡概念可以剔除那些建立在不可置信威胁之上的纳什均衡，从而找出更为合理的均衡结果。
无名氏定理告诉我们，无限次重复博弈可能有无穷多个精炼均衡结果。因此，精炼均衡的概念并不能帮助我们走出多重均衡的困境。
多重均衡的困境
当然，在现实中，参与人也许使用特定的协调机制来达到一个“聚点均衡”。
博弈论文献中通常使用的协调机制一般是假定在对称博弈中聚点均衡是对称的和帕累托最优的，如在库诺特博弈中，生产垄断产量可能是一个聚点均衡，它是帕累托最优的，在成本函数相同时，也是对称的。
