Two-facility Location Games with Minimum Distance Requirement

Xinping Xu, Bo Li, Minming Li, Lingjie Duan

In the field of algorithmic game theory, facility location games explore how a central planner can optimally place resources—such as schools, hospitals, or power plants—when the agents using them might misreport their locations to gain a personal advantage. A recent study published in the Journal of Artificial Intelligence Research introduces a significant real-world constraint to this model: the minimum distance requirement ($d$).

This constraint reflects practical necessities, such as social distancing requirements for public health sites or safety buffers between industrial facilities. The authors provide the first comprehensive analysis of two-facility location games under this constraint, designing strategyproof mechanisms across various preference models.

Problem Formulation

Traditional mechanism design for facility location assumes facilities can be placed anywhere on a line. However, real-world constraints often dictate a minimum separation. The challenge is to design a mechanism—a function that maps reported agent locations to facility locations—that satisfies two primary criteria:

  1. Strategyproofness (SP): No single agent can achieve a better outcome (lower cost or higher utility) by reporting a false location.
  2. Efficiency: The outcome should minimize the "approximation ratio," which measures the gap between the mechanism's performance and the theoretical social optimum.

Methodology

The research categorizes the problem into five distinct "Games" based on facility types and agent preferences:

  • Facility Type: Facilities are either Heterogeneous (distinct types, like a school and a library) or Homogeneous (identical types, like two bus stops).
  • Agent Preference: Preferences can be Favorable (agents want to be close), Obnoxious (agents want to be far away), or Triple-Preference (agents may have positive, negative, or neutral feelings toward different facilities).

For each scenario, the authors propose specific algorithms and utilize mathematical induction and case analysis to prove strategyproofness and establish bounds on approximation ratios.

Key Results and Insights

The study reveals that the minimum distance constraint significantly impacts the feasibility of efficient, strategyproof mechanisms. A major finding is the "Distance Tax": for identical favorable facilities, the authors prove that no deterministic strategyproof mechanism can maintain a bounded approximation ratio for social cost. In this case, the constraint makes the system fundamentally vulnerable to manipulation.

Conversely, for heterogeneous favorable facilities, the authors demonstrate that strategyproofness is achievable by selecting the "leftmost" optimal solution (Mechanism 1), resulting in a perfect approximation ratio of 1.

Summary of approximation ratios (Upper Bounds and Lower Bounds) for the five games studied.

As shown in the table above, the results vary significantly across the five games:

  • Game 1 (Favorable, Heterogeneous): Achieved an optimal ratio of 1.
  • Game 2 (Favorable, Homogeneous): Proved the ratio is unbounded ($\infty$).
  • Game 3 (Obnoxious, Heterogeneous): Developed a mechanism with a ratio between 1 and 2.
  • Game 4 (Obnoxious, Homogeneous): Achieved an approximation ratio of 9.
  • Game 5 (Triple Preference): Designed a group strategyproof mechanism with an approximation ratio of 4.

Conclusion and Future Directions

While this work provides a rigorous foundation for two-facility games on a 1D line, it also highlights several avenues for future research. The current proofs are specific to two facilities; extending these results to $k$ facilities introduces significant combinatorial complexity. Additionally, moving from a 1D line to 2D planes or complex networks would better reflect urban environments. Finally, the authors suggest that exploring randomized mechanisms—where outcomes are determined by probability—might yield better approximation ratios than the deterministic rules focused on in this study.

Summary updated

Abstract

We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous, we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous, we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indifferent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4.
BibTeX
@article{xu2021two,
  author = {Xinping Xu and Bo Li and Minming Li and Lingjie Duan},
  title = {{Two-facility Location Games with Minimum Distance Requirement}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.12319},
}
Figure