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.