Strategyproof facility location on a circle with improved approximation ratio
A Randomized $\frac32$-Approximation for Strategic Facility Location on a Circle
Computer Science and Game Theory
Summary
This paper looks at how to fairly choose a spot on a circular path to build one facility so that a group of people, each with their own honest preferences, are served well. The authors study a method that mixes two known ways to pick this spot, ensuring that no one can benefit by lying about their location. They prove this mixed method works better than previous approaches, giving a closer-to-optimal solution for any number of people. They also show that no random method can do much better than their guaranteed performance.
What this means in practice
- •For urban planners: Place public facilities like bus stops or kiosks on circular routes to fairly serve users who may misreport their preferences, improving overall travel cost estimates.
- •For network infrastructure teams: Assign shared network resources positioned on circular topologies to users reporting their needs, reducing total connection delays and preventing gaming of the system.
A theory result. No direct application yet.
Authors
Hau Chan, Jianan Lin, Chenhao Wang
Abstract
We study strategyproof mechanisms for locating a single facility on a circle so as to serve a set of strategic agents under the utilitarian social cost objective. We analyze a simple parity-dependent mechanism that randomizes between the Random Dictator (RD) mechanism and the Proportional Circle Distance (PCD) mechanism. For an odd number \(n\) of agents, this mechanism mixes RD and PCD with equal probability, as originally proposed by Rogowski and Dziubi{ń}ski (IJCAI 2025). For even \(n\), it mixes RD with a random-deletion extension of PCD, in which one agent is removed uniformly at random before PCD is applied to the remaining agents. Our main result shows that this mechanism is strategyproof and achieves an approximation ratio of \(\frac32\) for every \(n\ge 3\). This improves the \(\frac74\) upper bound of Rogowski and Dziubi{ń}ski, which applied only to odd \(n\), and extends the guarantee to even numbers of agents. Finally, we establish a lower bound of \(\frac{11}{10}\) on the approximation ratio of any randomized strategyproof mechanism, improving on the previous lower bound of \(1.0456\) due to Meir (SAGT 2019).