# Equilibria in Two-Stage Facility Location with Atomic Clients

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 5 Mar 2024.

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

- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [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)
- [Hedonic Diversity Games](https://mlsanity.com/paper/1903.00303/) (2019)
- [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)
- [Strategy Proof Mechanisms for Facility Location with Capacity Limits](https://mlsanity.com/paper/2009.07986/) (2020)
- [Strategic Facility Location with Clients that Minimize Total Waiting Time](https://mlsanity.com/paper/2211.14016/) (2022)
- [Heterogeneous Facility Location with Limited Resources](https://mlsanity.com/paper/2105.02712/) (2021)
- [On Discrete Truthful Heterogeneous Two-Facility Location](https://mlsanity.com/paper/2109.04234/) (2021)
- [Strategic Resource Selection with Homophilic Agents](https://mlsanity.com/paper/2305.00843/) (2023)
- [General distribution of consumers in pure Hotelling games](https://mlsanity.com/paper/1602.04851/) (2016)

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

- [The Bakers and Millers Game with Restricted Locations](https://mlsanity.com/paper/2501.05334/) (2025)

## Abstract (arXiv)

We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of 2 on the price of anarchy which implies high social welfare of equilibria, if they exist.