Optimal Prior-Free Mechanisms for Consumer Surplus
2026-08-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a problem in mechanism design where multiple agents have values for different outcomes, and the goal is to maximize leftover value after payments, called residual surplus. They provide a truthful and fair mechanism that guarantees a residual surplus close to the best possible social welfare divided by the harmonic number of agents, which is shown to be the best possible in the worst case. Their result answers previous open questions and improves on earlier work by giving tighter guarantees that depend on the number of agents rather than the number of outcomes. The method is also efficient to run in many cases when standard welfare optimization is efficient.
mechanism designresidual surplustruthful mechanismindividual rationalitysocial welfareharmonic numberBayesian incentive compatibilityVCG mechanismgross substitutesmulti-unit auctions
Authors
Tomer Ezra
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.