---
title: "Two-Sided Facility Location Games"
authors:
  - "Simon Krogmann"
doi: "10.24963/ijcai.2024/963"
url: "https://ijcai.org/proceedings/2024/963"
pdf: "https://ijcai.org/proceedings/2024/0963.pdf"
venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence"
year: 2024
pages: "8496-8497"
track: "Doctoral Consortium"
keywords:
  - "DC: Game Theory and Economic Paradigms"
---

# Two-Sided Facility Location Games

Simon Krogmann

*Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 8496-8497. DOI: [10.24963/ijcai.2024/963](https://doi.org/10.24963/ijcai.2024/963)

## Abstract

Facility location problems have been studied in settings like hospital placement or the competition between stores.
In some cases, a central authority coordinates facility placements to optimize metrics like the coverage of an area or emergency response time.
In many cases, however, facilities are placed by multiple rational agents to maximize their utility, e.g., the number of clients they attract.
In previous research, these games feature simplistic client behavior independent of other clients' strategic choices, e.g., visiting the closest facility.
Our goal is to understand what happens if clients also act selfishly, resulting in a two-stage game consisting of strategic facility and client agents.

In three recent publications, we investigated such two-stage models for clients that optimize their waiting times.
We showed the existence and gave algorithms for (approximate) subgame perfect equilibria, a common extension of Nash equilibria for sequential games.
To learn more about this domain, we intend to investigate further natural client behaviors and eventually create a more general model or hierarchy of two-sided facility location games.
With this, we aim to make predictions in real-world settings, e.g., the placement of renewable energy infrastructure.

## Full text

## 1 Introduction

Facility location problems are widely studied in Operations Research, Economics, Mathematics, Theoretical Computer Science, and Artificial Intelligence. In these problems, facilities must be placed in some underlying space to serve a set of clients living in that space. Prominent applications are the placement of hospitals in rural areas to minimize the emergency response time or the deployment of wireless Internet access points to maximize the offered bandwidth to users, and recently vaccination centers, to enable easy access for the population. More intricate are facility location problems that involve competition, e.g., in the case where the facilities compete for the clients, which require methods from Algorithmic Game Theory for modeling and analyzing them.

![Image](https://ijcai.org/proceedings/2024/fulltext/963/image_000000_b45d922ac79d04807d88cc9c812a5be62714ae7d8643eeb865c69f85cb298579.png)

client B client A

Figure 1: Facility location games, with facilities (dots) and client visits (red arrows). Left: A one-sided game, in which client utility is based on distance. In a one-sided game, changing a client's strategy will not influence the other client's behavior. Right: A two-sided game in which a client visits the emptiest store within a distance of 2. If client A decides to change the store she visits, client B can improve her utility by changing to the now unvisited store.

![Image](https://ijcai.org/proceedings/2024/fulltext/963/image_000001_fe047fac40391b0a9b49a354a723053ab00428772448a82e88846a0237e7fdf3.png)

## 1.1 Competitive LocationModels

The first model on competitive facility location is the famous Hotelling-Downs model, introduced by Hotelling [1929] and refined by Downs [1957]. Their original interpretations are selling a commodity in the main street of a town, and political parties on a left-to-right spectrum, respectively. They assume a one-dimensional market on which clients are uniformly distributed and facility agents each place a single facility on the market. Each facility gets the clients to which their facility is closest. However, not every market is a one-dimensional line and clients are not always a continuous mass. To address this, D¨urr and Nguyen [2007] introduced Voronoi games that move the problem onto a graph and assume discrete clients on each node. Facility agents place a facility on any node of the graph and compete for clients that patronize the facility closest to them. This graph can be interpreted as a city with the facilities as competing supermarkets or gas stations.

Obviously, realistic client behavior can be more complex, e.g., a client might choose not to patronize any facility, if there is no facility sufficiently close to her. This setting was recently studied by Feldman et al. [2016] albeit with a continuous client mass on a line.

## 1.2 Two-Stage Facility Location

The models mentioned in the previous section are one-sided, i.e., only the facility agents face a strategic choice while the clients simply patronize the closest facility independently of the other clients' choices. Departing from this one-sidedness, clients might avoid crowded facilities to reduce waiting times. This notion was introduced to the Hotelling-Downs model by Kohlberg [1983], also on a line. Clients consider a linear combination of both distance and waiting time, as they

![Image](https://ijcai.org/proceedings/2024/fulltext/963/image_000002_d833a44882d78d1c47d2e397f03fa1457dd548e92621c99510bd0e492280dd52.png)

2

1

0

1

2

Figure 2: An instance of our load balancing two-stage facility location game published at IJCAI 2021. The clients (vertices) split their weight (numbers) among the facilities (colored dots) within a distance of one to minimize their maximum incurred facility load. The client distributions are shown by colored pie charts. Left: The blue facility receives a load of 2 and all others a load of 43 . The left client distributes weight 43 to the yellow facility and 13 each to red and green. The state is not in subgame perfect equilibrium (SPE) as red can improve her load to 3 2 by co-locating with blue (Right).

aim to minimize the total facility visiting time. This models clients that load-balance between different facilities.

Models that incorporate waiting time are inherently twosided, as there are two games played in sequence, affecting each other. After the facilities have chosen their locations (facility game), the clients play a second game, competing for short waiting times with the other clients (client game) under the given facility locations. This is in contrast to the one-sided models in which a client does not care about the other clients' actions, arguably making it a passive actor. In Figure 1, we compare one- and two-sided facility location models.

## 2 Previous Work

My first paper on this topic [Krogmann et al., 2021] introduces a two-stage facility location game, in which clients minimize their waiting time while considering only facilities within a given distance. We argue that this is realistic because clients have access to an increasing amount of information to aid their decision-making, e.g., facility loads by the time of the day as provided by Google Maps [D'Zmura, 2020]. This model, illustrated in Figure 2, somewhat surprisingly does admit equilibria in all instances. Moreover, we prove an upper bound of 2 on the price of anarchy showing that the societal impact of selfishness in contrast to central planning is limited. However, the question of how quickly an equilibrium can be reached by following best responses remains open.

In a recent follow-up paper [Krogmann et al., 2023], we investigate a related model with clients optimizing their sum of completion times instead of aiming for the earliest possible completion. Even though client equilibria are still unique and efficiently computable, this behavior prevents SPE from existing in all instances. This is quite surprising because we changed the model only slightly. To mitigate the SPE nonexistence, we developed an algorithm to efficiently compute approximate SPE, which we showed to exist for all instances. A third paper [Krogmann et al., 2024] will appear at IJCAI this year and features a two-sided improving response dynamic to find SPE for atomic clients. As such it is an algorithm that truly uses the two-state nature of the game.

## 3 Objectives

In this project, we plan to thoroughly investigate two-stage facility location games and, in particular, how the strategic

0

behavior of the client and the facility agents influences each other, with the following objectives:

- Create algorithms for efficiently computing best response strategies and equilibria.
- Analyze the quality of equilibria via the price of anarchy and the price of stability.
- Explore real-world applications.

Our plan is to not just have results for a small list of specific models but to fully understand the problem space by either creating a dichotomy for properties like the existence of equilibria, or a class hierarchy. This would enable practitioners to transfer our results to their models.

## 4 Outlook

We are currently working on expanding our knowledge of our previous variants of two-sided facility location games, while also looking at new variants. In addition to being interesting models on their own, we hope that this helps us to reach more general insights to achieve dichotomy results. Furthermore, we are in the process of identifying specific real-world applications of our models and talking to experts to verify our assumptions, mostly in the renewable energy sector. We also plan to look at the influence of human behavior in contrast to purely rational agents, since some of our envisioned applications feature humans while others feature algorithmic agents.

## References

1. [Downs, 1957] Anthony Downs. An Economic Theory of Political Action in a Democracy. Journal of Political Economy, 65(2):135-150, 1957.
2. [Dürr and Nguyen, 2007] Christoph Dürr and Kim Thang Nguyen. Nash equilibria in voronoi games on graphs. In ESA, pages 17-28, 2007.
3. [D'Zmura, 2020] Matt D'Zmura. Behind the scenes: popular times and live busyness information, 2020.
4. [Feldman et al., 2016] Michal Feldman, Amos Fiat, and Svetlana Obraztsova. Variations on the Hotelling-Downs Model. In AAAI, pages 496-501, 2016.
5. [Hotelling, 1929] Harold Hotelling. Stability in Competi- tion. The Economic Journal, 39(153):41-57, 1929.
6. [Kohlberg, 1983] Elon Kohlberg. Equilibrium Store Loca- tions When Consumers Minimize Travel Time Plus Wait- ing Time. Economics Letters, 11(3):211 -216, 1983.
7. [Krogmann et al., 2021] Simon Krogmann, Pascal Lenzner, Louise Molitor, and Alexander Skopalik. Two-stage facil- ity location games with strategic clients and facilities. In IJCAI, pages 292-298, 2021.
8. [Krogmann et al., 2023] Simon Krogmann, Pascal Lenzner, and Alexander Skopalik. Strategic facility location with clients that minimize total waiting time. In AAAI, vol- ume 37, pages 5714-5721, 2023.
9. [Krogmann et al., 2024] Simon Krogmann, Pascal Lenzner, Alexander Skopalik, Marc Uetz, and Marnix C. Vos. Equi- libria in two-stage facility location with atomic clients. In IJCAI, 2024.