Investment Incentives in Truthful Approximation Mechanisms by Akbarpour, Kominers, Li, Li and Milgrom

Computationally intractable optimization problems often allow approximate solutions that are 'close enough' to the optimal solution.  But these approximation algorithms can radically change the incentives to the participants, or not.  Here's a paper on frontier of market design and computer science, from the KIT — Paris — ZEW Workshop on Market Design from June 2022.

Investment Incentives in Truthful Approximation Mechanisms, by Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, and Paul Milgrom.   May 16, 2022

"Abstract: We study investment incentives in truthful mechanisms that allocate resources using approximation algorithms instead of exact optimization. In such mechanisms, the price a bidder pays to acquire resources is generally not equal to the change in other bidders’ welfare—and these externalities skew investment incentives. Some allocation algorithms are arbitrarily close to efficient, but create such perverse investment incentives that their worst-case welfare guarantees fall to zero when bidders can invest before participating in the mechanism. We show that an algorithm’s guarantees in the allocation and investment problems coincide if and only if that algorithm’s “confirming” negative externalities are sufficiently small. Algorithms that exclude confirming negative externalities entirely (XCONE algorithms) thus have the same worst-case performance for the allocation and investment problems."

 

A "confirming" negative externality is an investment that doesn't change the investor's allocation but imposes a negative externality on the market.