Algorithmic Mechanism Design With Investment

• 成果类型: Article
• 署名作者: Akbarpour, Mohammad; Kominers, Scott Duke; Li, Kevin Michael; Li, Shengwu; Milgrom, Paul
• 署名单位: Stanford University; Harvard University; Stanford University; Harvard University
• 刊物名称: ECONOMETRICA
• ISSN/ISSBN: 0012-9682
• DOI: 10.3982/ECTA19559
• 发表日期: 2023
• 页码: 1969-2003
• 关键词: COMBINATORIAL; incentives

摘要

We study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment.