《第三章 传统博弈理论(1重复博弈)》

1

东北财经大学数学与数量经济学院刘德海

ldhai2001@163.com

博弈专题讲座

（EconomicGameTheory)小作业：求守卫睡觉的混合均衡概率？？作业讲解

0，00，S-P，0V，-D偷窃不偷睡觉不睡觉守卫小偷分析：守卫睡觉的均衡概率p*B与小偷被抓体罚P成正比，与看管物品价值V成反比作为数学分析方法，传统博弈对参与者的“理性”要求非常苛刻：目标理性(主观理性):追求自身利益最大化(经济学理性的内涵)过程理性（具有理性能力）：包括两个推理步骤（1）认知理性（cognitive）——具有对相关环境形成正确信念的能力；

具体要求：了解博弈结构和规则、“共同知识”（递推归纳法的基础）、贝叶斯理性等（2）工具理性（instrumental）——具有从既定信念采取相应策略的能力

具体要求：具有计算推理、预见、记忆、分析判断的能力，不会犯错误（颤抖手均衡）等信念采取相应策略最大化目标相关环境认知理性工具理性目标理性课前复习:《第一章博弈论中“理性”概念的内涵》——参考：刘德海.理性概念的内涵及其在博弈论学科体系中的地位.《东北财经大学学报》理论分析实验检验理性主义均衡分析（传统博弈）演化主义均衡分析机制设计理论、信息经济学实验博弈演化博弈非合作博弈合作博弈不完全或不完美信息博弈完全完美信息博弈博弈论的理论体系:实证检验均衡合作信息静态博弈、动态博弈、重复博弈理论建模课前复习:《第一章博弈论的理论框架》5第三章传统博弈理论的简介主要内容：第一节传统博弈理论的研究范式；第二节纳什均衡的定义；第三节纳什均衡的无效率问题：重复博弈和无名氏定理；第四节纳什均衡的无效率问题：相关均衡和信号装置；第五节纳什均衡的多重性问题：静态博弈和焦点均衡；第六节纳什均衡的多重性问题：动态博弈和子博弈完美均衡；第七节不完全不完美信息下的纳什均衡存在性：贝叶斯均衡；

6博弈理论的研究对象：参与者互动过程中冲突与合作问题；分析思路：第三章传统博弈理论的简介

第一节传统博弈理论的研究范式大量情绪、直觉、性格、感觉等非理性的主观心理行为知识的未知状态、不可预测性和多样性等造成不同层次的有限理性实际行为方式的无序化为了对人们的互动行为加以模型化分析，必须进行合理的理论抽象博弈论的“完全理性”概念7第三章传统博弈理论的简介第一节传统博弈理论的研究范式传统博弈理论的研究思路：参与者“完全理性”假设下，通过推理演绎达到均衡化过程→均衡是瞬间实现的。在完全理性假设下，人们行为类似于按照既定程序运行的计算机（即给定博弈的环境和规则，严格按照策略执行）。——既没有冲动、情绪、直觉等非理性的因素，也不会像有限理性那样犯错误。回忆：“完全理性”的内涵信念采取相应策略最大化目标相关环境认知理性工具理性目标理性中国象棋大师许银川PK浪潮天梭服务器

2006年08月15日，浪潮杯”中国象棋人机大战再次展开，两场对决中，均战成平局。

8第三章传统博弈理论的简介第一节传统博弈理论的研究范式传统博弈理论的研究内容：纳什均衡的存在性（Nash，1951）纳什均衡的无效率及其解决途径：

——重复博弈，无名氏定理（Friedman，1971）；

——静态博弈，相关均衡（Aumann，1974）；纳什均衡的多重性及其解决途径：

——静态博弈，焦点均衡（Schelling，1960）；

——动态博弈，子博弈完美均衡（Selten,1965）；在不完全（或不完美）信息下，纳什均衡的存在性；

