引言与概览 本章介绍博弈论和机制设计的重要性以及它们在当前的意义。现代社会，信息和通 信技术迅猛发展，这蕴含着很多有趣的新东西。对于这些新东西的研发，博弈论和机制 设计在很多时候非常有用。本章提供几个启发性的例子，然后介绍该领域当今研究的趋 势和前沿。 博弈论和机制设计研究策略人（strategicagents）之间的互动。博弈论的主题是博 引言与概览 奔分析（analysisofgames），而机制设计则是设计博弈（designinggames）以达到合意 的结果。当前，博弈论和机制设计是跨学科问题求解的活跃领域。本书的目的在于帮助 读者理解博弈论和机制设计背后的科学，看清如何使用它们求解互联网时代的问题。本 书内容包含三大领域：非合作博弈论（non-cooperativegametheory）、合作博弈论（co- operativegametheory）以及机制设计（mechanismdesign）。 传统使用博弈论和机制设计的学科有经济学、工商管理、社会学、政治学、生物 学、哲学和工程学。在工程学领域，博弈论和机制设计被广泛用于工业工程、存货管 理、供应链管理、电子商务以及多智能体系统。最近，博弈论已涉足计算机科学和电子 工程学科的很多新兴应用领域。

1.1 博弈论：策略互动科学

博弈论（gametheory）中的博弈（game）一词，是指理性且智能的决策者或参与 人之间的互动。大致地说，参与人的理性（rationality）意味着他选择策略，以使得他 的收益最大（这里的收益需要明确定义），而智能（intelligence）则是指参与人能够计 算他们的最优策略。

博弈论是逻辑和数学分析的工具之一，它模拟决策者之间的冲突和合作，并且通过 使用均衡分析为人们提供了一种预测参与人之间互动结果的理论方法。传统的博弈，例 如国际象棋和桥牌，是博弈最自然的例子。博弈论研究的博弈更具一般性，可以视为传 统博弈的抽象和延伸。这类抽象和延伸能够包含社会互动的所有复杂性和特征。因此， 博弈论已成为社会科学尤其是经济学极其重要的工具。博弈论着眼于博弈分析，机制设 计则强调通过博奔设计来实现合意结果一一机制设计可以视为博弈过程的反转。在下 文，若非特别指出，我们把博弈论和机制设计统一简称为博弈论。 口博弈论和机制设计的价值 我们用四个简单例子说明博弈论和机制设计如何模拟策略人之间的冲突和合作。这 些例子是现实一般情形的抽象。 学生协作问题 假设印度科技学院（简称IISc）的两个学生（学生1和2）是好朋友。这两个学生 喜欢待在一起，要么在IISc一起学习，要么去学院附近的MG路一起玩要。因此，为 了待在一起，他们有两个选择（或称策略）：一是ⅡISc，二是MG路。如果他们在IISc 一起学习，每人得到的收益（效用）为100。如果他们一起去MG路玩要，每人得到的 收益仅为10。如果他们中的一个人待在IISc而另一个人去MG路，那么每人的收益都 为0。两人的收益见表1-1，意思不言自喻。假设两人必须同时且独自选择自己的策 略。作为理性和智能人，每人将选择最优可能策略。显然，两人都选IISc是最优可能 博 结果，两人都选MG路也比较好，但这个选择明显比前者差。最差的情形出现在两人选 奔论与机 择不同的策略，因为每个人最终得到的效用都为零。

表1-1：两个学生在不同情形下的收益

博弈论为我们提供了预测这两个学生所选策略的理论方法。在这个例子中，两人都 选择IISc以及两人都选择MG路是所谓的纳什均衡（Nashequilibria），纳什均衡是指 下面这样的策略组，在这样的策略组中，任何参与人都无法通过独自偏离自己的均衡策 略而获得更大的收益。对于这个博弈，博弈理论还提供了另外的预测，尽管这个预测表 面上不符合直觉，但它的确是参与人都不会反对的一个均衡结果。这个结果就是所谓的 混合策略纳什均衡（mixedstrategyNashequilibrium）一每人以1/11的概率选择 IISc且以10/11的概率选择MG路。它也许能说明如果你想找到某些学生，为何你通常 能在MG路上而不是IISc教室找到他们。 这个博弈通常称为协调博弈（coordinationgame），它是很多现实社会和专业技术 情形的抽象。在这里，我们不打算展开讨论，仅给出简要评价：博弈论为决策者的这类 互动结果提供了科学预测方法。 布雷斯论 我们现在介绍布雷斯论（Braessparadox），它以德国数学家迪特里希·布雷斯

