我学习统计学,学习博弈论,学习运筹学,还参加过经济学的一个讨论班,都是想探究有效的合作模式与机制。 发现一篇文章,叫“ Five Rules for the Evolution of Cooperation ”是篇经典的文献。我计划就这篇文章,结合我自己的思考,一点点展开来,讨论合作的模式和机制。 五个规则分别是:(1)血缘关系;(2)直接交互;(3)间接交互;(4)网络交互;(5)团体合作。 参考材料如下: Supporting Online Material for Five Rules for the Evolution of Cooperation __Nowak.SOM.pdf Five rules for the evolution of cooperation_PPT_seminar_Nowak.pdf
最近,因为某些想法而wiki了下博弈论,当然就看到了大名鼎鼎的疯子納什,深为普林斯顿的包容所折服,也顺便看到了 赖因哈德·泽尔腾 ,这个也许是离我最近的诺奖获得者了。但是,前段时间听同校经济系的同学说起他的演讲毫无逻辑,十分难以follow。不过,看他在诺奖网站的自我简介里却是有两句甚是有味的。 I had to learn to trust my own judgment rather than official propaganda or public opinion. This was a strong influence on my intellectual development. 看了这句,让我想起的并非,现在很多人缺乏独立思考,相反,我倒是认为我们的独立思考是太过了,不仅有直接的独立思考,甚至在此一步上,更深深地思考,我虽如此想,但是我该怎么说呢? 例子明显, 泽尔腾继续说道, My first contact with game theory was a popular article in Fortune Magazine which I read in my last high school year 我想会这样介绍自己研究动机的大牛在中国是不太有的吧,太下里巴了。。。(在此,也该反思科研过程中是否就该抱着学术搜索引擎) 自此,我忽然起了一个奇怪的念头,倘若中国科研界今天有领军人物获得了诺贝尔奖对我国科研的发展真的有益吗? 鸟尽弓藏,兔死狗烹。向来是中国官道首选的手段,在这样的原则下,疯子是无力挤进领军的,因为他尚不被认可有弓,狗之用。这样,大批诺奖得主估计都得徘徊在体制之外了。 中国科研领军人物,先不论科研水平,卖相首先得好,人情必须练达,更不可有方向性错误。 研究获奖首先感谢国家,研究心得自是阳春白雪。 在此,不免抱怨一句,在中国,学的真本事确实是难啊,让我们这些心智不熟的毛头小子还得先看穿迷雾才行。 这样的科研领军人物,获得诺奖之后,示范的是什么?我看多半不是对真理的追求,而是成为体制自我标榜的卖点,进一步培养体制内人的有力依据,如此看来,似乎无人得奖反倒是更好了。 在此,恳请大牛们,有了好成果一定努力捂住,直到去行政化之革命功成。到时以堂堂正正的科研人的姿态来发表,而非弓狗之态去邀功。
论文外审,积德祈福,水平有限,敬请赐教! 算法博弈论简介 (修改版) 1.1 信息安全经济学 本文所涉及的科学领域为普适计算安全领域与计算机理论应用的交叉方向,即信息安全经济学,这是一个新兴的学科领域,并正在得到越来越多研究人员的关注。剑桥大学计算机实验室的 Ross Anderson 和 TylerMoore 在 2006 年 10 月 27 日《科学》杂志上刊发的《信息安全经济学( The Economics of Information Security )》一文 , 标志着该学科领域的提出。信息安全经济学的基本观点是通过近些年的观察实践,发现许多安全问题的出现并非技术设计问题而是缺乏正确有效的激励机制,与以往 安全技术限制非法用户的使用不同,信息安全经济学使用安全机制通过影响系统参与用户的策略选择,使用户之间相互影响和制约以完成系统的预定目标。 信息安全经济学的一个重要理念是引入微观经济学中外部性的概念,即实体操作直接对第三方产生消极或积极影响却没有承担相应的义务或者获得回报。消极外部性的 一个例子是隐藏动作导致交互结果的失败,如在网络中双方实体进行数据包中继操作时,实体可以执行不易被观察到的丢包操作从而导致传输失败。解决消极外部性 的方法是要求实体承担责任,即不正常操作时要受到惩罚(可通过其他实体操作的外部性实现),或者正常操作时给予信用积分作为激励。 当前信息安全经济学研究大致有四个方向:一是软件漏洞与系统漏洞的经济学研究,二是隐私保护的经济学研究,三是激励与实施安全机制关系的研究,四是保护系统 不受理性对手侵害的研究。本文的研究主要集中在第四个方面。传统信息安全通常将用户分成两类:诚实用户和恶意用户,但实践发现系统的失效往往是由被称作策 略用户引起的,这种用户理性且自私,但没有恶意目的。类似的用户在垃圾邮件 、自私实体的 TCP 效应 、建立路由 、网络创建 等 等领域都有出现。在普适计算信任模型中,策略用户可以在推荐获取、推荐真实信任值等方面采取不转发或不提供推荐信息、给出虚假信任值或团体欺骗等非合作操 作,导致信任值难以体现用户间的真实关系,失去了信任模型本应实现的作用和意义。在本文的研究中,还有两个方面需要注意,一是公平性方面,由于自私实体的 理性化,在激励或者报酬分配时都需要考虑公平性;二是考虑网络拓扑结构对用户操作乃至对信息安全的影响 。 1.2 计算机经济学 信息安全经济学是计算机经济学的一个重要分支,后者是最新的计算机科学与经济学的交叉研究领域。计算机经济学不仅包括将商业活动信息化的传统电子商务领域,还包括利用经济学方法如博弈论、微观经济学等理论解决计算机科学中所遇到的问题,计算机经济学也被称做算法博弈论( Algorithmic Game Theory ) 。计算机经济学近年来得到了包括剑桥大学、耶鲁大学、哈佛大学、卡内基梅隆大学、加州伯克利大学、斯坦福大学和希伯来大学等世界各大著名研究机构的重点研究,在 ACM SIGECOM 组织的大力推行引导下,该领域的会议如 EC 、 WEIS 、 WINE 、 NetEcon 、 SAGT 、 GameComm 、 GameNets 如雨后春笋般出现并吸引越来越多知名研究人员参与到这个领域的研究,计算机经济学将成为今后几年计算机方面非常热的一个研究领域。 算法博弈论作为计算机理论科学的一个新领域,重点关注并解决有关拍卖、网络和人类行为的根本问题,它与微观经济学和博弈论的不同表现在以下几方面 :一是应用领域方面的不同,主要包括类 Internet 网络和非传统拍卖;二是应用定量工程性的方法,从具体优化问题的角度对应用建模,寻求最优解、判断不可解问题以及研究可解优化的上下限问题;三是讨论可计算性问题,相对一些经济方法无法在线性时间内由计算机解决( NP-C 问题),算法博弈论将可计算性作为算法实施必须考虑的限制条件。算法博弈论大略包括以下几个研究领域:一是研究各种均衡(如 Nash 均衡、子博弈 Nash 均衡等)的计算复杂性问题;二是从博弈论的观点研究计算机学科中的许多问题;三是算法机制设计领域,研究领域包括网络结构及性能方面的研究、在线拍卖和在线交易、在线广告、搜索结果页面排序及其它一些分布式应用;四是计算性社会选择问题。 作为经济学中的重要研究工具,博弈论通常被用于研究公司在市场竞争中如何采取恰当的经营策略以达到期望的目标,而博弈论被引入到计算机科学则归功于互联网及 其他开放式网络的出现。在这些开放性网络应用中存在着许多不同实体间的策略性交互操作,每个实体都有理性,来自于不同的组织并具有自己的利益,每个实体都 依据实际环境选择有利于自身的操作策略并实现利益的最大化,这些策略之间最终达到一种相互制约的均衡状态。在达到的各种均衡状态中,有些是系统设计者所希 望看到的,有的则恰恰相反。博弈论研究这些均衡状态的特性以便于区分选择,而机制设计则通过制定实体需遵守的交互机制,促使实体在自身利益驱动下选择设计 者期望的策略,实现符合设计目标的系统总体均衡态。 1.3 博弈论与机制设计 1.3.1 博弈论简介 下面,对博弈论和机制设计做一简要介绍,详细内容请参考文献 。 博弈论被作为正式学科,一般以 1944 年美籍匈牙利数学家 John Von Neumann( 同时也是算法的创始人和计算机之父 ) 和 Oskar Morgenstern 发表合著的《 Game Theory and Economic Behaviors 》 ( 《博弈论与经济行为》 ) 为标志,并在 20 世纪 50 年代由博弈论大师 John Nash 提出并研究了博弈论中最重要的解概念– Nash 均衡,奠定了非合作博弈论的理论基础。 博弈论是应用数学的一个分支,当前其应用领域已经从最初的军事领域扩展到政治、经济、文化、法律和哲学等社会性学科以及生物、工程和计算机等理工性学科,并 以经济学科中的应用最被人所熟知。博弈论试图以数学方式刻画策略性场景中的用户行为,每个用户的选择成功与否取决于其他人的行为选择。 2005 年诺贝尔经济学奖得主 Robert Aumann 认为,“交互的决策论”是博弈论的一个最恰当的定义,而另一位诺贝尔经济奖得主 Roger B. Myerson 则将博弈论定义为“相互影响的决策理论”。 博弈论将实体间的相互操作看作是一个博弈,每个博弈参与者依据系统设计者事先定义好的规则选择策略并进行操作,在博弈结束时获得一定收益。博弈可以分为静态 博弈和动态博弈,静态博弈指所有博弈者同时进行策略选择,动态博弈指博弈者的操作具有先后之分,重复博弈也是动态博弈的一种。博弈类型也可以分为完全信息 博弈和非完全信息博弈,其中完全信息博弈指全体博弈者在进行策略选择时完全知道有关作出决定的所有信息,非完全信息博弈则相反,可能需要依凭一定的概率假 设进行操作。还可以分为非合作博弈与合作博弈,在非合作博弈中,实体用户之间没有签约协议或存在协作,在合作博弈中,实体间先协同获得最大的团体利益,再 将团体利益分配到每个个体实体,在利益分配时会涉及到公平性和团体稳定性等问题。当前研究中较多的采用非合作博弈,从合作博弈的角度出发的研究并不太多。 在实体具有的信息和理性基础上,实体对博弈进行预测并实际选择策略,最终达到一种相互制约的结果均衡状态,该结果即博弈问题的解。博弈论研究的中心问题就是寻找可能的解并研究其特性。对于非合作博弈论中的完全信息静态博弈,研究的最多的结果均衡态包括占优均衡和 Nash 均衡。占优均衡指每个人的选择策略都是占优策略而形成的一种均衡,占优策略是指不管他人选择何种策略,博弈者都有一个最大化自己收益的最佳策略, Nash 均衡是指当其他博弈者的策略不变时,单方改变自己的策略时不能增加自己的收益。占优均衡一定是 Nash 均衡,反之则不一定。相对于最简单基础的完全信息静态博弈,其他类型博弈的解都在 Nash 均衡的基础上进行了改进,如完全信息动态博弈主要研究子博弈精炼 Nash 均衡,不完全信息静态博弈主要研究贝叶斯 Nash 均衡,不完全信息动态博弈研究精炼贝叶斯 Nash 均衡。对于合作博弈论而言,解指参与合作的博弈者最终分配得到的支付。合作博弈论从合作团体稳定性、公平性等角度提出不同的解,有稳定集 (stable set) 、核心 (core) 、 Shapley 值、核 (kernel) 及核仁 (nucleolus) 等。 1.3.2 机制设计简介 相比博弈论对博弈解的求解和分析而言,提出机制设计的原因是由于机制设计者想执行一项社会决策或选择以达到某种社会性目的,但由于执行决策所需要的信息是分 布式的,只有社会成员自己知道,设计者不可能获得信息或者获取成本太高。因此,机制设计提供了一个关注激励社会成员汇报自己私有信息问题的分析框架,研究 如何设计一个博弈形式,或者称作机制,令社会成员参与其中,得出的博弈解恰好符合设计者所想达到的社会选择,这个问题也被称作社会选择的实施问题。这里社 会选择是指整个社会群体性的选择结果,这个结果是由诸多独立博弈者通过表达各自的偏好而聚集得出的,社会选择的结果会反过来影响每个独立博弈者的收益。比 方在政治选举时,每个选民表达自己的意愿偏好,选择一位候选者当选,所有选民的偏好聚集在一起共同决定了哪位候选者可以当选,候选者上任以后实施的政策会 翻过来影响到选民的切身利益。 以社会选择函数来刻画社会选择的标准,如果对于每一种可能的社会状态,博弈形式(或机制)得到均衡解的结果与社会选择函数对于同一社会状态的计算结果相同, 我们就说该博弈形式(或机制)以某均衡解的方式实施了该社会选择函数。显然,社会选择函数是否能被某机制实施与解的选择(如占优均衡还是 Nash 均衡)密切相关。如果社会选择的结果是个社会结果集合,则以多值映射社会选择规则进行表示。 机制包括直观显示机制(或称作直观机制、显示机制、直接机制)和非直观显示机制(或称作非直观机制、一般机制、间接机制)。在直观机制中,设计者直接询问参 与者的私有状态信息(或类型信息或私有偏好),非直观机制中设计者只能观测到参与者的行为(或消息),该行为由以内在状态为参数的显示策略函数决定。如果 所有参与者的行为共同构成一个 Nash 均衡,则称其对应的显示策略共同构成一个事后纳什均衡( ex-post Nash equilibrium )。 机制设计中的一个重要问题就是如何设置恰当的机制,使每个博弈者显示自己的真实私有偏好,因为有的博弈者为了获得自身利益的最大化而隐瞒自身真实偏好,或者 通过策略性的显示偏好而操纵社会选择的结果。一般的,需要通过某种激励策略实现这个目的,如果一种机制能够获得博弈者的真实信息并能够防止博弈者的策略性 操纵,这种机制被称作真实机制,也被叫做激励相容( incentive compatible )机制或防护策略( strategy-proof ) 机制。需要注意的是,博弈者最终收益的组成,若采用准线性的收益形式,最终收益等于初始收益与获得报酬的两者之和。通常设计的显示机制包括社会结果选择函 数与实体支付函数两部分,机制的设计就是通过适当的构造这两个函数,使机制满足一些所需要的特性,如实体只有在报告真实信息时才能获得最大最终收益的真实 机制特性。真实机制可以被用作获得用户的真实意图,在一些计算机应用有此需要时,就可以应用机制设计的方式予以实现。 激励相容的直观机制具有良好的数学性质,可由一组表示激励限定的不等式表示并进行分析,但在实际应用中似乎很难有直接应用直观机制的情况,往往都是通过观察 参与者显示的行为,分析得出一组显示策略构成一个均衡解。显示原理较好的解决了这个问题,该原理声明任何具有均衡解的非直观机制都存在一个对等的直观机 制,且该直观机制激励相容。该原理的证明较为简单,以占优均衡为例,如果对于一个非直观机制存在一组显示策略构成一个占优均衡,则可以如下方式构建一个激 励相容的直观机制:直观机制直接询问私有状态信息,以获得的状态信息为参数,通过作为均衡解的显示策略算出对应的行为,机制再以该组行为为输入参数,利用 原有的非直观机制模拟参与者实现社会选择函数。依据占优均衡解的定义,参与者自己在非直观机制中的占优策略是以其真实私有状态信息为参数计算出的行为,一 定使汇报者自己获得最大受益。因此如果参与者在直接机制中汇报虚假状态信息,则机制算出的行为一定不能使自身利益最大化。显示原理还有其它相似的贝叶斯版 本。基于显示原理,我们可以重点关注并研究激励相容的直观机制。 参考文献 R. Anderson and T. Moore. The economics of information security. Science, 314(5799):610,2006. E. Allman. The economics of spam. Queue, 1(9):80, 2003. A. Akella, S. Seshan, R. Karp, S. Shenker, and C. Papadimitriou. Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP. In Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, pages 117–130. ACM, 2002. T. Roughgarden and ´ E. Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):259, 2002. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 295–304. IEEE, 2004. M.E.J. Newman. The structure and function of complex networks. SIAM review, 45(2):167–256, 2003. R. Albert, H. Jeong, and A.L. Barab´ asi. Error and attack tolerance of complex networks. Nature, 406(6794):378–382, 2000. N. Nisan. Algorithmic game theory. Cambridge University Press, 2007. T. Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78–86, 2010. R.B. Myerson. Game Theory: Analysis of Conflict. Boston, USA, 1991. G. Owen. Game Theory. Academic Press, 1982. D. Fudenberg and J. Tirole. Game theory. 1991, 1991. 罗云峰 . 博弈论教程 . 清华大学出版社 , 2007. E. Maskin and T. Sjostrom. Implementation theory. Handbook of social Choice and Welfare, 1:237–288, 2002. 7