Mechanism Design for Facility Location Games Under a Prelocated Facility
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to place a new facility near an existing one when people live on a line or circle and want to minimize their travel distance. Each person knows their own location but doesn’t share it truthfully, so the authors design methods (mechanisms) that encourage honesty. They create different strategies depending on whether people are all on one side of the existing facility or on both sides, aiming to reduce either the worst travel distance or the total travel distance. Their work includes both exact limitations on how well these methods can perform and practical mechanisms that achieve close approximations while ensuring truthfulness.
facility locationstrategy-proof mechanismmaximum costsocial costapproximation ratiodeterministic mechanismrandomized mechanismprivate informationreal linecircle
Authors
Genjie Qin, Qizhi Fang, Wenjing Liu
Abstract
We study the problem of locating a new homogeneous facility under a prelocated facility. Here, a set of $n$ agents is located on a real line or a circle, each of whom has her location as private information, and her cost is the (expected) distance from her location to the nearest facility. Our goal is to design mechanisms which can approximately minimize the maximum cost or the social cost while eliciting agents' private information truthfully (i.e., strategy-proof). Based on real-life scenarios, we consider the problem in two settings: the general setting where each agent can be located at both sides of the prelocated facility, and the special setting where all the agents are located at the same side of the prelocated facility. For agents on a line, in the general setting, we design the best possible deterministic strategy-proof mechanism with $2$-approximation and provide a lower bound of $1.5-ε\textbf{ }(ε>0)$ for any randomized strategy-proof mechanism under the maximum cost objective. For the social cost, we obtain an upper bound of $n$ for deterministic strategy-proof mechanisms and lower bounds of $1.5$ and $1.0425$ for any deterministic strategy-proof mechanism and any randomized strategy-proof mechanism, respectively. In the special setting, we further provide a randomized strategy-proof $5/3$-approximation mechanism for the maximum cost and a deterministic strategy-proof $(n-1)$-approximation mechanism for the social cost. For agents on a circle, we provide a deterministic strategy-proof 2-approximation mechanism under the maximum cost objective.