（DietrichBraess）的名字命名。这个论通常与交通网络联系在一起，它说明交通网络 在增加容量后，可能反而对通行者不利（以交通时间衡量）。这个事实不是那么直观。 我们这里介绍的博弈来自Easley和Kleinberg合著的书。[1] % S 起点 终点 B 图1一1有四个节点的交通网络 图1一1中的交通网络由起点S、终点T以及两个中间点A和B组成。所有从S出 发的车辆可以经过A点或B点。假设不管路上的车辆数为多少，从S到B或者从A到 T都需要25分钟。另一方面，从S到A需要m/50分钟，其中m是SA路上的车辆数。 类似地，从B到T需要m/50分钟，其中m是BT路上的车辆数。 引言与概览 起点 终点 B 图1一2开通AB路之后的交通网 假设为了缓解交通网的拥挤程度，我们开通AB路（为简单起见，我们假设从A到 B所需时间为0)。图1一2画出了开通AB路之后的新交通网。现在从S到T有三条不 同的道路可走：（1）S—A—T；（2）S—B—T；以及（3）S—A—B—T。如果S到T 所需时间变短了，旅客将会更高兴。直觉告诉我们，图1一2的交通网即开通AB路后 的新交通网将会使旅客更高兴。然而，通过使用均衡分析，博弈论已证明：图1一1中 的交通网对旅客更有利。 布雷斯论有很多现实证据。例如，在韩国首尔市，作为清溪川（Cheong gyecheon）改造工程的一部分，在关闭一条高速通道之后，首尔周边的交通拥挤程度大 为缓解。在德国斯图加特市（Stuttgart），为了缓解交通拥挤，政府花费巨资修建新路，

然而人们发现只有在关闭其中一些新建道路时，交通状况才能得以改善。我们可以使用 博弈论，通过模拟交通网使用者的互动情形来预测可能出现的结果。在第4、5和6章， 我们将详细研究这个例子。 维克瑞拍卖 假设某个卖主打算把一件不可分割商品卖给n个潜在买主中的一个。比如，政府打 算将某个无线电频谱许可证卖给多个服务商中的一个（参见图1一3）。每个参与人对出 售的东西有一定估值或称评价（valuation）。例如，在频谱许可证这个例子中，假设有 四个服务商（服务商1、2、3和4），他们对该许可证的评价分别为4亿元、5亿元、7 亿元以及10亿元。在频谱拍卖中，政府邀请潜在买主投标并且根据拍卖协议决定谁中 标。有两种简单而常用的拍卖方法，即第一价格密封拍卖（firstpricesealedbidauc- tion）和第二价格密封拍卖（secondpricesealedbidauction）。在第一价格密封拍卖中， 报价最高的投标人中标，他应按照报价付款。在第二价格密封拍卖中，报价最高的投标 人中标，但他仅需要按照第二高的报价付款。 LL 无线电频谱 买者1 买者2 卖者 买者n 图1—3频谱拍卖 上面的每种拍卖都可以模拟为涉及卖主和买主的博弈。在第一价格密封拍卖中，投 标人的报价小于他们对拍卖物的估值。在第二价格密封拍卖中，投标人将更大胆，因为 他们知道如果他们中标，他们实际支付的钱数小于自己的报价。威廉·维克瑞（Wil- liamVickrey）证明，在第二价格密封拍卖中，投标人的报价正好等于各自对拍卖物的 估值。这一杰出工作使得维克瑞获得了诺贝尔经济学奖。事实上，维克瑞证明每个投标 人的最优选择是，不管其他投标人的报价为多少，他都应该如实报价（报价等于他的估 值）。在上面的例子中，如果政府使用第二价格密封拍卖，那么投标人的报价等于各自 的估值，服务商4将中标并获得许可证。这个服务商将向政府支付7亿元，注意，这是 第二高的报价。因此，在第二价格密封拍卖中，尽管卖者不知道投标人对拍卖物的评 价，但他能够通过投标人的报价获得这个信息。当前广泛使用的各种拍卖协议，其背后 的科学正是博弈论和机制设计。 分钱博弈 三人商议如何分300元钱。每个参与人都可以提出分配方案，在任何分配方案中，

