2、无限次重复博弈
?本授课单元教学手段与方法:
基于网络资源的启发式教学:课前根据所要讲授的课程内容,事先提出所要讨论问题,引导学生先行思考,并充分利用网络资源,对相关概念和知识从网上搜索解答;课堂中引出对不全相同的解释,请同学们分析判断区别和联系,教师引导学生找出一致性。令同学们不再以书本和老师讲的内容为准,而是根据自己对网络资源的对比分析得出的结果为准,培养学生自主学习和自主思维的能力。
本授课单元思考题、讨论题、作业:
1(什么是“连锁店悖论”,
2(如何求解有限次重复博弈的均衡策略,讨论博弈次数分别为3、4次时的重复博弈。 3(如何求解无限次重复博弈的均衡策略,讨论其求解方法与有限次重复博弈求解方法的区别。
本授课单元参考资料(含参考书、文献等,必要时可列出)
1.人大经济论坛http://www.pinggu.org/bbs/index.asp 2.博弈论讲义(人大经济论坛):
http://www.pinggu.org/bbs/dispbbs.asp?boardid=52&replyid=202126&id=33274&page=1&
skin=0&Star=2
有限次重复博弈与民风问题
有限次重复博弈与民风问题
以火车站为圆心,围绕在其附近的店铺不诚信经营司空见惯。早已擅长于打擦边球的经营者,要么短斤缺两,要么以次充好,要么强买强卖,来来往往的行人有时即便花了比较高的价钱也未必获得与付出相称的服务和商品。我认为,这与其说归咎于火车站管理者监管不力,毋宁说是迅速集散的人群中必然会产生的现象。
每次走过火车站,不小心遭遇上述情况,都让我情不自禁想起博弈论中的一类模型——有限次重复博弈模型。博弈论可以用于分析不稳定的寡头市场,不过结合个人的感受,其最大魅力在于精细地刻画了社会中人与人之间的行动轨迹。
如果要问,研究社会群体合作或非合作关系中,不完全信息条件下,人们的行为如何选择,什么工具最强大?我的回答只有三个字,那就是“博弈论”。
在有限次博弈模型中,假设了如果某人在最后一次合作中选择背叛,那么他就会由于“投机”获得额外收益,可是那些老实坚持到最后的参与者就会因此遭受损失。模型的关键就是,他们的合作是有时间界限的,而且可以预期。
散布在火车站周围的买卖都是单次博弈。过往该地的旅游客或在此中转,或短暂逗留后便奔向城市中心,对大多数人而言,如果要消费,难说今生也就仅此一回,下次不晓得是猴年马月,何况赶路又急,哪有时间细看,讨价还价。经验丰富的住宿店、杂货店、餐饮店经营
者也知道,因为旅客如果急需,高价也必须的买,就算制假售假旅客也不可能花巨大成本追讨公道。
不管质量好与坏,一锤子买卖,卖了一次就是一次,卖个次品还有额外收益。于是,所有经营者都才过了道德的卢比孔,选择了单次博弈的“背叛”策略。
只要合作关系被预期一次或者有限次,投机主义者必然在最后关头图穷匕见,“背叛”所有“合作者”。我们也就能理解为什么,摆地摊的所卖的东西的质量总是那么让人不安心的重要原因。
单次博弈模型不仅帮助我深入理解了火车站如此混乱的内在原因,也指引我认识到开放的城市与封闭的村镇,为什么会显现出截然不同的民风这一问题。
城市中以流动人口居多,虽然有大量外来人口涌入城市,但大多只做短暂逗留,不管是本地人与外地人,还是外地人与本地人之间的合作关系都不会维系太久,这样地联系显得松散而不稳定。没有人知道对方会不会背叛自己,在何时背叛自己,于是都趁着对方选择“不合作”之前选择“背叛”。
也许为了避免被“背叛”的危险,刚开始就不愿和任何陌生人接触,持不合作的态度,于是造成了城市人之间的冷漠;
也许为了获得有限次博弈的额外收益,在初期假装合作,然后突然之间选择背叛,并立即终止关系,于是惊心动魄的较量与竞争常在城市的舞台上演。
那么,城市以工商业为主的市场经济环境带来的激烈竞争,以及大量外来人口不稳定的生存环境带来治安上的不稳定因素,则加剧了城市较为紧张的社会关系。
众所周知,以中国为代表的中华文化圈的东亚人,注重家庭,讲究内外有别,对内关会备至,对外却是“各家自扫门前雪,休管他人瓦上霜”。所以,不必奇怪,日本人可以对自己的同胞彬彬有礼,也可以对并非同宗同族的中国人亮出屠刀,撕下文明的面纱。
在封闭的城镇、不发的乡村,民风之所以淳朴,根本原因在于其社会结构建立以家庭为单位的简单经济体之上,如农业、手工业、个体工商业。简单经济体自给自足,互帮互助,不相互压榨,这无疑密切了人与人之间的联系。没有太多外来人口,以致于“一家人昨晚吵架,第二天一早全城皆知”,每个人的人际圈既扩展到全城有仅限于全城。这就给每个交往组合的人们之间相互间提供了一个预期——我们相互认识,知根知底,每个人为了长远的利益必须永久合作下去,而任何一个背叛群体利益的人将被这个集体摒弃。
这样没有敢为眼前的额外收益,铤而走险选择背叛,而在之后的长期关系中被其他人抛弃。他们必须在自己所在的范围内和其他人保持良好的合作关系,并永久持续下去。没有人敢投机取巧,每个人在做选择的时候都考虑到别人在远期的反馈行动,那么所有人都经自觉的保持与其他人的合作关系。
淳朴的民风,形成了。武汉、南昌和赣州不就是很好的例子么?
最后,从原因中,我们也到了一些重要的启示——如何避免有限次博弈中的“背叛”?
一、 愿意合作者要发出持续合作下去的预期。比如第一次去某家店购物,要设法透露还会购买的可能,卖家从长远考虑就会重视并提供更优质产品服务。
二、 背叛者应该受到有效地威胁和惩罚。比如,政府给诚信商家颁发锦旗或打上特别标志,引导消费者购买诚信商家商品,而使不守法的商家遭受损失。
有限次重复博弈_手机互动百科
概述
有限次重复博弈是指相同结构的博弈有限次重复进行。在有限次重复博弈中,参与者会欺骗和违约,但当参与者不知道哪一次是末期时,决策近于无限次博弈。
如果是有限期的重复博弈,情况就有所不同了。用逆推法来分析博弈过程,可以表明,参与者若明确合作到了最后一期,以后不会再有重复博弈,那么,最后一期的博弈和一次性的博弈就没有区别,参与者的欺骗和违约行为是不可能被报复的,于是最后一期单个参与者的占优策略就是不合作的欺骗或违约。逆推到前一期,每个参与者都推知以后将不合作,所以也不会合作。如此等等,在有限次重复博弈中,囚犯困境博弈的纳什均衡是参与者的不合作。
举例
例:一个男孩被视为傻瓜,因为每当别人拿一枚1角硬币和5分硬币让他选的时候,他总是选5分的,有一个人觉得奇怪,就问他:“为什么你不拿1角钱的?”,男孩小声回答:“假若我拿了1角钱的硬币,下次他们就不会拿钱让我选了。”
有限次重复博弈与无限次重复博弈的区别 无限次重复博弈没有结束重复的确定时间。在有限次重复博弈中,存在最后一次重复正是破坏重复博弈中局中人利益和行为的相互制约关系,使重复博弈无法实现更高效率均衡的关键问题。
无限次重复博弈不能忽视不同时间得益的价值差异和贴现问题,必须考虑后一期得益的贴现系数,对局中人和博弈均衡的分析必须以平均得益或总得益的现值为根据。 [1]
无限次重复博弈与有限次重复博弈的共同点:试图“合作”和惩罚“不合作”是实现理想均衡的关键,是构造高效率均衡战略的核心构件。
相关条目 无限次重复博弈
点击加载更多
加载中...
贝满创建, 路在前方、贝满等参与编辑。
互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。如需转载,请注明来源于www.baike.com。
有限次重复囚徒博弈中的合作机制研究
有限次重复囚徒博弈中的合作机制研究
1 1,2 1,,杨 城吕峻闽缪春池
( 1( ,611130; 2( ,西南财经大学 经济信息工程学院成都 西南财经大学 天府学院成都
610051)
: ,“”,摘 要模仿现实中人们的决策方式提出类触发策略的策略思想将原问题由双策略的多阶段博弈转换为
,; ,,多策略的一次性博弈并建立起扩展的支付矩阵然后运用进化博弈理论将随机扰动引入复制子动态从理论
; 上说明有限次重复囚徒博弈之所以能够涌现合作是复制效应和变异效应共同作用的结果最后通过建立多主体
,。系统的仿真模型进一步分析和验证了合作涌现的门限条件和稳定状态
: ; ; ; “”; 关键词有限次重复囚徒博弈进化博弈演化稳定策略类触发策略随机扰动 中图
: F224( 32 : A : 1001-3695( 2012) 04-1322-04 分类号文献标志码文章编号
do: 10( 3969 / ssn( 10013695( 2012( 04( 033 ij( i-
Cooperation mechanism in finite iterated prisoner’s dilemma: revisit
based on real-life decision making simulation
1 1,2 1YANG Cheng,LV Jun-min,MIAO Chun-chi
( 1, School of Economic Information Engineering,Southwestern University of Finance , Economics,Chengdu 611130,China; 2, Tianfu Col-
lege,Southwestern University of Finance , Economics,Chengdu 610051,China)
Abstract: This article proposed a new decision-making process based quasi trigger strategy approach to convert FIPD study
from the dual-strategy multistage game into multi-strategy one-short game,and then established an extension payoff matrix and
adopted the repcator dynamcs equaton wth stochastc dsturbance to expan theoretcay that the emergence of cooperaton liiiiiiliilli
in FIPD was a common result of imitation effects and mutation effects( This paper developed a multi-agent system simulation
model in the end to further discuss the threshold of cooperation emergence in FIPD and its stabilization(
Key wods: fnte terated prsoners demma ( FIPD) ; evoutonary game; evoutonary stabe strategy( ESS) ; quas trgriiii’illililii-
ger strategy( QTS) ; stochastc dsturbance ii
,,FIPD ,的直觉经验严重不符而且相关的实证研究也显示中包经典的囚徒困境是一个非零和的两人对称博弈即博弈双T ,。,M M 。与之类 含合作的现象非常普遍尤其在重复博弈的早期阶段方的支付矩阵互为转置可分别表示为 和 ,1,a b 、。似的悖论问题还有惊讶测试蜈蚣博弈和连锁店悖论等 M = ( 1), , c d ,目前已经有大量的文献对上述悖论的成因进行探讨除了传统,2,: ( defect,D) ,其中第一行对应背叛策略的收益第二行对应合 ,、研究者主要从期望效用预期心理以及逆向 的实证分析外( cooperate,C) ,b , d , a , c,2d , b + ,3 , 5,作策略的收益并且满足 。、归纳法的有效性等方面进行分析一种公认的直观的解 c。 ( D,D) ,这类博弈具有唯一的纳什均衡解即双方都选择背: ,释是在重复博弈中参与人会在短期利益和长期利益之间权 , 。叛但它显然不是帕累托效率意义上的最佳策略组合 ,,衡即参与人可能会为了长远利益而牺牲眼前利益从而选择 ( IPD) ,, 对于重复囚徒博弈问题当重复次数趋于无限时。不同于一次性博弈的均衡策略但这样的解释显然过于简单 ( trigger strategies,TS) ( C,触发策略即开始一直选择 任何博弈 ,,和模糊既没有说明产生合作的内在原因和动态过程也没有 D D) 方的一次不合作 都将触发后续永远的不合作 是它的一 ,,对产生合作的条件即何时可能出现合作以及合作的稳定性 ,。个子博弈精练纳什均衡并且是帕累托最优的而当重复次数 。,FIPD 和持续性等深层问题进行阐述因此本文试图深入到 ,( endgame effect,-有限时基于最后阶段博弈效应即随着最后 ,。达到均衡的动态过程中对上述问题作进一步的探讨 ,,阶段的临近博弈双方进一步合作的潜在利益愈来愈小停止 ,合作的可能性会越来越大故将合作持续到最后一刻是不理性 1 FIPD 的扩展支付矩阵 ) ,( D,D) ,的最后一个子博弈的纳什均衡策略依旧是因此根 ,( all defect,AllD) 据逆向归纳法推导总是背叛应该是唯一的 , 重复博弈本质上是一种称为序贯博弈的特殊的动态博弈。( FIPD) ,子博弈精练均衡也就是说有限次重复囚徒博弈实 ,由若干相同结构的阶段博弈组成参与人的收益是各阶段博弈 ,,际是经典囚徒博弈的简单重复理论上不可能实现合作也不 。1,收益的总和这里假定贴现因子为 即暂时不考虑收益的时 。会改变原博弈的低效率均衡但是该理论分析的结果与人们 G( T) T FIPD 。。间成本下文中用 表示重复 次的 博弈
收稿日期: 2011-09-10; 修回日期: 2011-10-24
: ( 1977-) ,,,,( mr( yangcheng@ 163( com) ; ( 1970-) ,,作者简介杨城男重庆人博士主要研究方向为复杂系统仿真和最优化理论吕峻闽男山
,,,; ( 1972-) ,,,,东 莱芜人副教授博士研究生主要研究方向为计算机应用和电子商务缪春池女四川成都人副教授主要研究方向为计算机应用和
(供 应链管理
4 1323 ??第 期,: 杨 城等有限次重复囚徒博弈中的合作机制研究 ,6, ( T) ,Meps 自下而上反复应用劣策略消去法最后只剩 因为通过对 ,Kr对于上述理论与实际不相符的现象等人认为其
s,0,,AllD 。,,下策略 即 是唯一的均衡策略可见基于经典博弈 中一个重要原因在于实际博弈时信息的不完全性即参与人无
FIPD 。, ,理论的逆向归纳法无法解释 中的合作现象究其原因法确切地知道对手的收益函数因而不确定对手是会选择
———( AllD 是因为逆向归纳法的两个基本假设理性人假设每个人 。策略还是存在一定的合作可能如果他们彼此认为对手
) ( ( tit-for-tat,TFT) ,都是完全理性的和一致性预期每个人对他人行为的预期都 有可能选择针锋相对策略则开始阶段合作是 ,4, ) ,。, 是正确的在现实中很难得到保证存在明显的不足因此。Li ,一种更合理的选择等人进一步指出由于存在最后阶
。本文考虑运用更加贴近现实的进化博弈理论 ,,TFT 。段博弈效应即使在合作状态选手也随时可能背叛当
,进化博弈理论从有限理性的个体出发以群体为研究对 TFT AllD ,对手由 转变为 时自己的最佳策略反应也是立即转
,,象认为现实中的个体并非行为最优者个体的决策是一个向 ADll。变为
,、优势策略渐变的过程是通过相互之间模仿学习和突变等动 ,TS,由此可见现实博弈中参与人的策略更像是一种 但又
。,TS,态过程来实现的在这类模型中驱动系统演化的是达尔文的 不完全是 因为参与人会在某个时点策略性地主动终止合
: ,( QTS) , 自然选择理论高于平均收益值的策略对应更高的适应度能 。,、作于是本文提出一种更实际更具体的类触发策略,7,8,i C,; 。即参与人在博弈刚开始的前 个阶段主动选择 一旦对方选 够继续生存繁衍而低于平均收益值的策略则逐渐消亡 D i D。 ,择 或者重复次数大于 时则在余下的博弈中永远选择 G( T) , 考虑在一大群参与人之间以随机配对的方式进行 i ,,其中称为该策略的合作截止点表示参与人的最大可能合 x,,s,,,u,,siii用 表示使用策略 的人数占总人数的比例表示 。珔作次数 ,i,,u ,的期望收益表示所有策略的平均期望收益则
TQTS : G( T) 实际上是多种常见策略的一个集合中每个参 x,i,= 1 0x,i,1 ( 3) ???T + 1 ,s,i,( i = 0,i = 0 与人的策略空间包含 个纯策略分别表示为 i , 11,…,T) 。s,0,,AllD ,其中表示自始至终选择背叛等价于 策 u,,= ( jd + c + ( T , j , 1) a) x,j,+ ( d + ii?????j = 0 ; s,T,,略表示始终以合作对待合作以永久性的背叛反击任何 T,TS。背叛等价于 相对于重复囚徒博弈中的其他几种常见策 ( T , i) a) x,i,+ ( id + b + ( T , i , 1) a) x,j, ( 4) ?????? j = i + 1 ,TFTGTFT( TFT ,、略如 与 类似但同时以小概率的合作回应背 T珔u = x,i,u,i, ( 5) ??) 、Pavlov( ,) ,QTS 。叛赢则保持输则变换等通常更为有效例 i = 0 ,TFT QTS , 如等策略和 虽然前期都能形成高收益的合作局面: ( 4) s,i,其中式等号右边的三个加项分别表示策略 与合作截 ,QTS 但前者只能被动地反击背叛行为而 却能够基于最后阶 、。 止点更低相等和更高三类策略博弈时的期望收益的加权值,,。TFT 段博弈效应策略性地主动选择背叛从而取得优势等 。,在进化博弈过程中收益越高的策略选择的人数越多这 一点,策略希望通过反击促使对手重新选择合作甚至在对方背叛的 : s,i,x,i,在复制子动态方程中体现为运用策略 的人数比例 ,情况下仍然以小概率尝试合作以避免意外背叛所导致的不合 珔u,i,u 的增长率等于该策略的收益 与总体的平均收益 之 ( GTFT) ,QTS ,作如 但 通常只在最后某个阶段主动背叛此时 ,差即 ,合作的潜在利益已经很小后续的阶段博弈已经很难形成有效 ,,dx i 珔= x,i,( u,i,, u) ( 6)?。T ,的反击空间尤其当 值较小时仅有的一两次占优的阶段博 dt ,QTS 。弈将使得 的优势显得尤为明显 ( 2 ) ( 2 ) ,1 M例如图 显示了式中支付矩阵 对应的基于复 ,QTS ,T + 1 这样基于 的思想原博弈问题就转换为 种策 ( Mape ) l。,制子动态的策略演化过程运用 软件其中三角形 ,略的单次博弈即将双策略的多阶段博弈转换为多策略的一次 ( x,0 ,,x,1 ,) ,为策略单纯形在平面上的投影它的每个点代 。G( T) ( T + 1) × ( T + 1 ) ,性博弈此时对应着一个的扩展支付 。s,0,AllD 表一种策略组合例如顶点 表示所有参与人都使用 M( T) 。( 2) G( 2) ,矩阵 例如式是一个两阶段重复囚徒博弈 的 s,0,s,2,AllD TFT ,策略与 的中点表示使用策略 和 的参与人 ,,a,b,c,d,=,10,50,9,49,,T = 2,M( 2) 展开式其中矩阵 ; ,各占一半小箭头表示该点处对应的策略组合的演化方向实 s,0,、s,1,、s,2,。的三个行向量分别对应策略 的收益值 ( ) 。线表示部分解轨道即部分初始策略组合的演化路径图中
20 60 60 ,,微分方程组的向量场表明无论初始状态如何经过足够长时 , ,,s,0 ,,,间的演化系统都会收敛到单一同态的纯策略 并且其
M( 2) = 19 59 99 ( 2) : 动态演化过程与劣策略反复消去法的推导过程是相似的群体 , ,, ,19 58 98 s,2,s,1,,s,0 ,。中的策略 逐渐过渡到 并最终全部收敛于 但
通过对 M( T) 结构的分析,可以计算任意策略组合( s,i,,s,0,,,的吸收域非常窄小系统在该点 另一方面向量场也显示 s,j,) ,: a) = j,i i 的收益具体分为两种情况如果 表示前 个阶段 ,,处并不稳定很小的扰动就会导致系统远离稳态重新循环演 C,D,两种策略都选择 然后同时在后续博弈中一直选择 收益 。,,化而在现实生活中各种随机扰动总会存在系统常常受到 u,i,= u,j,= id + ( T , i) a; b) i , j,s,i,函数 如果 表示 先。G( T) ,1 来自突变和其他偶然事件的冲击因此图 中 不会稳 s,j,,C,( D,C) ,i 于 选择背叛即前 个阶段都选 然后分别选择s,0,,。定在 处而是呈现不确定的循环波动 ( T , , 1 ) i D,u最 后在余下的个阶段中都选择 收益函数 ,由于标准复制子动态强调的是选择机制只能够在原有策 ,7,,i,= id + b + ( T , i , 1) a,u,j,= id + c + ( T , i , 1) a。 ,略集中进行优胜劣汰式的竞争但不包含任何形式的变异机 ,1 。,制因此它无法体现图 中吸引点处的随机扰动由此本文 2 合作行为分析 ,考虑在标准复制子动态中引入非确定性的随机扰动用更为现 ( stochastic dynamical model) G( T) 实的随机动态模型来研究 中 M( T) ,i + 1 = j ,s,i,考察矩阵 的结构不难发现当 时是 ,9,10,。的策略演化过程 s,j,,。的弱占优策略这正是逆向归纳法能够发挥作用的关键
29 计 算 机 应 用 研 究 第 卷 1324 ??
。,,假定每一轮博弈结束后都会有很小一部分的参与人随机除任何小突变群体的侵入那么该群体达到了进化稳定状态
,,x,0,= 1。地变换其策略每种策略变异个体的数量与使用该策略的参与 假定某时刻系统收敛到完全不合作状态即 由
,p。,: x,0,= 1 , 人比例成正比即系统存在一个常数化的随机扰动率 这种 于存在随机扰动系统下一时刻的策略构成比为
,p,x,,= p / T ( = 1,…,T) ii 。AllD 策略转移往往是系统内外多种因素综合影响的结果既可能是 如果此时所有非 策略的收益
,u,0 ,,s,0,,出于参与者的理性误差或博弈双方彼此的不信任也可能是因 都小于 则系统会继续稳定在 的吸收域内并向
、x,0,= 1 ,; ,AllD ,为个体的新旧更替迁移或突变等原因所导致并且这种影响 的方向演化系统不会涌现合作反之若某个非
0,,,、。,u,是连续的可累积的当原博弈体系引入随机扰动后其直接 策略的收益大于 则该策略的比例会进一步增长从而出
s,i,p?x,i,,( 效应导致当期的策略构成比中 的成分有 移出同 现随机扰动之外的主动合作区别于因随机扰动产生的非主 p( 1 , x,,) / T T i。,?) 。( 8) G( T) :,时有 的成分由其他 种策略移入于是完 动性合作因此将式称为 的合作判别式
整地融入随机扰动因素后的复制子动态微分方程为 max( u,i,) / u,0,, 1 i = 1,…,T ( 8)
x,,1 , i,,dx i : u,0,u,i,( 4 ) 。,其中和 的值可由式计算不难看出合作判别 珔, x,,) ( 7)i= x,i,( u,i,, u) + p(?? T dt M ,T 式的结果不仅与原始支付矩阵 相关更与博弈次数 和扰 ,2 ( 2 ) ( 2 ) M例如图 显示了式中支付矩阵 对应的随机动 T p ,p 。。动率 相关和 的值越大越容易出现合作本文将使得,p = 5% 。态模型的演化过程其中扰动率 对比两张向量场图 * * ( 8) ( T,p) G( T) 。式成立的最小参数组合称为 的合作门限 ,,像可以看出两者演化轨迹的绝大部分是类似的但前者收敛 s,0 ,,于策略单纯形的一个顶点 后者收敛于单纯形的一个内 3 合作涌现仿真 E。,。点 前者的均衡是脆弱的而后者的均衡是演化稳定的考
SWARM ,2 E ,接下来运用一个类似 的软件平台按照复杂适应 察图 中 点处各策略的收益并不相等如果运用标准的复制
( complex adaptive system,CAS) ,,5% 系统的思想建立多主体系统的 子动态系统的策略构成比还要继续调整下去但在引入
,,( ) 仿真模型将大量具有有限理性的参与人设计为适应性主体 的随机扰动后不同期望收益产生的复制效应或模仿效应与
( adaptive agent) ,E ,通过随机配对式的反复博弈来考察系统内策 随机扰动产生的变异效应在 点处正好相互抵消使得各 成
。,。,,略构成比的演化趋势和稳定性这里所谓的适应性主体是指 分策略的比例趋于平稳此时系统均衡于混合策略其中 主
s,1 ,,C D。 ,体策略为 即绝大多数人选择第一次 而第二次 值参与人采用类似生物进化的方式通过不断地相互学习模仿和
,E ,,。得一提的是点处的均衡并非是静止不动的系统仍然会 在 动态调整来适应系统环境的变化以获取更高的收益
E ,、点附件的区域波动它是一种动态的基于时间平均的 均( 7) ,M( T) 仿真模型基于式的分析框架以扩展式 作为博 。衡 ,1 000 QTS agent,10 弈双方的支付矩阵包含 个采用 的 并用 位 10 L ( T × L /2) 。s[1] 二进制串 表示合作截止点的百分比位置在策 s[1] ( ,E略的进化方式上模型没有采用传统的基于三种遗传算子选 0.8 0.8 ) ,( 、择交叉和变异的演化算法而是直接将每一个演化代内包 0.6 1 000 ,agent 含 轮独立博弈在每一轮博弈中所有 以随机配对 0.6 0.4 2-IPD ) 、a- p 的方式展开 博弈总收益最低的比例值为 的那些 0.4 gent 。L ,,的策略编码 进行随机变异生成新策略这样既保证 0.2 0.2 ,, 优势策略的动态增长又体现随机扰动的思想同时有利于系 s[2] 0.2 0.4 0.6 0.8 s[0] 。s[2] 0.2 0.4 0.6 0.8 s[0] 统中策略的多样性 图 引入随机扰动后的复制 2 ,G( T) 本文共设计了两组仿真实验分别用于研究 的合作 其 子动态微分方程组的向量场,图 基于标准复制子动态的 1 三个顶点 中支付矩阵为式(2),其中支付 微分方程组的向量场,,门限和稳定状态后者主要通过系统中主体策略的构成比例以 为吸引 分别代表三个纯策略,E 三个顶点分别 代矩阵为式(2),扰动率 点,p=5%, 是吸引点表三个纯策略,s[0], avg _i 。来反映为了对比分析不同参 及合作截止点的平均值 ( 7 ) 1 2 ,对比图 和 的演化轨迹可以看出式中既包含不断 ,, 数条件下的状态值对平均合作截止点作如下的归一化处理0 ,趋于 的基于复制子动态的有向模仿又包含不随时间和状态 ,agent 将其转换为一个百分比值其大小体现了所有 合作意愿 。,变化的常数突变率如果仅有前者系统会最终收敛到单一同 。持久性的平均强度 s,0,,,; 态的纯策略 但其吸收域很窄小是非颤抖均衡的如果 T,,仅有后者系统会始终在初始态附近波动不会出现真正的演 avg_ = x,,/ T ( 9) iii??i = 0 。; ,,化当两者结合时初期由前者主导系统的演化而后期当各 agent ,AllD ,在第一组实验中初始态所有 均采用 策略通 ,种策略的比例基本稳定后则由两者共同维持策略比例的相对 ,avg_i 过设置不同的参数观察系统在演化过程中 值是否有明 。,,均衡同时由于扰动是随机变异的从任何初始态开始的演 ,。1 显上升的迹象以检验主动性合作是否出现表 显示了四组 ,化都会产生所有的策略从而保证演化过程始终满足遍历性要 G( T) ,不同条件下 合作涌现的门限参数包括理论的计算值和 * * ( ,( 6 ) 求不同于标准复制子动态式只会在初始策略集中进行 。( T,p) ,仿真的实验值对比分析显示门限参数的理论计 ,) 。优胜劣汰式的竞争不会产生新的策略 。算值普遍略高于实验值这是因为在仿真过程中总会出现部 ,G( T) 此外随机扰动的思想还可以用于近似推导 的合作 , 分具有较高合作截止点策略的参与人短期内的多次配对博弈,。门限即合作涌现的最低限度条件根据进化稳定策略的概 。 从而使他们在某个特定时期内获得远高于理论平均值的收益* ,,念在一个因局部突变形成的混合群体中如果突变小群体的 T T,当重复次数 接近门限值 时这一类偶然事件通过复制效 ,; 收益大于原群体的收益那么突变体就能够入侵大群体反之 ,AllD ,s应放大必然提高系统中非 策略的比例从而提前突破 ,。则不能入侵将在演化过程中逐渐消亡如果一个群体能够消 ,0,,。的吸收域合作涌现
4 1325 ??第 期,: 杨 城等有限次重复囚徒博弈中的合作机制研究 G( T) 1 表 不同参数条件下 的合作门限 涌现是期望效用的复制效应和随机扰动的变异效应两者共同 。,最后通过建立多主体系统仿真模型进一步 动态演化的结果* * a b c d p/ % TG( T) 。分析和验证了 中合作涌现的门限条件和稳定状态 10 50 9 49 5 2 /3 ,( 7) 相对于精确的定量分析而言本文式的动态演化方程 10 50 9 49 2 3 /4 ,更侧重于对博弈系统状态量的定性分析即对合作门限和稳定 1 5 0 3 5 20 /23 ,状态的基本性状进行解释和描述而具体计算的结果值仅仅作 1 5 0 3 3 33 /37 。( 7 ) ,p 为一种决策参考因为在现实博弈中式的扰动率 是一 * : T/ 注列中的两个数据依次为实验值 计算值 ,。个相当不稳定的系统参量受多种主客观因素的影响它不仅 agent s,i,,在第二组实验中初始态所有 的策略 按照等概 ,、, 取决于具体的博弈环境如博弈主体支付矩阵和重复次数等,p = 5% 。率随机分布并且系统的随机扰动率固定为 ,p 而且即使是在相同环境下的不同博弈阶段值也可能因为参 2 ,图 中微分方程的向量场显示融入了随机扰动的复制子 。G( T) ,与人主观心态的变化而变化因此有关 的定量分析还 G( T) ,动态使 稳定于策略单纯形的某个内点而仿真结果进一 。有待于今后实证研究提供更有力的支持 ,G( T) 步表明的这种演化稳定态并非表现为系统的策略构成 :参考文献 ,、、比固定不变而是一种循环的不确定的基于时间平均的纳什 ,avg_i 。均衡其波动幅度与平均合作意愿 密切相关 ,1, SMEAD R( The evolution of cooperation in the centipede game with * fi- nite populations,J,( Philosophy of Science,2008,75 ( 2 ) : 3 T T,图 显示当 在门限值 附近时平均合作意愿和策略 157- ,。4 T 构成比相当不稳定演化曲线呈周期性波动图 显示当 远 * 177( Tavg_i ,,大于合作门限值 时曲线平稳演化并且其稳定值较 ,2, NORMANN H T,WALLACE B( The impact of the termination rule on 3 ; ,图 显著增长而几条主策略的百分比曲线虽然还在波动但 cooperation in a prisoner ’s dilemma experiment,EB / 。波动频率和幅度都明显偏小这一结果进一步验证了重复次 OL,( ( 2006 -T ,T ,数 是决定合作涌现的关键因素值越大合作越明显越 12) ( http: / / ssrn( com / abstract = 952953( 。稳定 ,3, HART S( Evolutionary dynamics and backward induction
,J,( Games and Economic Behavior,2002,41( 2) : 227-264(
1 1 ,4, LI Jia-wei,KENDALL G( Finite iterated prisoner’s dilemma ca 0.9 0.9 revisited- belief change and end-game effect,C,/ / Proc of the 0.8 0.8 cBehavioral and Quantitative Game Theory: Conference on Future 0.70.7 Directions( New York: ACM,2010: 48( 0.60.6 a 0.5 0.5 ,5, FALK A,FISCHBACHER U( A theory of reciprocity,J,( Games and 状态量0.40.4 b Economic Behavior,2006,54( 2) : 293-315( 0.3 0.3 d 0.2 0.2 ,6, KREPS D M,MILGROM P,ROBERTS J,et a, Ratona cooperaton lili0.1 0.1 d b 00100 300 500 700 900 100 300 500 700 900 in the finite repeated prisoner’s dilemma,J,( Journal of Economic 演化代数演化代数Theory,1982,27( 2) : 245-252( 图 在合作门限附近的演 图 远离合作门限时的演 3 G(T)4 G(T) 化状态其中原博弈矩阵 其中原博弈矩阵 ,M [a,b,c, (M [a,b, 化状态,7, NEILL D B( An evolutionary resolution to the finitely repeated 表 d]=[10,50,9,49],T=10,p=5%,a c,d]=[10,50,9,49],T=3,p=5%,a 曲线分别表示三种 示avg_i ,b/c/d 表示 曲线分别表示avg_i ,b/c/d prison- er’s dilemma paradox,EB / OL,( ( 2003 ) ( http: / / 主要策略 和 的百分 s[8]、s[9]s[10]三种主要策略 、和 的s[1]s[2]s[3] 比曲线, reports- archive( adm( cs( cmu( edu / anon /2003 / CMU-CS-03-百分比曲线) 155( pdf(
4 结束语 ,8, CHONG S Y,HUMBLE J,KENDALL G,et al, Iterated prisoners di- ’ 状态量
lemma and evolutionary game theory: chapter 2 ,M,/ / The Iterated
Prisoner’s Dilemma: 20 Years On( ,S( l( ,: World Scientific,
2007(
FIPD 针对 博弈中逆向归纳法的结论与实践经验之间存在,9, ELLISON G( Basins of attraction,long-run stochastic stability,
,QTS ,FIPD and the speed of step-by-step evolution ,J,( Review of 较大差异的现象基于 的策略思想本文将 的多阶段
Economic Studies,2000,67( 1) : 17-45( ,M 博弈转换为多策略的一次性博弈建立起扩展的支付矩阵 ,10, YOUNG H P,FOSTER D( Cooperation in the short and in the long ( T) ; ,然后运用进化博弈理论在标准的复制子动态中引入随 run ,G( T) ———机扰动从理论上说明了合作涌现的内在原因合作 ,J,( Games and Economic Behavior,1991,3( 1) : 145-156( 2008 ( 上接第 1262 页)
,4, IEDRICH F,GEHBAUER F,RICKERS U( Optimized resource
alloca- tion for emergency response after earthquake disaster
,J,( Safety Science,2000,35( 1 /3) : 45-57(
,5, ( ,J,( 赵林度城市重大危险源应急物流网络研究东南大学学
: 2007,9( 1) : 27-29(,报哲学社会科学版
,6, ,,( holon 黄运夏吴广谋李骥基于 的应急物流系统控制模型,J,(
,2009( 3) : 42-44(物流科技
,7, ( ,J,( ,2005,2( 4) : 441-许志端物流系统柔性的研究管理学报445(
,8, ,( ,J,( 王建张文杰供应链系统可靠性分析中国安全科学学,报
2003,13( 11) : 7375( -
,9, ,( ,J,( ,吴依伟赵林度应急物流网络弹性 初 探价 值 工 程
4 1325 ??第 期,: 杨 城等有限次重复囚徒博弈中的合作机制研究
( 4) : 1-3(
,10, ALBERT R,JEONG H,BARABSI A L( Error and attack tolerance of compex networks,J,( Nature,2000,406( 6794) : 378382( l-
11, HOLME P,KIM B J,YOON C N,et , Attack vunerabty of compex ,allili- l
networks,J,( Physical Review E,2002,65( 5) : 114( -
,12, ,( ,J,( ,吴俊谭跃进复杂网络抗毁性测度研究系统工程学报
2005,20( 2) : 128-131(
,13, ,( ,J,( 李靖张永安复杂网络理论在物流网络研究中的应用中国 流通
,2011( 5) : 38-41(经济
,14, LATORA V,MARCHIORI M( Vulnerability and protection of infra-
structure networks,J,( Physical Review E,2005,71 ( 1 ) : 015103-
10151034( --
有限次重复博弈与民风问题.doc
有限次重复博弈与民风问题
以火车站为圆心~围绕在其附近的店铺不诚信经营司空见惯。早已擅长于打擦边球的经营者~要么短斤缺两~要么以次充好~要么强买强卖~来来往往的行人有时即便花了比较高的价钱也未必获得与付出相称的服务和商品。我认为~这与其说归咎于火车站管理者监管不力~毋宁说是迅速集散的人群中必然会产生的现象。
每次走过火车站~不小心遭遇上述情况~都让我情不自禁想起博弈论中的一类模型——有限次重复博弈模型。博弈论可以用于分析不稳定的寡头市场~不过结合个人的感受~其最大魅力在于精细地刻画了社会中人与人之间的行动轨迹。
如果要问~研究社会群体合作或非合作关系中~不完全信息条件下~人们的行为如何选择~什么工具最强大,我的回答只有三个字~那就是“博弈论”。
在有限次博弈模型中~假设了如果某人在最后一次合作中选择背叛~那么他就会由于“投机”获得额外收益~可是那些老实坚持到最后的参与者就会因此遭受损失。模型的关键就是~他们的合作是有时间界限的~而且可以预期。
散布在火车站周围的买卖都是单次博弈。过往该地的旅游客或在此中转~或短暂逗留后便奔向城市中心~对大多数人而言~如果要消费~难说今生也就仅此一回~下次不晓得是猴年马月~何况赶路又急~哪有时间细看~讨价还价。经验丰富的住宿店、杂货店、餐饮店经营
者也知道~因为旅客如果急需~高价也必须的买~就算制假售假旅客也不可能花巨大成本追讨公道。
不管质量好与坏~一锤子买卖~卖了一次就是一次~卖个次品还有额外收益。于是~所有经营者都才过了道德的卢比孔~选择了单次博弈的“背叛”策略。
只要合作关系被预期一次或者有限次~投机主义者必然在最后关头图穷匕见~“背叛”所有“合作者”。我们也就能理解为什么~摆地摊的所卖的东西的质量总是那么让人不安心的重要原因。
单次博弈模型不仅帮助我深入理解了火车站如此混乱的内在原因~也指引我认识到开放的城市与封闭的村镇~为什么会显现出截然不同的民风这一问题。
城市中以流动人口居多~虽然有大量外来人口涌入城市~但大多只做短暂逗留~不管是本地人与外地人~还是外地人与本地人之间的合作关系都不会维系太久~这样地联系显得松散而不稳定。没有人知道对方会不会背叛自己~在何时背叛自己~于是都趁着对方选择“不合作”之前选择“背叛”。
也许为了避免被“背叛”的危险~刚开始就不愿和任何陌生人接触~持不合作的态度~于是造成了城市人之间的冷漠,
也许为了获得有限次博弈的额外收益~在初期假装合作~然后突然之间选择背叛~并立即终止关系~于是惊心动魄的较量与竞争常在城市的舞台上演。
那么~城市以工商业为主的市场经济环境带来的激烈竞争~以及大量外来人口不稳定的生存环境带来治安上的不稳定因素~则加剧了城市较为紧张的社会关系。
众所周知~以中国为代表的中华文化圈的东亚人~注重家庭~讲究内外有别~对内关会备至~对外却是“各家自扫门前雪~休管他人瓦上霜”。所以~不必奇怪~日本人可以对自己的同胞彬彬有礼~也可以对并非同宗同族的中国人亮出屠刀~撕下文明的面纱。
在封闭的城镇、不发的乡村~民风之所以淳朴~根本原因在于其社会结构建立以家庭为单位的简单经济体之上~如农业、手工业、个体工商业。简单经济体自给自足~互帮互助~不相互压榨~这无疑密切了人与人之间的联系。没有太多外来人口~以致于“一家人昨晚吵架~第二天一早全城皆知”~每个人的人际圈既扩展到全城有仅限于全城。这就给每个交往组合的人们之间相互间提供了一个预期——我们相互认识~知根知底~每个人为了长远的利益必须永久合作下去~而任何一个背叛群体利益的人将被这个集体摒弃。
这样没有敢为眼前的额外收益~铤而走险选择背叛~而在之后的长期关系中被其他人抛弃。他们必须在自己所在的范围内和其他人保持良好的合作关系~并永久持续下去。没有人敢投机取巧~每个人在做选择的时候都考虑到别人在远期的反馈行动~那么所有人都经自觉的保持与其他人的合作关系。
淳朴的民风~形成了。武汉、南昌和赣州不就是很好的例子么,
最后~从原因中~我们也到了一些重要的启示——如何避免有限
次博弈中的“背叛”?
一、 愿意合作者要发出持续合作下去的预期。比如第一
次去某家店购物~要设法透露还会购买的可能~卖家从长远
考虑就会重视并提供更优质产品服务。
二、 背叛者应该受到有效地威胁和惩罚。比如~政府给
诚信商家颁发锦旗或打上特别标志~引导消费者购买诚信商
家商品~而使不守法的商家遭受损失。