Approximate mechanism design without money

TLDR

Algorithmic mechanism design has traditionally focused on game‑theoretic optimization problems where standard money‑based mechanisms fail, leading to the development of truthful approximation mechanisms that rely on payments—a trend that contrasts with earlier work where payments were ubiquitous and approximation was a necessary compromise to address computational complexity. In this paper, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We argue that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments.

Abstract

The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on enforcing payments. In this paper, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We argue that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are ubiquitous, and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity.