# Strategic Facility Location with Clients that Minimize Total Waiting Time

arXiv: https://arxiv.org/abs/2211.14016 · HTML: https://mlsanity.com/paper/2211.14016/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 25 Nov 2022.

## Builds on (most cited first, 12 of 12)

- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [On Voting and Facility Location](https://mlsanity.com/paper/1512.05868/) (2015)
- [Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives](https://mlsanity.com/paper/1911.09813/) (2019)
- [Two-Stage Facility Location Games with Strategic Clients and Facilities](https://mlsanity.com/paper/2105.01425/) (2021)
- [Hotelling-Downs Model with Limited Attraction](https://mlsanity.com/paper/1611.05959/) (2016)
- [From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation](https://mlsanity.com/paper/1903.04265/) (2019)
- [Hotelling Games with Random Tolerance Intervals](https://mlsanity.com/paper/1909.11558/) (2019)
- [Voronoi Choice Games](https://mlsanity.com/paper/1604.07084/) (2016)
- [On One-Round Discrete Voronoi Games](https://mlsanity.com/paper/1902.09234/) (2019)
- [Spatial competition with unit-demand functions](https://mlsanity.com/paper/2001.11422/) (2020)
- [Equilibrium Computation in Resource Allocation Games](https://mlsanity.com/paper/1612.00190/) (2016)
- [Strategyproof Facility Location in Perturbation Stable Instances](https://mlsanity.com/paper/2107.11977/) (2021)

## Built on by (most cited first, 3 of 3)

- [Strategic Resource Selection with Homophilic Agents](https://mlsanity.com/paper/2305.00843/) (2023)
- [Equilibria in Two-Stage Facility Location with Atomic Clients](https://mlsanity.com/paper/2403.03114/) (2024)
- [The Bakers and Millers Game with Restricted Locations](https://mlsanity.com/paper/2501.05334/) (2025)

## Abstract (arXiv)

We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.