最近以第一作者身份被IEEE Communications Letters期刊录用一篇论文 标题为:Distributed Channel Access for Device-to-Device Communications: A Hypergraph-based Learning Solution 作者: Sun Youming; Wu Qihui; Xu Yuhua; Zhang Yuli; Sun Fenggang; Wang Jinlong Abstract: In this letter, we propose a learning solution fordistributed channel access in device-to-device communications based on hypergraph interference model. We first define a new interference metric for hypergraph model, and then formulate this distributed channel access problem as a local altruistic game, which is proved to be an exact potential game admitting at least one pure strategy Nash equilibrium (PNE). A distributed learning algorithm is designed to quickly achieve the optimal PNE, which can minimize the defined networks’ interference metric. Simulation results show that the proposed algorithm outperforms the existing schemes and significantly improves the spectrum efficiency. 考虑在未来密集网络中(D2D网络,小蜂窝网络)存在诸多弱干扰源,传统的二元干扰图只强调了成对节点间的强干扰关系,但是忽略了干扰叠加效用。因此该论文从图模型出发,利用超图干扰模型刻画累计干扰关系。目前虽已经有部分研究工作关注超图干扰模型,但是这部分工作都是基于集中式的资源分配方法,需要全局的信息交互,因而难以适用到具有高度动态性和缺乏信息交互的D2D网络场景。该论文将D2D网络中的分布式信道接入问题建模为局部互利博弈模型,并证明该博弈为精确势能博弈。然后设计了一种快速学习算法收敛到博弈的纯策略纳什均衡解。
期刊中文名: 《博弈论与实验经济学》 期刊英文名:Journal of Experimental Economics andManagement Science 主办单位名 : China Association of Game theory andexperimental economics Institute of Quantitative Technical Economics, Chinese Academy of Social Sciences Chongqing Real Estate College ( 重庆房地产职业技术学院 ) 期刊出版 商 :OLYMPIA ACADEMIC PUBLISHER CORPORATION Address:115 SKYLINE DR , EDMONDS, WA98020, USA ISSN: 2373-3705 (Print) 2372-9783 (Online) 主编 姓名 : 未公示 责任编辑:未公示 期刊检索: EI 检索 报告依据: 英文投稿说明:Notice to Authors.pdf 中文投稿说明:博弈论与实验经济学会--官方网站.pdf 期刊注册单位:重庆房地产职业技术学院.pdf 期刊编委信息:Editorial Board.pdf 期刊英文网站: http://journal.expeconomics.org/ 学会中文网站: http://www.expeconomics.org/ 本报告链接: http://blog.sciencenet.cn/blog-30719-911636.html 报告时间 :20150808
最近《福布斯》杂志提出的一个方向“Toward an evolutionary theory of business”(见 Forbes ),虽然是个自亚当-斯密以来的老问题,但交易的动态模型这个老问题一直没有解决,也就是说经济学的理论基础本身就存在问题。从经验总结经济学规律是对的,但也要有一定的理论逻辑推导,现在一直有人提一个尖锐的问题:经济学是不是一门真正的科学? 经济学的中心问题就是市场交易影响价格的理论问题,博弈论作为现有微观经济学的一个研究工具,有优点,但主要缺陷就是不能解决价格形成这个难题。 价格形成涉及到交易过程,但一般认为博弈论是一个静态化的理论体系,现有的博弈论就难以解决这样的动态问题。 现在发展的演化博弈论并没有在价格形成方面取得突破性进展,主要问题可能出在交易者理性模型的认识和建立上。 博弈论从数学角度研究经济学,针对的就是交易或交换,可最终还是卡在数学模型上了。从经济学基础模型的角度来看,经济学的理论突破可以说先得在数学上有所突破。 经济学只有解决了理论基础本身存在的问题,再和从经验总结出来的经济规律相互印证,既有理论指导也能解释实践现象,我们就可以说:经济学是像物理学一样的科学。 《福布斯》杂志是从企业角度提出这一问题的:“经济学怎样能够帮助企业做好交易或生意?”如果单纯靠静态的理论解释,很困难,难免面对这样的疑问。
——旧札新钞 ( 151 ) @ 荷兰天体物理学家 Hendrik van de Hulst 说,磁场之于天文学犹如性之于心理学。在弗洛伊德以前,性被忽略了;紧接着,性似乎能解释一切;但后来,观点就越来越折中了。“ Magnetic fields in astronomy are like sex in psychology. Before Freud, it was ignored; then immediately afterward it was going to explain everything; but with time a more balanced view has evolved ” @ David McAdams 在介绍博弈论的新书 Game-Changer: Game Theory and the Art of Transforming Strategic Situations 的引言开头,引用了诸葛亮的一句名言: “The wise win before they fight, while the ignorant fight to win.” 原话见 《便宜十六策》(治军第九):“ 智者先勝而後求戰,闇者先戰而後求勝 。” @ 趙之謙 自詡天分高,說“鄧(石如)天四人六,包(世臣)天三人七,吳(讓之)天一人九”,而他自己是“天七人三”。他的天才,似乎就表現在書法線條的搖曳多姿和結體的靈巧生動。日本藏《梅花盦詩》四條屏可謂趙書佳品。 网上找的,不知谁做的,把四屏的次序弄错了。
1. Game Theory for Applied Economists , Princeton UniversityPress, 1992. (International version: A Primer in Game Theory,Harvester-Wheatsheaf.) translated into Chinese, Greek, Hungarian,Italian, Japanese, and Spanish.; Robert Gibbons; Prentice Hall, 1992 博弈论入门经典,俗称“吉本斯”,有中译版,适合初学者,但内容和深度有所不足 2. A Course in Game Theory; Martin J. Osborne, Ariel Rubinstein; MIT Press, 1994 博弈论教学经典,简称“OR”,内容全面且具有一定深度,信息量非常大,但缺点在于大量采用数学描述,只适合课堂使用,有中译版 3. An Introduction to Game Theory; Martin J. Osborne; Oxford University Press, 2003 OR的简化版,为降低难度,著者删节了部分高阶内容,弱化了形式化描述,同时附带很多直观的实例分析,非常有助于理解 4. Game Theory; Drew Fudenberg, Jean Tirole; MIT Press, 1991 内容全面,形式化强度感觉没有OR那么大,描述较简洁,因此需要一定基础;书中取材也较新颖,适应研究生阅读。有中译版 5. 博弈论与信息经济学; 张维迎; 上海人民出版社, 2004 国内口碑不错,内容也较全面,但某些内容和实例跟经济学基础内容绑定得略显紧密,不太适合其他专业背景的读者阅读 最后,一点小忠告:博弈论需要一定的微观经济学基础,不然可能无法理解其中的多数具体实例,令理解大打折扣;在选取用书方面,尽量看英文原版的,不得已再看中文原著的,千万不要看中文翻译的。
我学习统计学,学习博弈论,学习运筹学,还参加过经济学的一个讨论班,都是想探究有效的合作模式与机制。 发现一篇文章,叫“ 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