——贝叶斯纳什均衡（Harsanyi，1967）9第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径纳什均衡（NashEquilibrium，简记NE）的理解：参与者可以直接交换信息并一致同意选择某一策略，虽然口头协议无法强制实施，但是每个参与者单独偏离却不会带来更大收益。双人策略式博弈的纳什均衡：策略组合(x1*，x2*)是一个NE，当且仅当x1*是x2*的最佳应对策略，x2*也是x1*的最佳应对策略，双方都没有动机偏离，该策略组合是自动实施的（self-enforcing）。举例：囚徒困境博弈中，双方都选择坦白策略是一个NE；师生的上课时间。-8，-80，-10-10，0-1，-1坦白P抵赖NP坦白P抵赖NP囚徒A囚徒B10定义：策略式博弈（X1,…,X

n；u1,…,u

n）的一个策略组合(x1*，…，xn*)是纳什均衡，如果下式成立：

u(xi*，x－i*)≥u(xi，x－i*)，所有xi∈Xi都成立如果上式取严格不等号，则为强NE。分析方法：离散的策略空间中，采用划线法。例如囚徒困境中，NE为（P，P）。思考：如果策略空间是连续函数f(x)，如何分析？——求利润函数f(q)最大值：df(q1，q2)/dq1=0，即古诺模型坦白P抵赖NP坦白P抵赖NP囚徒A囚徒B-8，-80，-10-10，0-1，-1第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径2006-3-711第一种实现途径：博弈前的串谋过程：参与者在博弈前直接的沟通，达成一个没有约束力的协议，然后开始单独行动——如果一致同意达到某个结果，那么可以预期这个结果是可以自我实施的（self-enforcing），即NE。举例：参加齐心协力跑比赛问题：现实条件可能不允许参与者事前进行直接沟通，怎么办？(1)物质条件不允许直接沟通（参与者人数众多）；(2)双方进行对话的基本互信不足（朝鲜核问题六方会谈）；(3)博弈规则不允许参与者会面（司马相如和卓文君私奔）。——通过外部力量进行协调。注：通过事前的串谋实现纳什均衡，改变了原博弈的信息集合。第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径2006-3-712第二种实现途径：引入外部实体进行协调回忆：一般均衡理论中市场均衡价格的形成假定市场有一个“瓦尔拉斯”拍卖商假定存在一个虚拟的“纳什调节器”（Nashianregulator），博弈前其向每个参与者提供一个均衡的策略组合。例如：朝鲜核问题中国外交穿梭第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径2006-3-713[资料夹]朝核问题和六方会谈朝鲜指控美国对其国家安全构成最大威胁，美国坚持朝鲜半岛无核化。为解决问题，朝鲜一直要求与美国进行直接对话，并多次提议与美国签订互不侵犯条约，以图获得外交承认；但美国坚持不直接与“流氓国家”接触，要求朝鲜先行放弃核计划，并坚持采取多边对话解决。中国外交穿梭，先2003年4月23日－25日，中、朝、美三方在北京举行了三方会谈，中国作为中间人角色促成朝美双方进行直接沟通；然后8月份进入六方会谈阶段。07年3月，美国首席谈判代表希尔与朝鲜代表团团长金桂冠在日内瓦就朝鲜核计划举行了为期两天的谈判。据美国首席谈判代表希尔称，朝鲜将全面公开其核计划，并在年底前关闭所有核设施。朝一核反应堆施工现场(02年8月7日)2006-3-714第三种实现途径：理性主义——参与者“完全理性”假设下，通过推理演绎达到均衡化的过程根据博弈的完全理性假设，尤其是理性的共同知识假设，每个参与者都能利用全部的信息，并且能够正确理解参与者之间的相互作用，因此做出正确的预期。点评：当博弈规则不允许参与者事先进行沟通，又没有外部力量进行行动协调时，如果参与者理性程度很高，仍可以实现NE均衡（此时等价于“理性预期均衡”）。第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径2006-3-715第四种实现途径：演化主义——参与者“有限理性”假设下，在归纳学习过程中实现均衡化过程参与者仅具有有限的认知能力和计算能力，但是时间的重复过程弥补了理性的不足。（1）长期机制，如生物学基于基因遗传和变异的自然选择过程；（2）中短期机制，如社会中模仿、经验、惯例、试错等学习过程。群体参与者中，每个个体观察对方的行动后，根据各种复制原则进行复制。那些最有效率的策略将被大量复制，并淘汰那些表现不佳的策略，最终达成稳定的分布状态。

