Optimal Prior-Free Mechanisms for Consumer Surplus

Abstract

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)/H_n$, where $W(N)$ is the optimal social welfare and $H_n$ 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|\mathcal{O}|)$ guarantee of [Fotakis et al. 2015] by the tight agent-dependent factor $H_n$, 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.