Chapter3 Repeated Games(博弈论-浙江大学)课件

Chapter3RepeatedGames

Inthischapterweanalyzewhetherthreatsandpromisesaboutfuturebehaviorcaninfluencecurrentbehaviorinrepeatedrelationships.Muchoftheintuitionisgiveninthetwo-periodcase;afewideasrequireaninfinitehorizon.区分：repeatedgamesandsequentialgames张维迎P207—209Sequentialgame的特征：参与人在前一阶段的行动选择决定随后的子博弈的结构，因此，从后一个决策结开始的子博弈不同于从前一个决策结开始的子博弈，或者说，同样结构的子博弈只出现一次。Repeatedgame，顾名思义，就是同样结构的博弈重复多次，其中每一次博弈称为阶段博弈Stagegame（也称为原博弈）。RepeatedGame的基本特征有3项：1、阶段博弈之间没有“物质上”的联系（noPhysicallinks），也就是说，前一阶段博弈不改变后一阶段博弈的结构（对比之下，序惯博弈涉及到物质上的联系）；２、所有参与人都观测到博弈过去的历史；３、参与人的总支付是所有阶段支付的贴现值之和或加权平均值。１：阶段博弈本身可能是一个静态博弈，也可能是一个动态博弈。因此重复博弈可能是不完美信息博弈，也可能是完美信息博弈，尽管博弈论专家谈到重复博弈时一般是指前一种情况。重复次数的重要性来自于参与人在短期利益和长期利益之间的权衡。当博弈只进行一次，参与人只关心一次性的支付；但如果博弈重复多次，参与认可能会为了长远利益而牺牲眼前利益从而选择不同的均衡策略。这是重复博弈分析给出的一个强有力的结果，它为现实中观测到的许多合作行为和社会规范提供了解释。信息不完备的影响将在下一章讨论，这里只讨论重复次数对均衡结果的影响，并假定信息是完备的。一、有限次重复博弈（以two-stagerepeatedgames为例）考虑曾经给出的囚徒困境的标准式（回忆并画出支付矩阵）。假设两个参与者要把这样一个同时行动博弈重复两次，并且在第二次博弈开始之前可观测第一次的结果。再假设整个过程博弈的收益等于两阶段各自收益的简单相加（即不考虑贴现因素），我们称这一重复进行的博弈为两阶段囚徒困境。（一）阶段博弈只有唯一NE回忆第二章第四节的“有同时选择的两阶段动态博弈”。两阶段囚徒困境其实属于这种类型博弈。无非这里的参与人3、4与参与人1、2是相同的，行动空间A3、A4也与A1、A2相同，并且总收益μi(a1,a2,a3,a4)等于第一阶段结果(a1,a2）的收益与第二阶段结果(a3,a4)的收益简单相加。在“有同时选择的两阶段动态博弈”中第二阶段参与人3和4的稳定行动依赖于第一阶段的可行结果(a1,a2)，表示为(a3*(a1,a2),a4*(a1,a2))，而不是简单的(a3*,a4*)(关税博弈中第二阶段企业的均衡产量依赖于政府第一阶段所选择的关税）.而在两阶段囚徒困境中,第二阶段的NE可以完全不依赖于第一阶段的结果。分析时要注意3点：1逆推归纳法backwards-induction2参与人在第二阶段行动只须考虑该阶段的利益最大化，因为无须“瞻前顾后”。3分析第一阶段时，可把第二阶段的均衡结果下的支付值叠加到第一阶段的相应支付值上。有限次“囚徒困境”博弈的NE再一次表明了为什么会爆发价格战。试想两博弈方不是囚徒而是两个大公司，比如可口可乐公司和百事可乐公司、或者是联合利华公司和宝洁公司，如果摆在这些公司面前的是两种拓展市场份额策略的选择：保持原价或降低价格，“囚徒困境”博弈告诉我们这些公司会降低价格并不断重复下去。这个结论是令人沮丧的。但实际情况并非完全如此。那么在什么情况下，它们会合作呢？罗伯特.艾克斯劳德在著作《合作的演进》一书中描述了一个计算机的竞赛：选择14种策略在PropositionIfthestagegameGhasauniqueNashequilibriumthen,foranyfiniteT,therepeatedgameG(T)hasauniquesubgame-perfectoutcome:theNashequilibriumofGisplayedineverystage.注

（二）阶段博弈存在两个以上NE市场开发博弈。P111借此了解重复博弈均衡路径、及其效率比较。*该G重复两次构成一个两阶段的重复博弈，那么可形成多少条路径？如果不考虑混合策略，16条。其中子博弈完美NE路径有哪些？从前述的例子中已知，阶段博弈的NE在每个阶段的重复或交替构成子博弈完美NE。那么不考虑混合策略NE情况下，有4条。这4条均衡路径及其支付是：行动组合支付向量Stage1Stage2总支付平均支付（A，B）（B，A）（A，B）（B，A）（A，B）（B，A）（2，8）（1，4）（5，5）（2.5，2.5）（5，5）（2.5，2.5）（8，2）（4，1）路径的支付采用平均支付与采用总支付相比的优点：平均支付可以与阶段博弈的支付相比较。0甲的平均支付乙的平均支付．．．．1231234（1，1）（4，1）（1，4）（3，3）·（2.5,2.5）·(2.67,2.67)*该博弈如果重复三次构成一个三阶段的重复博弈，由每阶段都重复或交替阶段博弈的纯策略NE，那么子博弈完美NE路径有几条？8条。它们的效率如何？同两阶段重复博弈。除此之外已找不到另外的效率更高的均衡路径。但可找到另外一条效率更高均衡路径。考虑如下面的策略组合：甲：第一阶段开发A市场；第二阶段视第一阶段的结果而定—如果结果是（A，A），则选A，如果是（A，B），则选B；第三阶段无条件选B。乙：第一阶段开发A；第二阶段开发B；第三阶段根据第一阶段的结果而定—如果第一阶段结果是（A，A），则选A，否则选B。1、策略中都包含有条件的选择。2、策略是一个完整的行动方案。问题：该策略组合对应的路径是什么？这就证明了该策略组合是子博弈完美的。从这条均衡路径中看到：将来利益对当前的选择有约束。这种策略有2个特点：1、第一阶段选A，试探合作。机会主义2、后续阶段中包含着奖励和惩罚机制：选A可以奖励对方，选B可以惩罚对方。因为（A，B）和（B，A）都是阶段博弈的NE，所以奖励和惩罚都是可信的。一方的机会主义行为将触发其他参与人策略中的惩罚机制发生。触发策略(Triggerstrategies):我们把这种包含着奖励和惩罚机制的策略称为触发策略。正是由于害怕“触发”其他参与人的惩罚机制，所以不敢利用机会使自己在该阶段利益最大化，从而使该阶段的“合作”出现。从这个意义上看，触发策略是“温柔的”。该阶段博弈如果只有两个阶段，则无法构造触发策略(不存在触发策略)。上面的例子因为阶段博弈的NE很丰富，且存在可供奖励和惩罚的NE，所以双方不仅可构造触发策略，而且触发策略是子博弈完美的（或者说触发策略所包含的奖励和惩罚是可信的）。双方的策略均为：第一阶段选择M；如果第一阶段的行动组合是（M，X）（或（X，M），X为除M之外的其它可选行动），则第二阶段选P(Q)，如果是除此之外的其它任何组合，则选R。第一阶段的行动组合是(M,M),则第二阶段的行动组合将是(R,R);第一阶段的行动组合是(M,X)或(X，M)，则第二阶段的行动组合将是(P,P)或(Q,Q);第一阶段的行动组合为其它，则第二阶段还是(R,R)。参与人2LMRPQ参与人1L4,45.5,43,33,33,3

M4,5.5

7,7

4,0.5

4,0.54,0.5

R3,30.5,46,63,33,3P3,30.5,43,37,3.53,3Q3,30.5,43,33,33.5,7案例：美国Staten岛上的报纸发行市场上有两个主要的竞争对手：《纽约邮报》和《每日新闻》。1994年，《纽约邮报》所属公司RubertMurdoch将邮报的价格从40美分提高到50美分，这时《每日新闻》没有跟着提价。在将《纽约邮报》的价格降回到40美分之后，对方还是没有作出反应，于是RubertMurdoch公司宣布有意向将价格再降到25美分，但对方仍然没有做出响应。接着RubertMurdoch公司果然将邮报在这个岛屿上的发行价格降到25美分。此时，〈每日新闻〉终于明白了〈纽约邮报〉的意图，将价格提高到50每分。不久，RubertMurdoch公司也将价格重新提高至50美分。〈纽约邮报〉的策略是友好的，因为它一开始就提高价格；同时也是挑衅的，在〈每日新闻〉没有跟着提价时，它又将价格降低；这一策略同样具有宽恕性，当〈每日新闻〉将价格提高到50美分后，也重新将价格提高；这一策略也是明了的，〈纽约邮报〉的意图对〈每日新闻〉来说经过了两个回合就变得显而易见。由于“触发策略”的运用，在这场“囚徒困境”式的价格博弈中出现了合作双赢的局面。Murdoch公司的做法和“触发策略”的益处在事后看来更加明显。Murdoch公司的成功是因为它掌握了博弈论的重要原则：你要了解竞争对手，也让竞争对手了解你。因此，如果公司的策略为竞争对手所明白，并且应向竞争对手清楚地表明公司准备合作，但对背叛行为将采取以牙还牙的报复行动，那么公司最终将赢得竞争，而竞争对手通过合作也将大有收获。引入贴现因子δ,若某个参与人在某一路径的各个阶段的支付分别为：π1

、π2

、……，则该参与人在该路径的“总支付”π为

无限序列π1

、π2

、……的现值之和，即：

π=π1+δπ2+δ2π3+……=∑

δt-1πt

t=1∞δ？0≤δ≤1当δ0，行动短视化，时间视野往往局限于本期、近期；当δ1，参与人有远见，他充分意识到他现期的行动决策将通过其他参与人的反应影响到他未来的收益，因而试图跨期协调其行动决策。无限次重复博弈及其支付的定义：DefinitionGivenastagegameG,letG(∞,δ)denotetheinfinitelyrepeatedgameinwhichGisrepeatedforeverandtheplayerssharethediscountfactorδ.Foreacht,theoutcomesofthet-1precedingplaysofthestagegameareobservedbeforethetth

stagebegins.Eachplayer’spayoffintheG(∞,δ)isthepresentvalueoftheplayer’spayoffsfromtheinfinitesequenceofstagegames.现在分析无限次重复囚徒困境博弈。我们将证明尽管阶段博弈中唯一的NE是不合作的(招认，招认)，在有限次重复时，唯一的子博弈完美NE还是在每个阶段都(招认，招认)，可是在无限次重复（在可预见的将来不会结束）进行的情况下，只要参与人有足够的内心(即δ足够接近1)，每个阶段的行动组合为(沉默，沉默)将形成一条子博弈完美NE的路径。考虑参与人的触发策略：在第一阶段选择不坦白，且在之后的任意阶段t，如果之前的（t-1）阶段的结果是双方都不坦白，则继续选择不坦白，否则从t阶段开始永远选择坦白。注意：参与人制订了一个关于未来的无所不包的行动计划，即一次性地选择了函数形式si(·)作为应对策略，而不是一期只作出依次行动选择。序列5，1，1，……的贴现值之和：5+δ·1+δ2·1+δ3·1+……=5+δ/(1–δ)沉默的现值4/(1-δ)招认的现值5+δ/(1–δ)≥δ≥1/4这说明，当且仅当δ≥1/4，给定对方的触发策略并且对方没有首先选择招认，自己也不会首先招认。（二）民间定理(无名氏定理)P125“民间定理”第一段。先明确两个关于支付的概念。平均支付averagepayoff：在无限次重复博弈中，平均支付指为了得到相等的支付现值之和而在每一阶段都应得到的等额支付值。计算：令贴现因子为δ，那么无限支付序列π1

、π2

、……的现值之和V为：V=∑

δt-1πt

∞t=1无限支付序列π、π、……的现值之和V为：V=π+πδ+πδ2+……=π/(1-δ)如果下式成立：∑

δt-1πt∞t=1=π/(1-δ)即：π=(1-δ)∑

δt-1πt∞t=1那么，π就是无限支付序列π1

、π2

、……的平均支付，它是各阶段支付现值之和的(1-δ)倍。可行支付向量feasiblepayoffs:支付数组x=(x1，x2、…、xn)称为可行支付向量，如果它是阶段博弈G的纯策略支付的凸组合(concavecombination)(即xi是阶段博弈中参与人i的纯策略支付的加权平均值，权数非负且和为1)。可行支付向量。以“囚徒困境”为例…一个可行支付向量对应重复博弈的一条路径。0囚徒1的支付值囚徒2的支付值1234512345····(1,1)(4,4)(5,0)(0,5)阴影面积中的任意一个坐标点都是一个可行支付向量。哪些对应着均衡路径？FolkTheorem(Friedman1971)LetGbeafinite,staticgameofcompleteinformation.Let(e1,e2,……,en)denotethepayoffsfromaNashequilibriumofG,andlet(x1，x2、…、xn)denoteanyotherfeasiblepayoffsfromG.Ifxi＞eiforeveryplayeriandifδissufficientlycloseto1,thenthereexistsasubgame-perfectNashequilibriumoftheinfinitelyrepeatedgameG(∞,δ)thatachieves(x1，x2、…、xn)astheaveragepayoff.(P127)例如“囚徒困境”无限次重复博弈中…P128Nash威胁点Nashthreatpoint

(e1,e2,……,en)保留支付reservationpayoff:参与人i的保留支付是指无论其它参与人如何行动，参与人i能够保证得到的最大支付；它意味着即使其它参与人试图给参与人i最大惩罚时，参与人i至少能保证得到的支付。通常以υi表示参与人i的保留支付。

阶段博弈囚徒困境中υi=ei=1；阶段博弈古诺模型中υi=0，而ei=(a-c)2/9，υi≠ei。