每个人分得的钱数不能为负，三人分得的钱数总和不能大于300。如果两人以上（含两 人）提出的方案相同，就按该方案分钱。例如，如果参与人1和2提出的分配方案为 （150，150，0），参与人3提出的方案为（100，100，100），则按照（150，150，0）分 钱。然而，参与人3可用分配方案（0，225，75）来诱惑参与人2，如果参与人2和3提 出这个方案，那么原来的方案即（150，150，0）就被推翻了。注意，分配方案（0， 225，75）使得参与人2和3的状况严格变好。然而，参与人1现在可以诱惑参与人3， 两人共同提出方案（200，0，100），这个方案使得参与人1和3的状况严格变好。这样 的议价永无尽头，联盟不断破裂，新联盟不断形成……·这种情形在现实世界（例如，在 政治和商业领域）比较常见。 传统方法很难预测这种情形的结果。合作博弈论能以系统且科学的方式帮助我们分 析这种情形。例如，通过将上述情形模拟为合作博弈，我们可以证明，这个博弈的核 （core）是空的，这意味着任何一种分配方案都不是稳定的，它总会被两人合谋推翻。 我们也可以证明，这个博弈的夏普利值（Shapleyvalue）为（100，100，100），在这个 例子中，夏普利值提供了一种公平分配财富的方法。 口博奔论：丰富的历史 作为数学分支和建模工具，博弈论有着丰富的历史，它的奠基和发展源于20世纪 一批最聪明的人物的贡献。图1一4给出了在博弈论和机制设计领域做出突破性贡献的 传奇人物。约翰·冯·诺依曼（JohnvonNeumann）和奥斯卡·摩根斯坦（Oskar Morgenstern）是1920年代、1930年代以及1940年代博弈论的奠基者。他们的杰出合 第 作构建了博弈论基础，并且留下了里程碑式的著作《博弈论与经济行为》（TheTheory 章 ofGamesandEconomicBehavior）。2]这本书至今仍是博弈论早期开创结果的权威来 引 源。在冯·诺依曼和摩根斯坦工作的基础上，一些著名博弈论学家将博弈论发展为经济 言 学。博弈论的重要性以及他们的贡献体现在一批博弈论学家先后于1994年、1996年、 与 概 2005年、2007年和2012年获得瑞典中央银行奖（诺贝尔经济学奖）。事实上，从1994 览 年到2012年，多达11位博弈论学家获得此奖。 约翰·纳什（JohnNash）、约翰·海萨尼（JohnHarsanyi）、莱茵哈德·泽尔腾 （ReinhardSelten）于1994年获得诺贝尔奖，因为他们在博弈均衡分析上做出了突破性 的工作。威廉·维克瑞（WilliamVickrey）凭借拍卖理论获得1996年诺贝尔奖。2005 年，罗伯特·奥曼（RobertAumann）和托马斯·谢林（ThomasSchelling）因对博弈 参与人之间的冲突和合作分析方面的贡献而获奖。2007年，诺贝尔经济学奖颁给莱昂 尼德·赫维奇（LeonidHurwicz）、埃里克·马斯金（EricMaskin）、罗杰·迈尔森 （RogerMyerson），奖励他们对机制设计理论的原创贡献。2012年，劳埃德·夏普利 (LloydShapley）、埃尔文·罗斯（AlvinRoth）因提出稳定配置理论和市场设计实践而 获得诺贝尔奖。在所有这些贡献之前，肯尼斯·阿罗（KennethArrow）已凭借社会选 择理论这一杰出工作获得1972年诺贝尔奖，他早在1950年代已开展这方面的研究。显 然，到现在，博弈论和机制设计已主导社会科学领域几十年。可以说，博弈论的发展是 20世纪最杰出的成就之一，因为它表明数学推理可用于研究复杂的人类互动。

lohnvonHeumann OskarMorqenstern KennethArrow ohn Nashj Reinhard Selten William Vickroy Robert Aumann Leonid Hurwicz Roger Myerson pAoll 图1一4博弈论和机制设计领域的传奇人物 [从左到右依次为：约翰·冯·诺依曼，奥斯卡·摩根斯坦，肯尼斯·阿罗，约翰·纳什，约翰·海萨尼，莱 茵哈德·泽尔腾，威廉·维克瑞，托马斯·谢林，罗伯特·奥曼，莱昂尼德·赫维奇，埃里克·马斯金，罗杰·迈 尔森，劳埃德·夏普利，埃尔文·罗斯]

1.2 当前趋势和现代应用

自1990年代以来，两条相关主线使得博弈论成为当今时代问题求解的主要工具。 第一条主线是博弈论与多个学科例如计算机科学、网络科学和其他工程学的交叉领域出 现的理论研究。第二条主线是博弈论在互联网时代自然的和令人信服的应用。当今时 代，博弈论已成为电子商务、互联网广告、社会网络分析和社会网络货币化、无线网 络、智能运输、智能电网以及碳足迹（carbonfootprint）最优化等诸多领域问题求解的 重要工具。我们稍微介绍一下博弈论的当前趋势和现代应用。 口当前趋势 为了说明第一条主线，我们以算法博弈论这个崭新领域为例，它是博弈论与计算机 科学的交叉地带。这条主线的重要性和闪光点体现在下列事实上。2012年，理论计算 机科学领域中的哥德尔奖（GodelPrize）颁发给了算法博弈论领域的六位学者（Elias Koutsoupias,Christos Papadimitriou,Tim Roughgarden,Eva Tardos, Noam Nisan,A- mirRonen）。哥德尔奖提到了三篇论文[3,4,5]，它们是算法博弈论的奠基之作。为了快 速领略该领域的主题，我们简要回顾一下这三篇论文。

的论文中引l人了“无政府主义的代价”（priceofanarchy）思想。无政府主义的代价衡 量自由个体的自私行为对社会最优状态实现的影响程度。特别地，该论文计算出了在 网络没有中央监管者的情形下，网络用户的自私行为造成的效率损失。他们的研究基 于互联网博弈理论模型，他们使用纳什均衡的概念来形式化无政府主义代价这个 概念。 RoughgardenandTardos[4使用无政府主义代价概念来研究大型交通网中的路线 （routing）交通问题。他们使用博弈理论模型漂亮地解释了交通科学中的著名的布雷斯 论（第4章和第5章），并且建立了拥挤网络中的中央最优路线和自私路线之间的关 系。通过这些研究，博弈论已变为路线政策和交通网设计的重要工具。 第三篇获得2012年哥德尔奖的论文为NisanandRonen5]，他们在这篇论文中提 出了一个迷人的新问题领域，即算法机制设计（algorithmicmechanismdesign）。他们 指出了博弈论和机制设计如何用于求解算法问题，在这种情形下，问题的输人数据为 理性且智能个体的私人信息。传统计算机科学假设算法一旦设计好，那么计算机将如 实执行这些算法。然而，如果在算法执行过程中，自利的参与人被迫提供私人信息， 那么提供给算法的这些信息可能为真也可能为假。算法机制设计的主旨正是使得算 法对策略型个体的人为控制行为是稳健的。现在，算法博弈论已成为世界很多重要 计算机科学部门的一个活跃的研究领域。算法博弈论是博弈论诸多研究趋势的一个 代表。 我们现在转而考察第二条主线，它将博弈论推动到问题求解的前沿。这条主线源于 博弈论在互联网时代问题求解中的重要性。 第 章 口现代应用 引 博弈论的现代应用通常涉及互联网，这是因为互联网的自由性质鼓励上网者的策 言 与 略行为。另外，博弈论在社会科学、经济学或商学领域中的现代应用，总是涉及有自 概 身利益且能进行策略行动的个人或组织。尽管这些个人或组织都是理性的，但在进行 览 系统设计时，我们仍可以使用博弈论和机制设计提供的方法。正是这方面的应用使得 博弈论和机制设计走向前台。为了说明博弈论在现代问题求解中的重要性，我们提供 四个例子。 市场匹配 市场匹配问题既传统又现代。匹配（matching）是指将一组资源或个人分配给另一 组资源或个人的过程。相关例子有买卖双方的匹配、资源与任务的匹配、医生与医院的 匹配、求职者与用人单位的匹配、学生与学校的匹配等（参见图1一5）。其中一些匹配 问题有着深远的社会影响，例如肾脏与病人之间的匹配（更一般地，器官供体与受体之 间的匹配）。匹配问题通常分为两类，一类称作婚姻问题（marriageproblem），另一类 是住房配置问题（houseallocationproblem）。在婚姻问题中，市场任何一方的资源对另 一方的资源有自己的偏好。在住房配置问题中，这种偏好是单向的，即仅一方的资源对 另一方的资源有偏好，毕竟没有生命的住房不可能有偏好。在这两类情形下，匹配都要 使个人偏好得到尊重，并且使结果达到最优。

厂公司 公司 简历 公司 简历 市场匹配 学生 机构 （医生、找工作的人） （医院、公司） 图1一5市场匹配 匹配问题的任何解都要满足两个重要要求，一是稳定性（stability），二是激励相容 性（incentivecompatibility）。大致地说，如果对于某个解，我们无法通过重新配置使 它严格变好，那么这个解就是稳定的。对于某个解，如果所有参与人都如实报告自己的 偏好，那么这个解就是激励相容的。在这两个方面，相关学者都用博弈论进行了严格分 析。1960年代以来，博弈论学者在市场匹配领域做出了极大努力和贡献。现实世界已 有市场匹配成功的大量例子，这反映了博弈论在市场匹配领域的胜利。事实上，2012 年诺贝尔经济学奖颁给了劳埃德·夏普利和埃尔文·罗斯，正是因为他们在匹配理论和 匹配市场方面做出了原创性工作。[6] 在现实生活中，市场匹配的很多例子，例如学生与大学的匹配、医生与医院的匹配 等，有着重要的社会意义，它们的匹配使得社会福利最大化。另外一些匹配，例如器官 供体与受体的更好、更快匹配，拯救了很多人的宝贵生命。博弈论和机制设计在保证这 些市场的成功方面，起着重要作用。 赞助搜索拍卖 业模式。当互联网用户搜索关键词时，搜索引擎提供的网页含有成千上万个与关键词相 关的链接，也含有与广告相关的赞助链接。图1一6描述了一种常见情形。 当互联网用户点击了赞助链接时，他们就打开了相关广告客户的网页。在常见的点 击付费（pay-per-click）模式下，广告客户按照它的网页点击量向搜索引擎支付一定费 用。由于互联网用户和关键词都是任意的，搜索引擎面对的问题是将不同广告客户与 （有限的）赞助广告位置进行匹配。另外，搜索引擎也需要确定广告客户对每次点击需 要支付的费用。目前，大多数搜索引擎使用拍卖机制来解决这个问题，这就是所谓的赞 助搜索拍卖（sponsoredsearchauction）。互联网巨头例如谷歌（Google）、微软（Mi- crosoft）、雅虎（Yahoo!）等的相当大的一部分收人来自赞助搜索拍卖。在典型赞助搜 索拍卖中，搜索引擎让广告客户报出他们对自己喜欢的关键词的支付意愿，即当互联网

Google camera About1000. ] Camera-wikipedla,thefoe oncyclopedia Ads en.wiipedia.org/wikuCamera Acisdvietmesthcanestreectyed Nikon Next:Digital rmoring- ww.kconnext.com nocner Ibca Vlsualtrs what canboaccorplishod Digitalcamer-Wikinedia.the free encyclopedle Canon Camera Cemcorders ewicpecin.org/wii/Digital_camer wwr.homieshopl8.coenfcenon_camere Adigta oamars (r dgicam）sa LotPrces.YR Wanty. reconggesonelecrnicmagesensotostoloayr Free Home delvery.Expicre No 31people in Bangejore.Kamataka +Id BuvDiaital Cnmerns Qoline etBestPricesin ndle:Too Retin HoxneShopla wwww.fipkart.com/cameras Samsung Digial Cameras Nkan Camras-SLR:Camera-Camera Accessotles-SonyCamaras wEhHDShootirg.Check Now Images forcaumera-Reportimages Fujilm X-Pro1Camera HighQualityMicro Camera 图1一6搜索引擎上的关键词拍卖 用户点击相应赞助广告位置时广告客户愿意支付的最大钱数。这个支付意愿通常称为每 次点击费用（cost-per-click）。根据广告客户对特定关键词的报价，搜索引擎确定： （1）让哪些广告出现；（2）不同广告出现的顺序；（3）当客户的广告位置被互联网用户 点击时客户需要支付的钱数。广告客户实际支付的钱数取决于他们的报价。决策（1）、 第 （2）和（3）构成了赞助搜索拍卖机制。 搜索引擎通常希望收人最大化，而广告客户希望在给定的预算下实现最大收益。这 章 就构成了博弈，其中搜索引擎和广告客户为博弈参与人。参与人是理性的，因为他们试 引 图使得自已的收益最大化。这促使广告客户在计算最优可能报价之后进行策略型报价。 言与概收 于是，赞助搜索拍卖的设计机制问题变成了博弈设计问题。博弈规则的设计要能使得均 衡解实现既定的明确标准。 览 众包机制 众包（crowdsourcing）是一种近几年兴起的完成工作的方式，它将工作外包给众 多个体完成。具体地说，众包以公开形式向大量不定个体发包，让他们完成既定工作。 最近几年，众包平台涌现，比较出名的有AmazonMechanicalTurk、CrowdCloud、 CrowdFlower、Elance、Innocentive、Taskcn、Topcoder等。通过众包完成的任务通常 有：图像标记、商标图形设计、营销方案的准备、网站设计、为算法交易问题提供有效 率的代码、文件（法律文件、专利等）的分类、语言翻译、回答问题、大区域搜救任 务等。 关于众包，美国国防高级研究计划局（DARPA）曾于2009年做过一项著名实验， 简称红气球挑战赛。实验人员在美国10个秘密地点释放10个红气球（释放地点参见图 1一7），要求参赛队伍尽快找到这些气球。总奖金为40000美元。获奖队伍为麻省理工 学院（MIT）代表队，他们使用的机制如下。首先，招募志愿者（第一层志愿者）组建 队伍，每个队员招募第二层志愿者。第二层志愿者再招募第三层志愿者，以此类推。第 一个发现并报告红气球的志愿者（比如X）将得到2000美元，而招募X的志愿者（比

如Y）将得到1000美元，招募Y的志愿者得到500美元，以此类推。这个机制非常成 功，麻省理工学院代表队在不到10个小时的时间内找到了全部10个红气球。获胜机制 是博弈论和机制设计在现实应用中的一个极好的例子。 滨水公园 波特兰，依勘冈 克里斯蒂安娜，特拉华 格拉斯哥公园 旧金山，加利 联合广场 福尼亚 特斯拉公园 夏洛茨维尔，弗吉尼重 蔡斯综有公园 圣芭芭拉，加利 福尼亚 查帕拉尔公园 李公园 斯科茨代尔，亚利桑那 孟菲斯，田纳西 百年纪念公园 亚特兰大，佐治亚 凯蒂公园 柯林斯大街 迈阿密，佛罗里达 图1—7DARPA挑战赛中10个红气球的释放地点 博奔论与机制设计 一般来说，成功的众包涉及很多问题。这些问题包括：吸引足够多的参与人； 确定激励的形式和额度（现金或实物）；诱使参与人如实报告；保证任务执行的质 量、时效以及成本效果。在设计类似的众包活动时，博弈论和机制设计起着重要 作用。 社会网络分析 当今，社会网络（socialnetworks）已无处不在。社会网络广泛用于信息扩散、电 子商务、搜索等领域。对于基于互联网的活动来说，社会网络分析至关重要，这些基于 互联网的活动有病毒营销、影响力最大化、影响力最小化等。 社会网络分析的常规方法和工具有个缺陷：它们不能描述个体节点的行为（例如 理性和智能性），也不能模拟这些节点之间的策略性互动。博弈论能够弥补这个缺 陷，因为它可以用准确的数学模型模拟自治、智能且理性个体之间的互动，这些个 体构成了社会网络的节点。Jackson[7]以及EasleyandKleinberg1]认为，在预测社 会网络图谱、模拟信息扩散等社会网络分析问题中，应该使用博弈论。例如，在图 1一8所示的社会网络中，我们使用夏普利值找到了四个最有影响力的节点，其中 夏普利值是合作博弈论的一个解概念。8]博弈论为社会网络分析的可伸缩算法 （scalablealgorithms）提供了合适的工具。在社会网络货币化领域，机制设计比较 有用。近年来，基于社会网络的应用大量出现，部分原因就在于博弈论和机制设计 的使用。

