CAREER: Towards a Predictive Theory of Algorithmic Mechanism Design

传统算法被设计为接受给定的输入并产生最佳的可实现输出。然而，随着现代算法越来越多地影响我们看到的广告、我们约会的人以及我们生活的许多其他方面，他们的意见不再直接提供，而是从战略代理人那里征求。重要的是，这些代理人非常关心所产生的产出，他们将操纵自己的投入，以实现更理想的结果。这些操纵并不是假设的，而是在医疗保健、云计算和在线约会等价值数十亿美元的行业中得到了很好的证明。然而，现代算法可以从利用博弈论的工具成功地与战略代理交互中受益。算法机制设计领域出现在经济学和计算机科学的交叉点上，正是为了应对这一紧迫的挑战。该项目将推动这一快速增长的研究议程。该项目还包含一项教育计划，以开发一门研究生课程来培训未来的研究人员，以及一门本科课程，以培训将部署这些算法的未来工程师。更具体地说，这项提议的首要重点是将现有的广泛理论从描述性扩展到规范性。例如，大量的先前工作成功地描述了为什么简单的机制在与不成熟的设计者的日常交互中无处不在，但还没有为拥有数据和手段的成熟的设计者开出新的机制来进行精细优化。该项目将在三个关键方向上实施这一议程：(A)分析超越传统近似担保的简单收入最大化拍卖；(B)为学习如何随着时间的推移战略性竞标的买家设计新颖的收入最大化拍卖；(C)为激励兼容的加密货币开发基本构件。这三个方向的研究都将利用计算机科学和经济学的广泛工具包，并继续在这些领域之间建立新的联系。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Traditional algorithms are designed to take a given input and produce the best achievable output. However, as modern algorithms increasingly influence ads we see, people we date, and many other aspects of our lives, their input is no longer directly given but instead is solicited from strategic agents. Importantly, these same agents care deeply about the output produced, and they will manipulate their input to achieve more desirable outcomes. These manipulations are not hypothetical, but well-documented in multi-billion-dollar industries like healthcare, cloud computing, and online dating. Modern algorithms can however benefit from utilizing tools from Game Theory to successfully interact with strategic agents. The field of Algorithmic Mechanism Design emerged at the intersection of Economics and Computer Science precisely to tackle this pressing challenge. This project will advance this rapidly-growing research agenda. The project also contains an educational plan to develop a graduate course to train future researchers and an undergraduate course to train future engineers who will deploy these algorithms.More specifically, the overarching focus of this proposal is to extend the vast existing theory from descriptive to prescriptive. For example, extensive prior work successfully describes why simple mechanisms are ubiquitous in daily interactions with unsophisticated designers, but does not yet prescribe novel mechanisms for a sophisticated designer with the data and means to finely optimize. The project will implement this agenda in three key directions: (a) the analysis of simple revenue-maximizing auctions beyond traditional approximation guarantees, (b) the design of novel revenue-maximizing auctions for buyers who learn how to bid strategically over time, and (c) the development of fundamental building blocks for incentive compatible cryptocurrencies. The research in all three directions will draw on broad toolkits from both Computer Science and Economics and continue forging new connections between these fields.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.