Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Money Burning Mechanism Design: From Welfare to Surplus
event speaker icon
Tomer Ezra (Tel-Aviv University)
event date icon
Wednesday, 18.11.2026, 13:00
event location icon
Taub 201

We study mechanism design with the objective of maximizing consumer surplus. Payments are a standard tool for incentivizing truthful behavior. When maximizing social welfare, these payments are simply transfers from consumers to the auctioneer and therefore do not reduce the overall welfare. But what happens when monetary transfers are unavailable or undesirable? For example, when allocating medical appointments, we may not want to charge patients, yet asking them to wait in line also imposes a cost. Unlike money transferred to an auctioneer, the time spent waiting is lost. Such costs act as payments that are effectively burned, and our objective becomes the total value participants receive minus these costs, known as consumer surplus.

Hartline and Roughgarden [STOC 2008] initiated the algorithmic study of such money-burning mechanisms. For allocating a single good among n participants, they presented a truthful mechanism whose expected consumer surplus approximates the optimal welfare within an O(log n) factor. They also showed that a logarithmic loss is unavoidable.

We extend this line of research to general multidimensional settings, where participants can have complex preferences over many possible outcomes. We present black-box reductions that turn welfare-maximization algorithms, as well as existing truthful welfare-approximation mechanisms, into truthful mechanisms for consumer-surplus maximization with only an additional O(log n) loss. In particular, we show that the worst-case loss from money burning is the same in general multidimensional settings as in a single-item auction: neither the number of goods nor the complexity of participants’ preferences increases this loss. Our mechanisms achieve this optimal guarantee without any knowledge of participants’ value distributions, yet no better guarantee is possible even for a single item with values drawn independently from a known common distribution.

Based on: https://arxiv.org/abs/2608.01693