Social and Information Sciences Laboratory (SISL) Seminar

Abstract: We consider the problem of locating a single facility on a plane where a set of strategic agents have Euclidean preferences, defined by their private ideal locations. The objective is to design a strategy-proof mechanism without transfers and approximate the optimal social cost. In this setting, it is known that the only strategy-proof, Pareto optimal, anonymous mechanisms are the coordinate-wise median mechanisms, which asks agents for their ideal points locates the facility at the coordinate-wise median of the reported ideal points. We show that aggregate welfare under the coordinate-wise median mechanism is always within a factor of $\sqrt{2}$ of aggregate welfare under the first best. For any fixed number of agents, we show that this bound can be improved and give a closed form solution for the worst case ratio of aggregate welfare under the coordinate-wise median to aggregate welfare under the first best.