Friday, Nov 13, 2009, 11-12
Room # 3315
Yajun Wang
Microsoft Research Asia

Approximate Mechanism Design for the Facility Game

We consider the facility game where the planner is building facilities
while agents report their locations. The cost of the agents are
measured by the distance from their locations to the closest facility.
Truthful mechanisms, e.g., those mechanisms that no agent can
manipulate to improve its utility, are not socially optimal when the
number of facilities are greater than 1. In this talk, we first give a
linear lower bound of the approximation ratio for the deterministic
mechanisms of the two facility game. Then we show a randomized
mechanism that achieves constant approximation ratio. Previous works
only have constant lower bound and linear upper bound for both
deterministic and randomized mechanisms.

This is a joint work with Pinyan Lu, Yuan Zhou, Zeyuan Zhu