点评：当博弈规则不允许参与者事先进行沟通，又没有外部力量进行行动协调时，参与者理性程度又很低，只好在不断的犯错误中摸索尝试。第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径纳什均衡的存在性（Nash，1951）：每一个有限博弈都至少有一个NE，其中包括混合策略纳什均衡。证明：采用不动点定理证明；也可以采用单纯形法的初等证明，参见施锡铨著《博弈论》。布劳威尔不动点定理：对于一个拓扑空间中满足一定条件的连续函数f，存在一个点x0，使得f(x0)=x0。举例：大商场等地方可以看到平面地图（相当于一个映射f），上面标有”您在此处”的红点。这个点x0就是把实际地形映射到地图的连续函数f(x0)的不动点。第三章传统博弈理论的简介第二节纳什均衡的定义和实现途径17第三章传统博弈理论的简介第三节纳什均衡的无效率问题博弈论揭示出新古典经济学基本命题存在的问题：“看不见手原理”（亚当·斯密，1776）：“我们的晚餐不是来自屠夫、酿酒的商人或面包师傅的仁慈之心，而是因为他们对自己的利益特别关注。。。每个人都会尽其所能，运用自己的资本争取最大的利益，。。。但如此一来，他就好象被一只无形的手引领，在不知不觉中对社会改进尽力而为。”

——结论：市场机制下个体理性（自利）达到社会理性。“囚徒困境”PrisonerDilemma（A.W.Tucker，1950）

——结论：个体理性与集体理性的深刻矛盾，在个体理性假设下，可能无法实现资源配置的帕累托状态。18[资料夹]n人的囚徒困境：公地的悲剧过度放牧，草场退化，缺草，西部的羊互相啃食羊毛，牧民无奈只得给羊穿上衣服，但是裸露在外面的羊毛还是被别的羊啃秃了长江源地区的草场正在退化1968年美国生物学教授哈丁（GarrettHardin）在《公地的悲剧》（TheTragedyoftheCommons）中讨论了公共草场的问题：如果草场是公共的，为了增加收入，每个牧民都希望增加自己的牲畜，这将带来过牧的问题，并导致草场退化，最终给所有的放牧人带来悲剧。[资料夹]公地的悲剧：来自格鲁吉亚的例子

“该国大部分地区，每天供电4小时，入夜后村庄一片漆黑，点煤油灯照明。

“交上来的电费只有1/3，人们向查电表的人行贿，后者会把部分贿金交给上司，上司再依样层层上交。人们花在煤油灯上的钱比交的电费还多。由于总统的侄子控制着国家的煤油业，实行改革根本不可能。

“人人都知道老老实实地做事最终将一事无成”

其他资料：独立15年来，格鲁吉亚仍处于四分五裂的状态，腐败现象十分普遍。该国54%的人生活在贫困线以下，20%的人在国外打工。——资料来源：(英)卢茨·克莱维曼著《新大牌局——亚洲腹地大国角力内幕》，新华出版社，2006年20纳什均衡的无效率问题：囚徒困境问题描述：帕累托效率结果为（－1，－1），可是一次性博弈的纳什均衡却陷入了深深的“囚徒困境”中：（－8，－8）合作行为是如何产生的？——20世纪人类未解决的难题思考：在非合作博弈框架内的解决途径？打虎亲兄弟，上阵父子兵

