Strategyproof Approximation Mechanisms for Location on Networks

Date Added: Jul 2009
Format: PDF

The authors consider the problem of locating a facility on a network, represented by a graph. A set of strategic agents have different ideal locations for the facility; the cost of an agent is the distance between its ideal location and the facility. A mechanism maps the locations reported by the agents to the location of the facility. Specifically, they are interested in social choice mechanisms that do not utilize payments. They wish to design mechanisms that are strategyproof, in the sense that agents can never benefit by lying, or, even better, group strategyproof, in the sense that a coalition of agents cannot all benefit by lying.