New paper: Approximation Mechanisms Without Money

The paper Strategyproof Approximation Mechanisms for Location on Networks by Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz was recently uploaded to the arxiv (this is probably Noga Alon‘s first work in AGT.)   This paper continues previous work on Approximate Mechanism Design Without Money by a subset of these authors.  The (amazingly animated) slides from Ariel’s distinguished dissertation talk in AAMAS give an overview of these results.

The Gibbard-Satherswaite impossibility result rules out, in most settings, the possibility of designing incentive compatible mechanisms without money.   Chapter 10 of the Algorithmic Game Theory book is devoted to settings where this is possible, and these papers suggest a new approach for escaping the impossibility, an approach which should not surprise computer scientists: approximation.  While the first paper gives motivation and promise and is technically simple, the new paper is more sophisticated.   Both papers focus on simple variants of facility location but one can certainly think of much future work in this direction in other settings, like the recent one on Sum of us: truthful self-selection by Noga Alon, Felix Fischer, Ariel D. Procaccia, and Moshe Tennenholtz.

Advertisement