pith. sign in

arxiv: 2604.16829 · v1 · submitted 2026-04-18 · 💻 cs.GT

Strategic Facility Location with Limited Liars

Yue Gruszecki , Elliot Anshelevich This is my paper

Pith reviewed 2026-05-10 07:30 UTC · model grok-4.3

classification 💻 cs.GT
keywords strategic facility locationNash equilibriumprice of anarchylimited liarsmetric spacestrong equilibriumline metricsprice of stability
0
0 comments X

The pith

With a limited number of strategic clients who may lie about their locations, Nash equilibria in facility location always exist and stay within a factor of (n+2k)/(n-2k) of the optimal total distance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines strategic facility location where n clients in a metric space select a facility to minimize the sum of distances, but k of them may misreport their positions if it reduces their individual cost. It establishes that Nash equilibria exist for any metric space with a price of stability near 1, and that every such equilibrium costs at most (n+2k)/(n-2k) times the optimum, a bound shown to be nearly tight. A sympathetic reader cares because the result indicates that complete strategyproofness is unnecessary when only a bounded fraction of participants can manipulate. The work also shows that strong equilibria, which may fail to exist in general, always exist on line metrics with the improved ratio (n+k)/(n-k).

Core claim

In strategic facility location games with n clients and k strategic liars in an arbitrary metric space, Nash equilibrium always exists and every Nash equilibrium is within a factor of at most (n+2k)/(n-2k) from the optimum solution, with the bound nearly tight. While strong equilibrium may not exist in general, it always exists for line metrics with cost at most (n+k)/(n-k) times the optimum.

What carries the argument

The ratio bound derived from how individual beneficial lies by the k strategic clients shift the chosen facility under the sum-of-distances objective.

Load-bearing premise

Strategic clients lie exactly when doing so reduces their personal distance to the facility that is selected based on the reported locations.

What would settle it

An explicit set of client positions in a metric space together with a Nash equilibrium whose total reported cost exceeds (n+2k)/(n-2k) times the true optimum cost would falsify the bound.

Figures

Figures reproduced from arXiv: 2604.16829 by Elliot Anshelevich, Yue Gruszecki.

