译者序
Twenty Lectures on Algorithmic Game Theory
我们该如何理解人的决策和交互，并使计算机程序能够像人一样进行决策和交互？本书所探讨的就是在由人或智能体所组成的系统中，个体是如何决策的；以及这样的系统该如何理解，如何设计。
算法博弈论处于博弈论和计算机的交叉领域。在诸多世界顶尖级学术机构中，均有开设此门课程。它已经成功应用于很多场景，包括搜索关键字竞拍、在线广告、机构选址、网络构建、频谱定价、婚恋匹配、无人机群、竞技游戏等,其中有些已经收获了巨大的商业效益。我们希望此次翻译能够让更多的人了解并喜欢这一学科。
原书是基于作者Tim Roughgarden多年的授课经验而写成的。如果能跟随作者的思路深入研习下去，定会受益匪浅。原书内容概述可见前言，此处不再赘述。
本书的翻译是我在讲授研究生课程“算法博弈论”的过程中，与我的学生李斌和刘凡共同完成的。我主要负责第1~7、11~15及19~20章。李斌主要负责第8~10及16~18章。刘凡对第5~7章进行了协助。全文的检查和修改由我和李斌完成。我们要感谢李凯、董涵、张冬呈、侯光伟、石琪、张永亮、郭宇航进行了读校并给出了宝贵的修改建议。感谢曲熠编辑的邀请和机械工业出版社的支持。
此书涉及博弈论、理论计算机、人工智能领域的诸多知识。我们力求翻译可靠、易读，但由于时间较紧，知识和经验均有限，译文难免存在不足，在此敬请各位学者和读者朋友批评指正，您的任何意见请发送到邮箱haodongpost@gmail.com。
郝 东
2019年12月6日
前 言
Twenty Lectures on Algorithmic Game Theory
在过去的15年里，计算机科学和经济学进行了一场热烈的交互，诞生了一个叫作“算法博弈论”或者“经济与计算科学”的新领域。计算机科学中的诸多核心问题本质上都涉及多个自私个体之间的交互，而经济学和博弈论为这样的问题提供了丰富的推理模型和定义系统。在传统经济学的很多问题上，来自计算机科学的研究又起到了补充作用。例如，计算机科学聚焦于计算复杂性，并且为之提供了整套描述语言；计算机科学对近似边界进行了研究和推广，为不能或不容易找到精确解的问题提供了推理方法；计算机科学还为贝叶斯或平均情况分析提供了替代方法，而这能帮助经济设计问题找到更牢靠的解。
本书源自我在斯坦福大学所讲授的“算法博弈论”课程的讲义。从2004年到2013年，我一共五次讲授这门课程。该课程的目标是利用具有代表性的模型和结论，让学生便捷、容易地进入这个领域。本书的目标、讲授结构和关键点都与我在斯坦福大学的课程一致。出于精简内容的需要，本书没有更详细地展开一些课题，包括贝叶斯机制设计、紧凑型博弈的表示、计算社会选择、竞赛设计、合作博弈、加密货币和网络系统中的动机、市场均衡、预测市场、隐私、信誉系统和社会计算。以上这些问题很多都可以参考其他书目，包括Brandt等（2016）、Hartline（2016）、Nisan等（2007）、Parkes和Seuken（2016）、Shoham和Leyton-Brown（2009），以及Vojnovic′（2016）。
在每章的开头，我会给出该章的简要介绍。在本书的最后，列出了全书的10个主要知识点。除此以外，每章中正文结束后，都会将重点知识总结出来。除了作为简介的第1章以外，全书可分为三部分。第2～10章涵盖关于规则制定的理论，即“机制设计”，除理论介绍外，还讲述了在线广告、无线频谱拍卖和肾脏交换等实际问题。第11～15章介绍的是“无秩序代价”理论，这是关于实际博弈中均衡的近似保证的，例如，由自私且相互竞争的个体组成的大型网络就是这样一个博弈。第16～20章介绍的是关于均衡计算的一些结论，既包括积极的结论，也包括消极的结论。这部分是基于分布式学习算法和以计算效率为核心的算法对均衡进行分析和计算的。第二、三部分可以独立于第一部分单独学习。学习本书第三部分需要具备第13章的基础；另外，学习16.2和16.3节需要12.4节的基础，学习16.4节需要第14章的基础。标星号的章节包含较困难的理论和技术内容，可以选择性阅读。
本书假设读者有一定的数学基础，另外，第4、19、20章需要读者对多项式时间算法和NP完全性有基本了解。本书并不要求读者具备博弈论或经济学的背景，同时，本书也不能代替博弈论或经济学的传统教材。在斯坦福大学，上这门课的学生包括高年级本科生、硕士生和一年级博士生，他们来自不同的专业，包括计算机科学、经济学、电子工程、运筹学和数学等。
在每一章的正文之后，我都简要总结了与其相关的参考文献。课后练习部分可以作为对这一章的回顾或加强。问题部分比较困难，但能带领读者一步步走向新的研究成果。在本书的最后，我还给出了部分习题的提示，有提示的习题都带有“（H）”标记。
我的课堂教学视频已经上传到YouTube，可以在我的个人主页（www.timroug-hgarden.org）上找到链接。除此以外，还有其他几门理论计算机科学课程的讲义和视频，也可以在主页上找到。如果有关于本书内容的问题，可以到论坛（twentylecturesonagt.freeforums.net/）与我及其他读者进行讨论。
我要感谢参加我的课程的斯坦福大学学生，他们提出的问题和建议对我很有益处。感谢我的助教Peerapong Dhangwatnotai、Kostas Kollias、Okke Schrijvers、Mukund Sundararajan和Sergei Vassilvitskii。其中，Kostas和Okke帮助我准备了本书中的部分图示。感谢Yannai Gonczarowski、Warut Suksompong和Inbal Talgam-Cohen，他们对本书的草稿给出了详细的反馈。感谢Lauren Cowles、Michal Feldman、Vasilis Gkatzelis、Weiwei Jiang、Yishay Mansour、Michael Ostrovsky、Shay Palachy和Rakesh Vohra给出的诸多建议。本书封面是由Max Greenleaf Miller设计的。本书的撰写得到了美国国家科学基金会CCF-1215965和CCF-1524062项目的资助。
如果你有任何建议或发现了书中的疏漏之处，请不吝提出，非常感谢。
Tim Roughgarden
2016年6月
于斯坦福大学
![《斯坦福算法博弈论二十讲》[59M]百度网盘|亲测有效|pdf下载](/uploads/s0309/f022f9b207604bd6.jpg)
