Breaking the 4-Approximation Barrier in Strategyproof Two-Facility Location
2026-08-10 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly place two facilities on a map so that people have the shortest possible travel times, where people can't lie about their location to get a better spot. Previously, the best known method to do this had a guarantee that was 4 times the optimal total travel distance, and the worst-case guarantee no one could beat was about 1.045. The authors create a new approach that combines two different methods and improves the guarantee to about 3.667 in many types of spaces, including normal Euclidean spaces. They also show a better proof that no method can do better than about 1.207, improving the previous lower limit.
strategyproof mechanism designtwo-facility location problemrandomized mechanismsapproximation ratiometric spacesPtolemaic metric spaceProportional mechanismGlobal Pair mechanismsocial cost minimizationlower bound
Authors
Mengfan Ma, Bo Peng
Abstract
We study strategyproof mechanism design without transfers for the two-facility location problem in metric spaces. A mechanism selects two facility locations based on agents' reported locations; each agent incurs her distance to the nearer facility, and the objective is to minimize the expected social cost. A mechanism is strategyproof if no agent ever benefits from misreporting her location. The best approximation ratio achieved by a randomized strategyproof mechanism has been $4$, attained by the Proportional mechanism of Lu, Sun, Wang, and Zhu (EC 2010), and the best lower bound has been $1.045$, due to Lu, Wang, and Zhou (WINE 2009). Neither bound has moved since then, even on the line $\mathbb{R}$. We improve both bounds. Our main result is a randomized strategyproof mechanism with approximation ratio $11/3 \approx 3.667$ on every Ptolemaic metric space, a rich class containing all Euclidean spaces. The mechanism randomizes between the Proportional mechanism and a new mechanism that we call Global Pair. Global Pair draws an unordered pair of agents with probability proportional to their distance and opens facilities at their reported locations. Although Global Pair and Proportional each have approximation ratio $4$, the two mechanisms attain their worst-case approximation ratios on complementary instances. Randomizing between them balances these complementary weaknesses and breaks the $4$-approximation barrier. On the lower-bound side, we construct a new two-profile instance that yields a lower bound of $(1+\sqrt{2})/2 \approx 1.207$, improving upon the previous lower bound of $1.045$.