图1一8社会网络中有影响力的节点

1.3 本书结构

在前面的讨论中，我们看到博弈论和机制设计在跨学科研究和现代应用领域变得日 益重要。为了更好地理解和欣赏博弈论的价值，有必要学习博弈论和机制设计的基础知 识。这本教材的目的正在于试图满足这个需求。 在深人阅读本书之后，我们希望读者能够使用博弈论和机制设计来模拟、分析和求 解集权或分权设计问题，这些问题通常涉及多个自治个体以理性且智能的方式进行策略 性互动。本书只要求读者熟悉微积分和概率论基本知识。当然，熟悉线性代数、数学分 析和最优化常识，也有助于本书的学习。数学附录（第33章）提供了本书使用的重要 的数学概念和结果。 在博弈论方面，目前已有大量优秀教科书和专著。很多博弈论教材基于社会科学尤 引言与概览 其是经济学。本书的目的是向工程类专业的研究生或高年级本科生提供博弈论和机制设 计的基本内容。 本书内容可以分成三个部分： （1）非合作博弈论（第2章到第13章）； （2）机制设计（第14章到第24章）； （3）合作博奔论（第25章到第31章） 在第1部分（非合作博弈论），我们主要介绍：博弈论的重要概念（例如效用、理 性、智能以及共同知识)；展开型博弈；策略型博弈；优势策略均衡；纯策略纳什均衡； 混合策略纳什均衡；效用理论；两人零和博弈；纳什均衡存在性定理（包括纳什定理）； 纳什均衡的计算；纳什均衡计算的复杂性；贝叶斯博弈。 第2部分（机制设计）的主题是博弈设计。这一部分的主要议题有：机制的构成元 素；社会选择函数及其应用；激励相容的概念；直接机制和间接机制的等价性；吉伯 德一萨特思韦特（Gibbard-Satterwaite）定理与阿罗不可能定理；维克瑞-克拉克-格罗 夫斯（Vickrey-Clarke-Groves，VCG）机制；机制设计的可能结果与不可能结果；拍卖 与收人等价定理；最优拍卖；赞助搜索拍卖案例研究；事后纳什均衡中的机制实施。 第3部分讨论合作博弈论。这一部分的主要内容有：相关策略和相关均衡；纳什议 价理论；特征型联盟博弈；联盟博弈的核；夏普利值；其他解概念；匹配算法。