——博弈重复进行的过程中产生合作行为-8，-80，-10-10，0-1，-1坦白P抵赖NP坦白P抵赖NP囚徒A囚徒B第三章传统博弈理论的简介第三节纳什均衡的无效率问题唯一纳什均衡下的有限次重复博弈，能否产生合作行为？

分析思路：参与者具有“共同知识”的预测、分析、推理能力，在博弈开始前能够从最后阶段进行反向归纳，总收益为各阶段收益的累加值。结论：当唯一的纯策略NE，有限次重复博弈无法摆脱“囚徒困境”解决途径？无限次重复博弈PNP-1，-1-8，0

0，-8-5，-5PNPPNP-1，-1-8，0

0，-8-5，-5PNP…G1

GTPNP-T，-T-8T，0

0，-8T-5T，-5TPNP累加，得：无限次重复博弈的分析难点：（1）无限期不存在终点，无法反向归纳；（2）任意正收益，无限次加总后总收益都为无穷大，失去比较意义。解决途径：考虑到时间价值（利率r），人们更为注重近期的收益，引入贴现系数δ＝1/(1＋r)，将未来收益折算到当期，总收益是等比收敛数列加总（有限数）。计算：给定贴现系数δ，每阶段收益都为u时，无限次重复博弈总收益的贴现值为：第三章传统博弈理论的简介第三节纳什均衡的无效率问题23举例：无限次重复囚徒困境博弈冷酷的触发策略(cooltriggerstrategy):双方在第一阶段采取合作策略R，如果前（t－1）都合作，那么继续合作；否则，如果对方背叛，则后续阶段一直采取背叛策略L作为惩罚。策略分析：如果一方一直采取合作策略，那么总收益为：U(合作)=4+4×δ+4×δ+…=4/(1-δ)如果一方背叛，那么路径(L,R),(L,L),(L,L)….总收益：

U(背叛)=5+1×δ+1×δ+…=5+δ/(1-δ)当合作收益大于背叛收益时，求得：δ>0.25结论：贴现因子δ足够大，表示参与者更看重未来长远收益，则采取触发策略可以摆脱囚徒困境。例如：地摊货不可靠思考：冷酷策略缺点？4，40，55，01，1LRLR第三章传统博弈理论的简介第三节纳什均衡的无效率问题参与者A参与者B课外阅读：《TheEvolutionofCooperation》Axelrod和Hamilton(1981)通过重复博弈囚徒困境实验，结果表明：K期触发策略最优，具有：清晰、善意、报复性和宽恕性——RobertAxelrod;WilliamD.Hamilton.TheEvolutionofCooperation,Science,Vol.211,No.4489.(Mar.27,1981),pp.1390-1396.无限次重复博弈的无名氏定理（Folktheorem，Friedman，1971）：在无限次重复博弈G（∞,δ）中，如果δ足够接近于1，那么一定存在一个均衡路径，实现博弈的可实现收益。前提条件：δ足够接近于1，即参与者都比较看重未来长期合作的收益，因此避免了短期行为。可实现收益：阶段博弈各纯策略收益的加权平均，其中权数非负且总合为1（即图中阴影）。即使原博弈具有唯一的纳什均衡时，可以设计可信威胁的触发策略，摆脱囚徒困境（但是没有指出具体的策略）。AB0，04，1

1，43，3AB(3,3)(1,4)(1,1)(4,1)(0,0)可实现收益思考：如果双方的贴现率不相等δ1≠δ2

