Algorithmic Mechanism Design With Investment, by Akbarpour, Kominers, Li, Li, and Milgrom,

 Mechanisms that are computationally complex may require approximation in implementation, which can change the incentive properties of the exact mechanism.   But progress can be made...

Algorithmic Mechanism Design With Investment, by Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, Paul Milgrom, Econometrica, First published: 07 December 2023, https://doi.org/10.3982/ECTA19559

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 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.

From the introduction:

"Approximation algorithms can be combined with pricing rules to produce truthful mechanisms, provided that the algorithm is “monotone” (Lavi, Mu'Alem, and Nisan (2003)). In this paper, we study the ex ante investment incentives created by such mechanisms.

"Suppose that one bidder can make a costly investment to change its value before participating in a truthful mechanism. As an initial result, we show that all truthful mechanisms using the same allocation algorithm entail the same investment incentives, so we can regard the investment incentives as properties of the algorithm itself.

"If an allocation algorithm exactly maximizes total welfare, then the corresponding truthful mechanism is a Vickrey–Clarke–Groves (VCG) mechanism. For VCG mechanisms, any single bidder's investment is profitable if and only it improves total welfare (Rogerson (1992)). In this respect, the VCG mechanisms are essentially unique. We find that a truthful mechanism aligns a bidder's investment incentives with welfare maximization only if there is some set of allocations such that, for generic valuation profiles, its allocation algorithm exactly maximizes welfare over that set. Many practical approximation algorithms do not have this structure and, as a result, lack efficient investment incentives.

"One might also hope that if an allocation algorithm approximately maximizes total welfare, then it generates approximately efficient investment incentives—but we show to the contrary that arbitrarily good approximations can have arbitrarily bad investment guarantees. To make this statement precise, we evaluate an algorithm's performance on any particular instance by the welfare it achieves divided by the maximum welfare. We refer to the worst-case ratio over all instances when values are exogenous as the allocative guarantee, and the worst-case ratio when one bidder's ex ante investment endogenously determines its value as the investment guarantee.1 (The investment guarantee measures welfare net of investment costs.)

"Because the investment guarantee is a worst case over instances and over investment technologies, it is never more than the allocative guarantee. We characterize the algorithms for which the allocative and investment guarantees are equal, and apply those results to evaluate and improve upon standard approximation algorithms."