10月11日论文推荐（附下载地址）
论文名：
Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions
会议/年份：2007
作者：
Alvin E. Roth （诺贝尔经济学家）
推荐理由：
诺贝尔经济学家Alvin Roth写的一篇关于Deferred Acceptance Algorithms（延迟决策算法）的历史、理论、应用以及一些开放问题的文章，很有意思。延迟决策算法是Gale和Shapley于1962年提出来的（Shapley也是诺贝尔经济学家）。延迟决策算法在经济学领域尤其是市场决策方面的影响非常大，例如：择校问题和招生问题、以及婚姻择偶问题。论文还给了很多Theorem和证明，包括大牛Knuth等人关于用户兴趣严谨度对可行性解的影响。
在今年数据挖掘顶级国际会议KDD的中Keynote中，这篇文章的作者Roth教授还作了题目为市场设计和计算市场（Market Design and Computerized Marketplaces）的报告，在报告中Roth教授首先介绍了匹配市场的基本概念和他与传统商品市场的区别。之后他针对学校招生和肾脏移植这两个匹配市场的经典例子做了深入的介绍。在学校招生的例子中，Roth教授介绍了稳定匹配这一概念和经典的deferred acceptance算法，并且讨论deferred acceptance算法和现实中常用的immediate acceptance算法有什么区别和优势。在肾脏移植的例子中，由于捐献者和病人之间的许多限制（血型、抗体、及时性等等）以及一些法律和伦理上的问题，人们总希望可以找到尽量长的移植链并且同时进行手术。Roth教授介绍了如何把这个问题建模成计算机科学中经典的旅行商问题（Traveling Salesman Problem）以及该算法如何在现实中帮助肾脏病人[6]。
Roth教授还展望了在信息时代和互联网时代，市场设计将如何与计算机科学结合发展。他提到了Uber，Airbnb，滴滴等新涌现的市场。他特别提到了中国的滴滴——事实上滴滴想要解决的问题正是交通中乘客和司机匹配的问题。笔者认为在信息时代，市场的设计者有了更多数据，对市场的实际情况有更多了解，在设计市场时也有了更多的工具；而参与匹配市场的玩家，无论是学校招生中的学生和学校，肾脏移植中的捐献者和病人，交通中的乘客和司机，也对效率，隐私，安全等有了更多更高的要求。这许多挑战需要计算机科学家和经济学家一起来面对和解决。
Abstract
The deferred acceptance algorithm proposed by Gale and Shapley (1962) has had a profound influence on market design, both directly, by being adapted into practical matching mechanisms, and, indirectly, by raising new theoretical questions. Deferred acceptance algorithms are at the basis of a number of labor market clearinghouses around the world, and have recently been implemented in school choice systems in Boston and New York City.
In addition, the study of markets that have failed in ways that can be fixed with centralized mechanisms has led to a deeper understanding of some of the tasks a marketplace needs to accomplish to perform well. In particular, marketplaces work well when they provide thickness to the market, help it deal with the congestion that thickness can bring, and make it safe for participants to act effectively on their preferences. Centralized clearinghouses organized around the deferred acceptance algorithm can have these properties, and this has sometimes allowed failed markets to be reorganized.
论文下载链接
https://www.aminer.cn/archive/deferred-acceptance-algorithms-history-theory-practice-and-open-questions/53e9b512b7602d9704043cc1