Figure 1
Figure 1. Figure 1: Plots of the approximation ratio w.r.t. k/n under the worst case NE (for general metrics) or SNE (for line metrics). The solid line shows the upper bound for POA w.r.t. k/n while the dashed line shows the upper bound for SPOA w.r.t. k/n. 1Note that results are much better for strategyproof mechanisms if facilities can be placed anywhere in the space, instead of only at a finite set of locations. For exampl… view at source ↗
Figure 2
Figure 2. Figure 2: An instance of facility location problem where the price of stability bound is almost tight [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An instance of the facility location problem where there are two facility locations [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An instance of a facility location problem with graph metric. There are three facility [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A lower bound instance for SPoS and SPoA. [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A lower bound instance for SPoS and SPoA. [PITH_FULL_IMAGE:figures/full_fig_p023_6.png] view at source ↗
read the original abstract

We study Nash equilibria in strategic facility location games where clients are located in an arbitrary metric space. Specifically, there are $n$ clients, and the goal is to choose a facility from a set of given locations, so that the total distance from the clients to the facility is as small as possible. While some of the clients are always truthful, $k$ of them are strategic, and will lie about their location if it benefits them. We quantify how the fraction of strategic clients affects the existence and quality of Nash equilibrium and strong equilibrium solutions, and note that even for relatively large $k$, the properties of these solutions can be much better than the results of fully strategyproof mechanisms. For Nash equilibrium, we show that it always exists, and the price of stability is very close to 1. More importantly, we prove that all Nash equilibria are within a factor of at most $\frac{n+2k}{n-2k}$ from the optimum solution, and that this price of anarchy bound is almost tight. While strong equilibrium may not exist for this setting, we prove that it always exists for line metrics, and its cost is at most $\frac{n+k}{n-k}$ times that of optimum.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies a facility location problem in arbitrary metric spaces with n clients, where k are strategic and may misreport locations to reduce their individual connection costs. The facility is placed at a location minimizing the reported sum of distances. The authors claim that Nash equilibria always exist with price of stability close to 1, that every Nash equilibrium has cost at most (n+2k)/(n-2k) times the optimum (and that this PoA bound is nearly tight), and that while strong equilibria need not exist in general, they do exist on line metrics with cost at most (n+k)/(n-k) times optimum.

Significance. If the stated existence and approximation results hold, the work demonstrates that the presence of a limited number of strategic liars does not substantially degrade equilibrium quality relative to the social optimum, and that the resulting bounds are substantially better than those achievable by fully strategyproof mechanisms. The near-tight PoA for Nash equilibria and the stronger guarantee for strong equilibria on lines are concrete, falsifiable contributions that advance the understanding of partial strategic behavior in metric facility location.

minor comments (3)
  1. The abstract states that the PoA bound is 'almost tight' but does not exhibit the matching lower-bound construction; including a brief description or reference to the tightness example in the main text would strengthen the claim.
  2. The model description should explicitly state the tie-breaking rule used when multiple locations minimize the reported total distance, as this choice can affect the set of equilibria.
  3. The price of stability is described only qualitatively as 'very close to 1'; an explicit bound (even if trivial) would make the statement precise.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper and for recommending minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives existence of Nash equilibria, a PoA bound of (n+2k)/(n-2k) that is almost tight, and a strong-equilibrium bound of (n+k)/(n-k) on line metrics directly from the standard definitions of unilateral and coalitional deviation incentives in the reporting game. Clients are partitioned into truthful and strategic subsets; the facility is chosen to minimize the reported sum-of-distances; bounds follow from charging arguments that compare equilibrium cost to optimum without any fitted parameters, self-referential definitions, or load-bearing self-citations. All steps remain independent of the target results and rely only on metric properties and individual rationality, rendering the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The analysis rests on standard game-theoretic equilibrium concepts and metric space properties without introducing new entities, fitted parameters, or ad-hoc axioms beyond the model definition.

axioms (3)
  • domain assumption Clients located in an arbitrary metric space
    Stated directly in the abstract as the setting for client locations.
  • domain assumption Strategic clients lie about location if it benefits them
    Core modeling assumption for the k liars.
  • standard math Nash equilibrium and strong equilibrium as standard solution concepts
    Invoked for existence and quality analysis.

pith-pipeline@v0.9.0 · 5510 in / 1424 out tokens · 56231 ms · 2026-05-10T07:30:59.394024+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Strategyproof ap- proximation mechanisms for location on networks.arXiv preprint arXiv:0907.2049, 2009

    Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof ap- proximation mechanisms for location on networks.arXiv preprint arXiv:0907.2049, 2009

    work page arXiv 2049

  2. [2]

    Strategyproof ap- proximation of the minimax on networks.Mathematics of Operations Research, 35(3):513–526, 2010

    Noga Alon, Michal Feldman, Ariel D Procaccia, and Moshe Tennenholtz. Strategyproof ap- proximation of the minimax on networks.Mathematics of Operations Research, 35(3):513–526, 2010

    work page 2010

  3. [3]

    Procaccia, and Moshe Tennenholtz

    Greg Aloupis, Mordecai Ben-Or, Shiri Chechik, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. Improved approximation ratio for strategyproof facility location on a cycle. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), volume 6484 ofLecture Notes in Computer Science, pages 379–390. Springer, 2010

    work page 2010

  4. [4]

    Strong price of anarchy.Games and Economic Behavior, 65(2):289–317, 2009

    Nir Andelman, Michal Feldman, and Yishay Mansour. Strong price of anarchy.Games and Economic Behavior, 65(2):289–317, 2009

    work page 2009

  5. [5]

    Randomized social choice functions under metric prefer- ences.Journal of Artificial Intelligence Research, 58(1):797–827, 2017

    Elliot Anshelevich and John Postl. Randomized social choice functions under metric prefer- ences.Journal of Artificial Intelligence Research, 58(1):797–827, 2017

    work page 2017

  6. [6]

    Lee, and Toby Walsh

    Haris Aziz, Alexander Lam, Barton E. Lee, and Toby Walsh. Proportionality-based fairness and strategyproofness in the facility location problem.Journal of Mathematical Economics, 119:103129, 2025

    work page 2025

  7. [7]

    Randomized strategic facility location with predictions.Advances in Neural Information Processing Systems (NeurIPS), 37:35639–35664, 2024

    Eric Balkanski, Vasilis Gkatzelis, and Golnoosh Shahkarami. Randomized strategic facility location with predictions.Advances in Neural Information Processing Systems (NeurIPS), 37:35639–35664, 2024

    work page 2024

  8. [8]

    Sincerevoting, strategicvoting: Alaboratoryexperimentusingalternativeproportional systems

    Antoinette Baujard, Herrade Igersheim, Frédéric Gavrel, Jean-François Laslier, and Isabelle Lebon. Sincerevoting, strategicvoting: Alaboratoryexperimentusingalternativeproportional systems. In John Aldrich, André Blais, and Laura B. Stephenson, editors,The Many Faces of Strategic Voting, chapter 10, pages 203–231. The University of Michigan Press, 2018. 24

    work page 2018

  9. [9]

    Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship.Mathematical Programming, 203(1):901–930, 2024

    Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, and Zihan Tan. Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship.Mathematical Programming, 203(1):901–930, 2024

    work page 2024

  10. [10]

    Mechanism design for facility location problems: A survey

    Hau Chan, Aris Filos-Ratsikas, Bo Li, Minming Li, and Chenhao Wang. Mechanism design for facility location problems: A survey. In Zhi-Hua Zhou, editor,Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 4356–4365. Interna- tional Joint Conferences on Artificial Intelligence Organization, 8 2021

    work page 2021

  11. [11]

    Strong equilibrium in cost sharing con- nection games.Games and Economic Behavior, 67(1):51–68, 2009

    Amir Epstein, Michal Feldman, and Yishay Mansour. Strong equilibrium in cost sharing con- nection games.Games and Economic Behavior, 67(1):51–68, 2009

    work page 2009

  12. [12]

    On voting and facility location

    Michal Feldman, Amos Fiat, and Iddan Golomb. On voting and facility location. InProceedings of the 2016 ACM Conference on Economics and Computation, EC’16, page269–286, NewYork, NY, USA, 2016. Association for Computing Machinery

    work page 2016

  13. [13]

    Voudouris, and Rongsen Zhang

    Aris Filos-Ratsikas, Panagiotis Kanellopoulos, Alexandros A. Voudouris, and Rongsen Zhang. The distortion of distributed facility location.Artificial Intelligence, 328:104066, 2024

    work page 2024

  14. [14]

    Approximation guarantees of median mechanism inRd

    Nikolai Gravin and Jianhao Jia. Approximation guarantees of median mechanism inRd. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 495–506, 2025

    work page 2025

  15. [15]

    Sincere versus sophisticated voting in congress: Theory and evidence.The Journal of Politics, 72(1):60–73, 2010

    Tim Groseclose and Jeffrey Milyo. Sincere versus sophisticated voting in congress: Theory and evidence.The Journal of Politics, 72(1):60–73, 2010

    work page 2010

  16. [16]

    Proportional fairness in obnoxious facility location

    Alexander Lam, Haris Aziz, Bo Li, Fahimeh Ramezani, and Toby Walsh. Proportional fairness in obnoxious facility location. InProceedings of the 23rd International Conference on Au- tonomous Agents and Multiagent Systems, AAMAS ’24, page 1075–1083, Richland, SC, 2024. International Foundation for Autonomous Agents and Multiagent Systems

    work page 2024

  17. [17]

    Leveling the playing field: Sincere and sophisticated players in the boston mechanism.American Economic Review, 98(4):1636–1652, 2008

    Parag A Pathak and Tayfun Sönmez. Leveling the playing field: Sincere and sophisticated players in the boston mechanism.American Economic Review, 98(4):1636–1652, 2008

    work page 2008

  18. [18]

    Approximate mechanism design without money

    Ariel D Procaccia and Moshe Tennenholtz. Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC), 1(4):1–26, 2013

    work page 2013

  19. [19]

    Strategy-proof location on a network.Journal of Economic Theory, 104(2):405–428, 2002

    James Schummer and Rakesh V Vohra. Strategy-proof location on a network.Journal of Economic Theory, 104(2):405–428, 2002

    work page 2002

  20. [20]

    Strategyproof facility location with limited locations.Journal of the Operations Research Society of China, 11(3):553–567, 2023

    Zhong-Zheng Tang, Chen-Hao Wang, Meng-Qi Zhang, and Ying-Chao Zhao. Strategyproof facility location with limited locations.Journal of the Operations Research Society of China, 11(3):553–567, 2023

    work page 2023

  21. [21]

    Strategy proof mechanisms for facility location at limited locations

    Toby Walsh. Strategy proof mechanisms for facility location at limited locations. InPRICAI 2021: Trends in Artificial Intelligence: 18th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2021, Hanoi, Vietnam, November 8–12, 2021, Proceedings, Part I 18, pages 113–124, Cham, 2021. Springer. 25

    work page 2021