第32章（结束语）说明了博弈论和机制设计对工程科学研究者的价值。第33章是 数学附录，这一章复习了本书经常使用的概率论、线性代数、线性规划、数学分析和计 算复杂性的重要概念和结果。 本书每一章开篇都辅以启发性的引言，每章结尾是简短总结，并给出了可供读者进 一步学习的参考文献。每一章都配有习题。概念和结果都用例子说明。这些例子精心选 自计算机科学、网络科学、微观经济学等领域，但它们都具有一般性。本书在某些地方 还以人物传记形式介绍了对博弈论和机制设计作出重大贡献的学者。 需要指出，本书受教于也受益于下列优秀教材和专著：Mas-Colell，Whinston，and Green9]; Myerson[1o]; Maschler, Solan, and Zamir[1l]; Nisan, Roughgarden, Tar- dos, and Vazirani[12]; Shoham and Leyton-Brown[13]; Straffin[14]; Osborne[15] Narahari，Garg，Narayanam，andPrakash[16]的专著可以视为本书的先驱。 对于热情的学生和研究者来说，1997年的博弈论经典论文合集[17]必不可少。我们 也推荐读者阅读Maschler，Solan，andZamir[i1]，这是一本近期出版且内容全面的教 科书。 口参考文献 [1]David Easley andJonKleinberg.Networks,Crowds,andMarkets:Reasoning AboutaHighlyConnectedWorld.CambridgeUniversityPress,2010. [2]JohnvonNeumann and OskarMorgenstern.Theory ofGamesandEconomic 博 Behavior.PrincetonUniversityPress,1944. 奔论与机制 [3]E.Koutsoupias and C.Papadimitriou.“Worst-case equilibria”.In:Computer ScienceReview,3(2)(2009),pp.65-69. [4]T. Roughgarden and E. Tardos.“How bad is selfish routing?”In:Journal of 设 ACM，49(2)(2002)，pp.236-259. 计 [5] N.Nisan and A. Ronen.“Algorithmic mechanism design”.In:Games and E- conomicBehavior，35(1-2)(2001),pp.166-196. [6]TheEconomicSciencesPrizeCommittee.StableMatching:Theory,Evidence, andPracticalDesign—TheSverigesRiksbankPrizeinEconomicSciencesinMemory ofAlfredNobel2012:ScienticBackground.Tech.rep.TheNobelFoundation， Stockholm,Sweden,2012. [7]MathewO.Jackson.Socialand EconomicNetworks.PrincetonUniversity Press,Princeton,NJ,USA,2007. [8]Ramasuri Narayanam and Y. Narahari.“A Shapley value approach to discove ringinfluentialnodesinsocialnetworks”.In:IEEETransactionsonAutomationSci enceandEngineering，8(1)(2011),pp.130-147. [9]AndreuMas-Colell,Michael D.Whinston,and JerryR.Green.Microeconomic Theory.Oxford University Press,1995. [10]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard Universi- tyPress,Cambridge,Massachusetts,USA,1997.