（1）为啥不相等？（2）出现啥新结果？Whenplayershavedifferentdiscountfactors,possiblyreflectingtheplayers’heterogeneoustimepreferencesordifferentaccesstocapitalmarkets,thefeasiblepayoffsetofarepeatedgameisgenerallylargerthantheconvexhulloftheunderlyingstage-gamepayoffs,becauseunequaldiscountingenablestheplayerstotradepayoffsintertemporallyusingnon-stationarypathsofplay(LehrerandPauzner,1999).ChenandTakahashi(2012)studiesrepeatedgameswithunequaldiscountingandwithmorethantwoplayerstoidentifyasufficientconditionsothatafolktheoremtailoredtotheunequaldiscountingsettingholds.多重均衡下有限次重复博弈阶段博弈：纯策略均衡为(2,4)和(4,2)，帕累托最优(5，5)。两阶段重复博弈的策略设计：开始选R策略，若对方不合作则改为M策略进行惩罚；如果对方合作，则采取L策略进行奖励均衡分析：如果不合作，(6,0)中对方收益增加1；但是在第二阶段的惩罚(2,4)中收益减少2δ。当δ>0.5时，合作。结论：具有多个均衡的有限次重复博弈，可以把低效率的均衡作为背叛行为的惩罚，高效率均衡作为奖励，从而实现合作。思考：为什么有限期囚徒困境无法实现合作？——由于惩罚和奖励策略都是纳什均衡，因此是可信的。囚徒困境无法提供可信的奖惩。5,50,00,60,00,04,26,02,40,0LMRLMR参与者A参与者B第三章传统博弈理论的简介第三节纳什均衡的无效率问题28（1）声誉效应问题提出：Axelrod(1981)实验博弈结果表明，有限期仍可达成合作。解决：Kreps，Milgrom，Roberts&Wilson(1982)引入不完全信息解决了这个悖论，建立了KMRW声誉效应模型。基本思路：参与者的行为类型具有不确定性：很大比例(1-ε)是理性的；很小比例ε是“非理性”的合作，刺激对方采取同样的回应，获得更大的长期利益，弥补当前非理性举动造成的短期损失。（2）互惠模型（3）利他主义行为（选讲）其它实现合作的途径29（4）空间网络上的演化博弈问题提出：市场交易行为并不是随机发生的，而是有着固定的关系。Barabasi和Albert（1999）建立了无标度网络的BA复杂网络模型以来，研究复杂网络上合作行为的演化，成为国际研究热点之一。基本结论：在空间网络上更容易产生合作行为——参考文献：（1）NowakM.A.,MayR.M.,Evolutionarygamesandspatialchaos[J],Nature,1992(359):826-829.（2）OhtsukiH.,C.Hauert,E.LiebermanandM.A.Nowak,Asimplerulefortheevolutionofcooperationongraphsandsocialnetworks[J],Nature,2006(441):502–505.（3）Watts,D.J.,Strogatz,S.H.Collectivedynamicsof‘small-world'networks[J].Nature,1998(393):440-442.（4）刘德海，国家自然科学基金青年项目，《复杂网络下群体性突发事件的演化博弈模型和信息传播机制研究》，编号：70901016（选讲）其它实现合作的途径案例1：信任问题的重复博弈分析问题提出：法律和信誉是维持市场有序运行的两个基本机制。（1）与法律相比,信誉机制维持交易秩序的成本更低；（2）法律的判决和执行依赖于当事人对信誉的重视程度。模型：重复博弈，达到（信任，诚实）5+5×δ+5×δ+…=5/(1-δ)原因及其解决：中国企业不重视信誉的原因在于产权不明晰和政府对经济的任意干预。为了使执法者重视自己的信誉,有必要在司法系统引入竞争机制。——来源文献：张维迎.法律制度的信誉基础.《经济研究》,2002(1):3-13.委托人0,0代理人5,5-5,10不信任信任诚实不诚实案例2：审计公司的声誉激励注重声誉具有促使审计公司履行监督和公证职能的积极作用。在审计评估市场上，通过建立管理人员和审计者之间的两阶段重复博弈模型，考虑到声誉作为唯一的激励因素，本文解释了注重声誉反而导致审计公司虚假报表因为后一阶段的真实汇报，将暴露出