CAREER: Towards a Predictive Theory of Algorithmic Mechanism Design

职业：算法机制设计的预测理论

• 批准号: 1942497
• 负责人: Seth Weinberg
• 金额: $ 60.28万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-01-01 至 2024-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942497&HistoricalAwards=false
• 关键词: CAREER; Towards; Predictive; Theory; Algorithmic

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.

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

项目成果

Optimal Mechanism Design for Single-Minded Agents

单心智能体的最优机制设计

• DOI: 10.1145/3391403.3399454
• 发表时间: 2020
• 期刊: Conference on Economics and Computation
• 作者: Devanur, Nikhil R.;Goldner, Kira;Saxena, Raghuvansh R.;Schvartzman, Ariel;Weinberg, S. Matthew
• 通讯作者: Weinberg, S. Matthew

New Query Lower Bounds for Submodular Function MInimization

• DOI: 10.4230/lipics.itcs.2020.64
• 发表时间: 2019-11
• 期刊: ArXiv
• 作者: A. Graur;Tristan Pollner;Vidhya Ramaswamy;S. Weinberg

Optimal Single-Choice Prophet Inequalities from Samples

样本中的最优单选预言不等式

• DOI: 10.4230/lipics.itcs.2020.60
• 发表时间: 2020
• 期刊: Innovations in Theoretical Computer Science
• 作者: Rubinstein, Aviad;Wang, Jack Z.;Weinberg, S. Matthew
• 通讯作者: Weinberg, S. Matthew

Optimal Multi-Dimensional Mechanisms are not Locally-Implementable

最佳多维机制无法在本地实现

• DOI: 10.1145/3490486.3538334
• 发表时间: 2022
• 期刊: ACM Conference on Economics and Computation
• 作者: Weinberg, S. Matthew;Zhou, Zixin
• 通讯作者: Zhou, Zixin

Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence

近似策略证明的锦标赛规则：关于大型操纵集和覆盖一致性

• DOI: 10.4230/lipics.itcs.2020.3
• 发表时间: 2020
• 期刊: Innovations in Theoretical Computer Science
• 作者: Schvartzman, Ariel;Weinberg, S. Matthew;Zlatin, Eitan;Zuo, Albert
• 通讯作者: Zuo, Albert