Algorithmic Mechanism Design with Investment

Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem, but guarantee only 0% when accounting for investment incentives. An algorithm’s allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. In the opening talk from the Simons Institute’s recent workshop on Online and Matching-Based Market Design, Paul Milgrom (Stanford) introduced fast approximation algorithms for the knapsack problem that have no confirming negative externalities, and guarantee close to 100% for both allocation and investment.