2026/08/03 by Tomer Ezra
Computer Science · #cs.GT
arxiv created 2026/08/03 · arxiv updated 2026/08/04
We settle the worst-case approximability of residual-surplus maximization in general multidimensional mechanism-design environments. For n agents with arbitrary nonnegative valuations over a finite outcome space, we give a universally truthful and ex-post individually rational mechanism whose expected residual surplus is at least W(N)/Hn, where W(N) is the optimal social welfare and Hn is the n-th harmonic number. This guarantee is worst-case optimal, including its constant, even for a single-item auction with a known i.i.d. prior and under the weaker requirement of Bayesian incentive compatibility. Our result resolves the welfare-approximation aspect of the open question of [Hartline and Roughgarden 2008] on the power of money burning beyond k-unit auctions, as well as an open question of [Ezra et al. 2025] concerning optimal guarantees for broader valuation classes. It also replaces the outcome-dependent O(log|O|) guarantee of [Fotakis et al. 2015] by the tight agent-dependent factor Hn, while strengthening truthfulness in expectation to universal truthfulness. The mechanism is polynomial-time whenever welfare-maximizing VCG is polynomial-time, yielding efficient mechanisms for gross-substitutes and multi-unit valuations and for several natural single-parameter feasibility constraints.