Tighter Bounds for Facility Games

In facility games, public facilities are placed based on the reported locations of the agents. The cost of an agent is measured by the distance from its location to the nearest facility. In this paper, we consider the one dimensional facility games where all locations for agents and the facilities are on the real line.

We study the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location. The social welfare function studied in this paper is the total cost of the agents. We mainly study two extensions of the simplest version as in (Procaccia et. al. 2009): two facilities and multiple locations per agent. In both cases, no lower bound for randomized strategy-proof mechanisms was previously known. We prove the first lower bound of 1.045 for two-facility games and the first lower bound of 1.33 for multiple locations per agent setting. Our later lower bound is obtained by solving a related linear programming problem, and we believe that this new technique of proving lower bounds for randomized mechanisms may find applications in other problems and is of independent interest.

We also improve several approximation bounds in (Procaccia et. al. 2009). In particular, we give a tighter analysis of a randomized mechanism proposed by (Procaccia et. al. 2009). This analysis is quite involved and confirms a conjecture in (Procaccia et. al. 2009). We also give a simple randomized mechanism for the two-facility games with approximation ratio n/2, improving the naive n-2 ratio from the deterministic mechanisms. For deterministic mechanisms for two-facility games, we improve the approximation lower bound to 2 from 1.5.