Algorithmic Mechanism Design With Investment
Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, Paul Milgrom
Econometrica · 2023 · Volume 91 · Issue 6
Abstract
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 itsconfirming negative externalitiesare 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.
Keywords
Combinatorial optimization, Knapsack problem, investment, auctions, approximation, algorithms
Enable JavaScript for citation tools and additional paper interactions.