[11]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam- bridgeUniversityPress,2013. [12]Noam Nisan,Tim Roughgarden,Eva Tardos,and VijayVazirani(Editors). AlgorithmicGameTheory.CambridgeUniversityPress,2007. [13]YoamShoham andKevinLeyton-Brown.Multiagent Systems:Algorithmic, GameTheoretic,and LogicalFoundations.CambridgeUniversityPress,NewYork， USA,2009,2009. [14]PhilipD.StraffinJr.GameTheory andStrategy.TheMathematical Associa tion of America,1993. [15]MartinJ.Osborne.AnIntroduction to GameTheory.TheMITPress,2003. [16]Y.Narahari,Dinesh Garg,Ramasuri Narayanam,and Hastagiri Prakash. GameTheoreticProblemsinNetworkEconomicsandMechanismDesignSolutions. Springer,London,2009. [17]Harold W.Kuhn (Editor).Classics in Game Theory.Princeton University Press,1997. 引言与概览

第1部分 非合作博弈论

大致地说，非合作博弈（non-cooperativegames）是指个体参与人的行动构成了基 元（primitives）的那些博弈，而合作博弈是指参与人团体的联合行动构成了基元的那 些博弈。在该部分，我们用12章的篇幅（第2章到第13章）研究非合作博弈。 ·在第2章，我们首先介绍了博弈论中的重要概念，例如偏好（preferences）、效 用（utilities）、理性（rationality）、智能（intelligence）以及共同知识（common knowledge）。然后，我们研究了非合作博弈的两种表达方法：展开型（extensiveform representation）（第3章）和策略型（strategicformrepresentation）（第4章）。 ·在第5、6和7章，我们描述了若千不同的解概念：优势策略与优势策略均衡 （dominantstrategyequilibria）（第5章）；纯策略纳什均衡（purestrategyNashequili- brum）（第6章）；混合策略纳什均衡（mixedstrategyNashequilibrum）（第7章）。这 些解概念对于策略型博弈的分析非常重要。在第8章，我们介绍了冯·诺依曼和摩根斯 坦提出的效用理论（utilitytheory），它是博弈论的基石。 ·第9、10、11和12章研究纳什均衡的存在性及其计算。在第9章，我们重点考 察两人零和博弈。在第10章，我们详细讨论了纳什定理，该定理说明有限策略型博弈 存在着混合策略纳什均衡解。第11章考察纳什均衡的计算，第12章讨论纳什均衡计算 的复杂性。 ·在第13章，我们介绍贝叶斯博弈（Bayesiangames），这是伴随不完全信息（in- completeinformation）的博弈。这些博弈在机制设计（本书第2部分）中起着重要 作用。