Strategic Facility Location with Clients That Minimize Total Waiting Time

Simon Krogmann, Pascal Lenzner, Alexander SkopalikAAAI 2023 · DOI

Introduction

Traditional facility location models, such as the Hotelling-Downs model, typically assume that customers are passive agents who simply visit the nearest available facility. However, in many real-world scenarios—from choosing a grocery store to selecting a server in a distributed network—customers act strategically. If the closest option is overcrowded, a rational client might choose a slightly more distant but less congested alternative to minimize their total waiting time.

This paper introduces the Two-Sided Facility Location Game (2-FLG), a model that captures this dual strategic behavior. In this game, facilities compete for market share (client load), while clients strategically distribute their "purchasing power" across all reachable facilities to minimize their individual congestion costs.

The Two-Sided Facility Location Game

The 2-FLG is structured as a two-stage game played on a graph.

  1. Facility Stage: Facilities (the players) choose their locations on the graph nodes to maximize the total load they receive from clients.
  2. Client Stage: Each client, located at a node with a specific weight (purchasing power), can reach any facility within a predefined "shopping range." Clients split their weight among these reachable facilities to minimize their total waiting time, which is defined as the sum of the loads of the facilities they use, weighted by the amount of business they send to each.
Figure 4: Illustration of client weight distribution between one (left) and two (right) facilities. Clients split their power (pie charts) to minimize total waiting time, affecting the final load of the facilities.

As shown in Figure 4, the introduction of a second facility ($v_2$) causes clients to redistribute their weight. The resulting loads ($f_1, f_2$) and the total waiting time $L_1$ are determined by this strategic balancing act. The researchers prove that for any fixed set of facility locations, a unique client equilibrium always exists and can be calculated in polynomial time.

Computational Complexity and Stability

Despite the predictable nature of client behavior, the overall game is highly unstable for facilities. The researchers analyzed the existence and computation of a Subgame Perfect Equilibrium (SPE)—a state where no facility wants to move and no client wants to redistribute their weight.

Facility Instability

The authors prove that an SPE does not always exist. Furthermore, determining whether a given instance has an SPE is NP-hard, and finding an equilibrium in a simplified "Uniform" version of the game is PLS-complete.

Figure 5: A sequence of facility moves on a path graph. The numbers represent facility loads, showing how facilities move to capture more weight, which can lead to cycles rather than a stable equilibrium.

Figure 5 illustrates this dynamic: as facilities move to improve their individual loads (e.g., from a load of 7 to 8), they trigger a redistribution of client weight, which may then incentivize the other facility to move again. This "cat-and-mouse" behavior can prevent the system from ever reaching a stable state.

Approximation and Practical Solutions

Given the hardness of finding exact equilibria, the authors propose a practical alternative: the 3-approximate SPE. They demonstrate that by using a simplified "proxy" game—where clients simply split their weight equally among all reachable facilities—one can efficiently find a configuration where no facility can improve its load by more than a factor of 3 by moving. This suggests that even if facilities use simplified rules of thumb to guess customer behavior, they can still reach a relatively stable state.

Conclusion

The 2-FLG model provides a more realistic framework for facility location by accounting for client sensitivity to congestion. While the strategic nature of clients introduces significant computational challenges and potential instability for businesses, the existence of efficient approximation algorithms offers a path forward for making near-optimal strategic decisions in complex competitive environments. Future work aims to tighten the approximation bounds and explore more complex, non-linear waiting time functions.

Summary updated

BibTeX
@inproceedings{krogmann2023strategic,
  author = {Simon Krogmann and Pascal Lenzner and Alexander Skopalik},
  title = {{Strategic Facility Location with Clients That Minimize Total Waiting Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25709},
}
Figure