Two-Sided Facility Location Games

Simon KrogmannIJCAI 2024

Introduction

Traditional facility location models, such as the classic Hotelling-Downs model, typically treat clients as passive actors who simply patronize the nearest facility. However, in modern contexts—aided by real-time data like Google Maps' "popular times"—clients are strategic. They balance travel distance against congestion. This paper explores "two-sided" facility location games where both facilities and clients act strategically to optimize their respective outcomes.

The Two-Stage Game Model

The research utilizes Algorithmic Game Theory to model these interactions as two-stage sequential games. In the first stage, facilities choose locations on a graph to maximize their total load (number of customers). In the second stage, clients distribute themselves among available facilities to minimize their individual costs, which include both distance and waiting time.

Strategic client distribution: clients A and B choose facilities based on proximity and potential congestion.

This shift from passive to strategic clients fundamentally changes system stability. As shown in the figure above, a change in one client's choice can trigger a chain reaction, requiring a more sophisticated analysis of equilibrium states.

Stability and Equilibrium

The focus of this work is finding Subgame Perfect Equilibria (SPE), where every player's strategy is optimal at every stage. A key insight is the sensitivity of stability to client objectives. For instance, when clients aim to minimize their maximum waiting time, equilibria are guaranteed to exist. Conversely, if the goal is to minimize the sum of completion times, a stable equilibrium may not be reachable.

Load-balancing dynamics across a network, illustrating how clients (colored dots) are distributed to manage facility loads.

As illustrated in the network dynamics above, the author developed specific "two-sided improving response dynamics" for atomic clients to navigate these configurations and find stable states.

Efficiency and the Price of Anarchy

To measure the impact of selfish behavior, the paper employs the Price of Anarchy (PoA) metric. This compares the efficiency of a decentralized, selfish outcome to a centrally planned optimal solution. The research establishes a theoretical upper bound of 2 for the PoA in specific load-balancing models, suggesting that the loss of efficiency due to individual selfishness is bounded and manageable.

Conclusion and Future Directions

While the current theoretical framework is robust, several avenues for future research remain. There is a need for a comprehensive hierarchy of games to understand which client behaviors lead to stability. Furthermore, the author plans to validate these models against real-world data, particularly in the context of renewable energy infrastructure placement, and to explore how heuristic-based human behavior differs from pure mathematical rationality.

Summary updated

BibTeX
@inproceedings{krogmann2024two,
  author = {Simon Krogmann},
  title = {{Two-Sided Facility Location Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure