Two-Sided Facility Location Games

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.

client B client A

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

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.