博文
算法博弈论简介 （修改版）
精选
|||
算法博弈论简介 （修改版）
1.1 信息安全经济学
本文所涉及的科学领域为普适计算安全领域与计算机理论应用的交叉方向，即信息安全经济学，这是一个新兴的学科领域，并正在得到越来越多研究人员的关注。剑桥大学计算机实验室的Ross Anderson 和TylerMoore在2006年10月27日《科学》杂志上刊发的《信息安全经济学（The Economics of Information Security）》一文[1]，标志着该学科领域的提出。信息安全经济学的基本观点是通过近些年的观察实践，发现许多安全问题的出现并非技术设计问题而是缺乏正确有效的激励机制，与以往安全技术限制非法用户的使用不同，信息安全经济学使用安全机制通过影响系统参与用户的策略选择，使用户之间相互影响和制约以完成系统的预定目标。
信息安全经济学的一个重要理念是引入微观经济学中外部性的概念，即实体操作直接对第三方产生消极或积极影响却没有承担相应的义务或者获得回报。消极外部性的一个例子是隐藏动作导致交互结果的失败，如在网络中双方实体进行数据包中继操作时，实体可以执行不易被观察到的丢包操作从而导致传输失败。解决消极外部性的方法是要求实体承担责任，即不正常操作时要受到惩罚（可通过其他实体操作的外部性实现），或者正常操作时给予信用积分作为激励。
当前信息安全经济学研究大致有四个方向：一是软件漏洞与系统漏洞的经济学研究，二是隐私保护的经济学研究，三是激励与实施安全机制关系的研究，四是保护系统不受理性对手侵害的研究。本文的研究主要集中在第四个方面。传统信息安全通常将用户分成两类：诚实用户和恶意用户，但实践发现系统的失效往往是由被称作策略用户引起的，这种用户理性且自私，但没有恶意目的。类似的用户在垃圾邮件[2]、自私实体的TCP效应[3]、建立路由[4]、网络创建[5]等等领域都有出现。在普适计算信任模型中，策略用户可以在推荐获取、推荐真实信任值等方面采取不转发或不提供推荐信息、给出虚假信任值或团体欺骗等非合作操作，导致信任值难以体现用户间的真实关系，失去了信任模型本应实现的作用和意义。在本文的研究中，还有两个方面需要注意，一是公平性方面，由于自私实体的理性化，在激励或者报酬分配时都需要考虑公平性；二是考虑网络拓扑结构对用户操作乃至对信息安全的影响[6][7]。
1.2 计算机经济学
信息安全经济学是计算机经济学的一个重要分支，后者是最新的计算机科学与经济学的交叉研究领域。计算机经济学不仅包括将商业活动信息化的传统电子商务领域，还包括利用经济学方法如博弈论、微观经济学等理论解决计算机科学中所遇到的问题，计算机经济学也被称做算法博弈论（Algorithmic Game Theory）[8]。计算机经济学近年来得到了包括剑桥大学、耶鲁大学、哈佛大学、卡内基梅隆大学、加州伯克利大学、斯坦福大学和希伯来大学等世界各大著名研究机构的重点研究，在ACM SIGECOM组织的大力推行引导下，该领域的会议如EC、WEIS、WINE、NetEcon、SAGT、GameComm、GameNets如雨后春笋般出现并吸引越来越多知名研究人员参与到这个领域的研究，计算机经济学将成为今后几年计算机方面非常热的一个研究领域。
算法博弈论作为计算机理论科学的一个新领域，重点关注并解决有关拍卖、网络和人类行为的根本问题，它与微观经济学和博弈论的不同表现在以下几方面[9]：一是应用领域方面的不同，主要包括类Internet 网络和非传统拍卖；二是应用定量工程性的方法，从具体优化问题的角度对应用建模，寻求最优解、判断不可解问题以及研究可解优化的上下限问题；三是讨论可计算性问题，相对一些经济方法无法在线性时间内由计算机解决（NP-C问题），算法博弈论将可计算性作为算法实施必须考虑的限制条件。算法博弈论大略包括以下几个研究领域：一是研究各种均衡（如Nash均衡、子博弈Nash均衡等）的计算复杂性问题；二是从博弈论的观点研究计算机学科中的许多问题；三是算法机制设计领域，研究领域包括网络结构及性能方面的研究、在线拍卖和在线交易、在线广告、搜索结果页面排序及其它一些分布式应用；四是计算性社会选择问题。
作为经济学中的重要研究工具，博弈论通常被用于研究公司在市场竞争中如何采取恰当的经营策略以达到期望的目标，而博弈论被引入到计算机科学则归功于互联网及其他开放式网络的出现。在这些开放性网络应用中存在着许多不同实体间的策略性交互操作，每个实体都有理性，来自于不同的组织并具有自己的利益，每个实体都依据实际环境选择有利于自身的操作策略并实现利益的最大化，这些策略之间最终达到一种相互制约的均衡状态。在达到的各种均衡状态中，有些是系统设计者所希望看到的，有的则恰恰相反。博弈论研究这些均衡状态的特性以便于区分选择，而机制设计则通过制定实体需遵守的交互机制，促使实体在自身利益驱动下选择设计者期望的策略，实现符合设计目标的系统总体均衡态。
1.3 博弈论与机制设计
1.3.1 博弈论简介
下面，对博弈论和机制设计做一简要介绍，详细内容请参考文献[10, 11, 12,13, 14]。
博弈论被作为正式学科，一般以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）机制。需要注意的是，博弈者最终收益的组成，若采用准线性的收益形式，最终收益等于初始收益与获得报酬的两者之和。通常设计的显示机制包括社会结果选择函数与实体支付函数两部分，机制的设计就是通过适当的构造这两个函数，使机制满足一些所需要的特性，如实体只有在报告真实信息时才能获得最大最终收益的真实机制特性。真实机制可以被用作获得用户的真实意图，在一些计算机应用有此需要时，就可以应用机制设计的方式予以实现。
激励相容的直观机制具有良好的数学性质，可由一组表示激励限定的不等式表示并进行分析，但在实际应用中似乎很难有直接应用直观机制的情况，往往都是通过观察参与者显示的行为，分析得出一组显示策略构成一个均衡解。显示原理较好的解决了这个问题，该原理声明任何具有均衡解的非直观机制都存在一个对等的直观机制，且该直观机制激励相容。该原理的证明较为简单，以占优均衡为例，如果对于一个非直观机制存在一组显示策略构成一个占优均衡，则可以如下方式构建一个激励相容的直观机制：直观机制直接询问私有状态信息，以获得的状态信息为参数，通过作为均衡解的显示策略算出对应的行为，机制再以该组行为为输入参数，利用原有的非直观机制模拟参与者实现社会选择函数。依据占优均衡解的定义，参与者自己在非直观机制中的占优策略是以其真实私有状态信息为参数计算出的行为，一定使汇报者自己获得最大受益。因此如果参与者在直接机制中汇报虚假状态信息，则机制算出的行为一定不能使自身利益最大化。显示原理还有其它相似的贝叶斯版本。基于显示原理，我们可以重点关注并研究激励相容的直观机制。
参考文献
[1] R. Anderson and T. Moore. The economics of information security. Science, 314(5799):610,2006.
[2] E. Allman. The economics of spam. Queue, 1(9):80, 2003.
[3] 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.
[4] T. Roughgarden and ´ E. Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):259, 2002.
[5] 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.
[6] M.E.J. Newman. The structure and function of complex networks. SIAM review, 45(2):167–256, 2003.
[7] R. Albert, H. Jeong, and A.L. Barab´ asi. Error and attack tolerance of complex networks. Nature, 406(6794):378–382, 2000.
[8] N. Nisan. Algorithmic game theory. Cambridge University Press, 2007.
[9] T. Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78–86, 2010.
[10] R.B. Myerson. Game Theory: Analysis of Conflict. Boston, USA, 1991.
[11] G. Owen. Game Theory. Academic Press, 1982.
[12] D. Fudenberg and J. Tirole. Game theory. 1991, 1991.
[13] 罗云峰. 博弈论教程. 清华大学出版社, 2007.
[14] E. Maskin and T. Sjostrom. Implementation theory. Handbook of social Choice and Welfare, 1:237–288, 2002. 7
https://blog.sciencenet.cn/blog-453771-333460.html
下一篇：算法博弈论相关信息资源（不断补充中）
