"Approximate Mechanism Design Without Money"

Speaker: Ariel Procaccia
Date: Wednesday, 3 December 2008
Time: 12noon
Place: Ross 201

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.

We present a case study in approximate mechanism design without
money. In our basic setting agents are located on the real line and
the mechanism must select the location of a public facility; the cost
of an agent is its distance to the facility. We establish tight upper
and lower bounds for the approximation ratio given by strategyproof
mechanisms without payments, with respect to both deterministic and
randomized mechanisms, under two objective functions: the social cost,
and the maximum cost. We then extend our results in two natural
directions: a domain where two facilities must be located, and a
domain where each agent controls multiple locations.

Joint work with Moshe Tennenholtz.