Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location
2026-08-17 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study ways to place multiple facilities on a line to serve agents who report their positions, aiming for fairness and no cheating without using money. They build on a known method for two facilities and create a new mechanism for three facilities called Random-Anchor Volume, which picks one agent randomly and then chooses others based on spacing, ensuring people have no incentive to lie. This method gives a solution close to the best possible in terms of total travel cost. They also extend this idea to more facilities, but while the method keeps being fair up to three facilities, it can be manipulated when there are four or more.
strategyproofnessfacility locationsocial costapproximation ratiorandomized mechanismsincentive compatibilityreal lineagent reportsmechanism designmanipulability
Authors
Haris Aziz, Simon Mackenzie, Mashbat Suzuki
Abstract
We study the strategyproof placement of \(k\) facilities on the real line for \(n\) agents who privately report their locations, without monetary transfers. For two facilities, the Proportional Mechanism of Lu, Sun, Wang, and Zhu (2010) is strategyproof in expectation and achieves a constant-factor approximation to the optimal social cost. Whether such a guarantee is possible for three facilities in the standard model, where each agent is served by her nearest open facility, has remained open. We resolve this question affirmatively by introducing the \emph{Random-Anchor Volume} mechanism. The mechanism first opens a facility at the report of a uniformly random agent, called the \emph{anchor}, and then jointly selects two additional reports, assigning each pair probability proportional to the product of the two consecutive gaps formed by the pair and the anchor. We prove that the mechanism is strategyproof in expectation and has expected social cost at most \(8 OPT_3\), where \(OPT_k\) denotes the minimum social cost achievable using at most \(k\) facilities. The mechanism naturally extends to every \(k\geq 2\) by selecting \(k-1\) additional reports with probability proportional to the product of the consecutive gaps among them and the anchor. Under truthful reporting, this generalization has expected social cost at most \(4(k-1)OPT_k\). Its incentive guarantee, however, has a sharp boundary: the mechanism is strategyproof in expectation for \(k\in\{1,2,3\}\), but is manipulable for every \(k\geq 4\).