Two-Stage Facility Location Games with Strategic Clients and Facilities

1 Introduction

Facility location problems are widely studied in Operations Research, Economics, Mathematics, Theoretical Computer Science, and Artificial Intelligence. In essence, in these problems facilities must be placed in some underlying space to serve a set of clients that also live in that space. Famous applications of this 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. These problems are purely combinatorial optimization problems and can be solved via a rich set of methods. Much more intricate are facility location problems that involve competition, i.e., if the facilities compete for the clients. These settings can no longer be solved via combinatorial optimization and instead, methods from Game Theory are used for modeling and analyzing them.

The first model on competitive facility location is the famous Hotelling-Downs model, first introduced by Hotelling [1929] and later refined by Downs [1957]. Their original interpretations are selling a commodity in the main street of a town, and parties placing themselves in a political left-to-right spectrum, respectively. They assume a one-dimensional market on which clients are uniformly distributed and there are k facility agents that each want to place a single facility on the market. Each facility gets the clients, to which their facility is closest. D¨urr and Thang [2007] introduced Voronoi games on networks, that move the problem onto a graph and assume discrete clients on each node.

The models mentioned above are one-sided, i.e., only the facility agents face a strategic choice while the clients simply patronize their closest facility independently of the choices of other clients. Obviously, realistic client behavior can be more complex than this. For example, 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], Shen and Wang [2017] and Cohen and Peleg [2019] albeit with continuous clients on a line. In their model with limited attraction ranges, clients split their spending capacity uniformly among all facilities that are within a certain distance. In contrast to the Hotelling-Downs model, pure Nash equilibria always exist. In another related variant by Fournier et al. [2020], clients that have multiple facilities in their range choose the nearest facilities. Another natural client behavior is that they 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 want to minimize the total time spent visiting a facility. This models clients that perform load balancing between different facilities. Peters et al. [2018] prove the existence of subgame perfect equilibria for certain tradeoffs of distance and waiting time for two, four and six facilities and they conjecture that equilibria exist for all cases with an even number of facilities for client utility functions that are heavily tilted towards minimizing waiting times. Feldotto et al. [2019] investigated the existence of approximate pure subgame perfect equilibria for Kohlberg's model and their results indicate that 1.08-approximate equilibria exist. The most notable aspect of Kohlberg's model is that it is two-sided, i.e., both facility and client agents act strategically. This implies that the facility agents have to anticipate the client behavior, in particular the client equilibrium. For Kohlberg's model Feldotto et al. [2019] show that this entails the highly nontrivial problem of solving a complex system of equations.

In this paper we present a very general two-sided competitive facility location model that is essentially a combination of the models discussed above. Our model has an underlying host graph with discrete weighted clients on each vertex. The host graph is directed, which allows to model limited attraction ranges, and we have facilities and clients that both face strategic decisions. Most notably, in contrast to Kohlberg's model and despite our model's generality, we provide an efficient algorithm for computing the facilities' loads in a client equilibrium. Hence, facility agents can efficiently anticipate the client behavior and check if a game state is in equilibrium.

1.1 Further RelatedWork

Voronoi games were introduced by Ahn et al. [2004] on a line. For the version on networks by D¨urr and Thang [2007], the authors show that equilibria may not exist and that existence is NP-hard to decide. Also, they investigate the ratio between the social cost of the best and the worst equilibrium state, where the social cost is measured by the total distance of all clients to their selected facilities. With n the number of clients and k the number of facilities, they prove bounds of Ω(√n/k) and O(√kn). While we are not aware of other results on general graphs, there is work for specific graph classes: Mavronicolas et al. [2008] limit their investigation to cycle graphs and characterize the existence of equilibria and bound the Price of Anarchy (PoA) [Koutsoupias and Papadimitriou, 1999] and the Price of Stability (PoS) [Anshelevich et al., 2004] to 94 and 1, respectively. Additionally, there are many closely related variants with two agents: restaurant location games [Prisner, 2011], a variant by Gur et al. [2018], and a multi round version [Teramoto et al., 2006]. Moreover, there are variants played in k-dimensional space: de Berg et al. [2019], Ahn et al. [2004], Boppana et al. [2016]. To the best of our knowledge, there is no variant with strategic clients aiming at minimizing their maximum waiting time.

A concept related to our model are utility systems, as introduced by Vetta [2002]. Agents gain utility by selecting a set of acts, which they choose from a collection of subsets of a groundset. Utility is assigned by a function that takes the selected acts of all agents as an input. Two special types are considered: basic and valid utility systems. For the former, it is shown that pure Nash equilibria (NE) exist. For the latter, no NE existence is shown but the PoA is upper bounded by 2. We show in the supplementary material that our model with load balancing clients is a valid but not a basic utility system.

Covering games [Gairing, 2009] correspond to a one-sided version of our model, i.e., where clients simply distribute their weight uniformly among all facilities in their shopping range. There, pure NE exist and the PoA is upper bounded by 2. More general versions are investigated by Goemans et al. [2006] and Brethouwer et al. [2018] in the form of market sharing games. In these models, k agents choose to serve a subset of n markets. Each market then equally distributes its utility among all agents who serve it. Brethouwer et al. [2018] show a PoA of 2 - 1k for their game.

Recently Schmand et al. [2019] introduced a model which considers an inherent load balancing problem, however, each facility agent can create and choose multiple facilities and each client agent chooses multiple facilities.

For further related models we refer to the excellent surveys by Eiselt et al. [1993] and ReVelle and Eiselt [2005].

1.2 Model and Preliminaries

We consider a game-theoretic model for non-cooperative facility location, called the Two-Sided Facility Location Game (2-FLG), where two types of agents, k facilities and n clients, strategically interact on a given vertex-weighted directed host graph H = (V,E,w), with V = {v1, . . . , vn}, where w : V → N denotes the vertex weight. Every vertex vi ∈ V corresponds to a client with weight w(vi), that can be understood as her spending capacity, and at the same time each vertex is a possible location for setting up a facility for any of the k facility agents F = {f1, . . . , fk}. Any client vi ∈ V considers visiting a facility in her shopping range N(vi), i.e., her direct closed neighborhood N(vi) = {vi} ∪ {z | (vi, z) ∈ E}. Moreover, let w(X) = ∑vi∈X w(vi), for any X ⊆ V , denote the total spending capacity of the client subset X.

In our setting the strategic behavior of the facility and the client agents influences each other. Facility agents select a location to attract as much client weight as possible, whereas clients strategically decide how to distribute their spending capacity among the facilities in their shopping range. More precisely, each facility agent fj ∈ F selects a single location vertex sj ∈ V for setting up her facility, i.e., the strategy space of any facility agent fj ∈ F is V . Let s = (s1, . . . , sk) denote the facility placement profile. And let S = V k denote the set of all possible facility placement profiles. We will sometimes use the notation s = (sj, s-j), where s-j is the vector of strategies of all facilities agents except fj. Given s, we define the attraction range for a facility fj on location sj ∈ V as As(fj) = {sj} ∪ {vi | (vi, sj) ∈ E}. We extend this to sets of facilities F ⊆ F in the natural way, i.e., As(F) = {sj | fj ∈ F} ∪ {vi | (vi, sj) ∈ E, fj ∈ F}. Moreover, let ws(F) = ∑vi∈As(F) w(vi).

We assume that all facilities provide the same service for the same price and arbitrarily many facilities may be colocated on the same location. Each client vi ∈ V strategically decides how to distribute her spending capacity w(vi) among the opened facilities in her shopping range N(vi). For this, let Ns(vi) = {fj | sj ∈ N(vi)} denote the set of facilities in the shopping range of client vi under s.

Let σ : S × V → Rk+ denote the client weight distribution function, where σ(s, vi) is the weight distribution of client vi and σ(s, vi)j is the weight distributed by vi to facility fj. We say that σ is feasible for s, if all clients having at least one facility within their shopping range distribute all their weight to the respective facilities and all other clients distribute nothing. Formally, σ is feasible for s, if for all vi ∈ V we have ∑fj∈Ns σ(s, vi)j = w(vi), if Ns(vi) ̸= ∅, and σ(s, vi)j = 0, for all 1 ≤ j ≤ k, if Ns(vi) = ∅. We use the notation σ = (σi, σ-i) and (σ′i , σ-i) denotes the changed client weight distribution function that is identical to σ except for client vi, which plays σ′ (s, vi) instead of σ(s, vi).

Any state (s, σ) of the 2-FLG is determined by a facility placement profile s and a feasible client weight distribution function σ. A state (s, σ) then yields a facility load ℓj(s, σ) with ℓj(s, σ) = ∑ni=1 σ(s, vi)j for facility agent fj. Hence, ℓj(s, σ) naturally models the total congestion for the service offered by the facility of agent fj induced by σ. A facility agent fj strategically selects a location sj to maximize her induced facility load ℓj(s, σ). We assume that the service quality of facilities, e.g. the waiting time, deteriorates with increasing congestion. Hence, for a client the facility load corresponds to the waiting time at the respective facility.

There are many ways of how clients could distribute their spending capacity. As proof-of-concept we consider the load balancing 2-FLG with load balancing clients, i.e., a natural strategic behavior where client vi strategically selects σ(s, vi) to minimize her maximum waiting time. More precisely, client vi tries to minimize her incurred maximum facility load over all her patronized facilities (if any). More formally, let Pi(s, σ) = {j | σ(s, vi)j > 0} denote the set of facilities patronized by client vi in state (s, σ). Then client vi's incurred maximum facility load in state (s, σ) is defined as Li(s, σ) = maxj∈Pi(s,σ) ℓj(s, σ). We say that σ∗ is a client equilibrium weight distribution, or simply a client equilibrium, if for all vi ∈ V we have that Li(s, (σ∗ i , σ-i)) ≤ Li(s, (σ′i , σ-i)) for all possible weight distributions σ′ (s, vi) of client vi. See Figure 1 for an illustration of the load balancing 2-FLG.

We define the stable states of the 2-FLG as subgame perfect equilibria (SPE), since we inherently have a two-stage game. First, the facility agents select locations for their facilities and then, given this facility placement, the clients strategically distribute their spending capacity among the facilities in their shopping range. A state (s, σ) is in SPE, or stable, if

1. ∀s ∈ S, ∀vi ∈ V : Li(s, σ) ≤ Li(s, (σ′i , σ-i)) for all feasible weight distributions σ′ (s, vi) of client vi.

We say that client vi is covered by s, if Ns(vi) ̸= ∅, and uncovered by s, otherwise. Let C(s) = {vi | vi ∈ V,Ns(vi) ̸= ∅} denote the set of covered clients under facility placement s. We will compare states of the 2-FLG by measuring their social welfare that is defined as the weighted participation rate W(s) = w(C(s)) = ∑vi∈C(s) w(vi), i.e., the total spending capacity of all covered clients. For a host graph H and a number of facility agents k, let OPT(H, k) denote the facility placement profile that maximizes the weighted participation rate W(OPT(H, k)) among all facility placement profiles with k facilities on host graph H.

We measure the inefficiency due to the selfishness of the agents via the Price of Anarchy (PoA) and the Price of Stability (PoS). Let bestSPE(H, k) (resp. worstSPE(H, k)) denote the SPE with the highest (resp. lowest) social welfare among all SPEs for a given host graph H and a facility number k. Moreover, let H be the set of all possible host graphs H. Then the PoA is defined as PoA := maxH∈H,k W(OPT(H, k))/W(worstSPE(H, k)), whereas the PoS is defined as PoS := maxH∈H,k W (OPT(H, k))/W (bestSPE(H, k)).

We study dynamic properties of the 2-FLG. Let an improving move by some (facility or client) agent be a strategy change that improves the agent's utility. A game has the finite improvement property (FIP) if all sequences of improving moves are finite. The FIP is equivalent to the existence of an ordinal potential function [Monderer and Shapley, 1996].

1.3 Our Contribution

We introduce and analyze the 2-FLG, a general model for competitive facility location games, where facility agents and also client agents act strategically. We focus on the load balancing 2-FLG, where clients selfishly try to minimize their maximum waiting times that not only depend on the placement of the facilities but also on the behavior of all other client agents. We show that client equilibria always exist and that all client equilibria are equivalent from the facility agents' point-of-view. Additionally, we provide an efficient algorithm for computing the facility loads in a client equilibrium that enables facility agents to efficiently anticipate the clients' behavior. This is crucial in a two-stage gametheoretic setting. Moreover, since there are only n possible locations for facilities, we can efficiently check if a given state of the load balancing 2-FLG is in SPE. Using a potential function argument, we can show that a SPE always exists.

Finally, we consider the 2-FLG with an arbitrary feasible client weight distribution function. For this broad class of games, we prove that the PoA is upper bounded by 2 and we give an almost tight lower bound of 2 - 1k on the PoA and PoS. This implies an almost tight PoA lower bound for the load balancing 2-FLG. Furthermore, we show that computing a social optimum state for the 2-FLG with an arbitrary feasible client weight distribution function σ is NP-hard for all feasible σ, hence, also for the load balancing 2-FLG.

We refer to Krogmann et al. [2021] for all details which were omitted due to space constraints.

2 Load Balancing Clients

In this section we analyze the load balancing 2-FLG in which we consider not only strategic facilities that try to get patronized by as many clients as possible but we also have selfish clients that strategically distribute their spending capacity to minimize their maximum waiting time for getting serviced. We start with a crucial statement that enables the facility agents to anticipate the clients' behavior.

Theorem 1. For a facility placement profile s, a client equilibrium σ exists and every client equilibrium induces the same facility loads (ℓ1(s, σ), . . . , ℓk(s, σ)).

Proof (Sketch). Consider a client weight distribution σ that minimizes EQ(σ) := ∑ki=1 ℓi(s, σ)2 . This is an equilibrium as a profitable deviation would decrease EQ. Moreover the KKT conditions of the corresponding convex optimization problem are precisely the conditions of a client equilibrium, hence, every equilibrium is an optimal solution of this optimization problem. Also, EQ is strictly convex in the facilities' loads ℓ1(s, σ), . . . , ℓk(s, σ) and the set of feasible solutions is compact and convex. Thus, the facilities' loads are identical in every equilibrium.

Two facility agents sharing a client have equal load if the shared client puts weight on both of them:

Lemma 1. In the load balancing 2-FLG, for a facility placement s, in a client equilibrium σ, if there are two facility agents fp and fq and a client vi with p, q ∈ Pi(s, σ), then ℓp(s, σ) = ℓq(s, σ).

Next, we define a shared client set, which represents a set of facility agents who share weight of the same clients.

Definition 1. For a facility placement profile s, let fp be an agent, σ be a client equilibrium. We define a shared client set of facility agents Sσ(fp), such that (1) fp ∈ Sσ(fp) and (2) For two facility agents fq, fr: If fq ∈ Sσ(fp) and there is a client vi with q, r ∈ Pi(s, σ), then fr ∈ Sσ(fp).

We prove two properties of such a shared client set: First, all facility agents in a shared client set have the same load, and second, a client's weight is either completely inside or completely outside a shared client set in a client equilibrium.

Lemma 2. For a facility placement s in a client equilibrium σ, for every fq, fr ∈ Sσ(fp) we have ℓq(s, σ) = ℓr(s, σ).

The next lemma follows from Definition 1:

Lemma 3. For a facility placement s, in a client equilibrium σ for every client vi and facility agent fp with p ∈ Pi(s, σ) , we have that for every facility agent fr /∈ Sσ(fp) it holds that r /∈ Pi(s, σ).

Algorithm 1: computeUtilities(H = (V, E, w), F, s)

• 5 H′ ← (V, E, w′ ) with w′ (vi) = 0 if vi ∈ As(M) else
• 1 if F = ∅ then return; 2 M ← computeMNS(H, F, s); 3 for fj ∈M do 4 ℓj (s, σ) ← w(As(M)) |M| ; w′ (vi) = w(vi); 6 computeUtilities(H′ ,F \M, s);

Additionally, we show that each facility agent's load can only take a limited number of values.

Lemma 4. For a facility placement profile s, in a client equilibrium σ a facility agent's load can only take a value of the form xy for x ≤ ws(F) and y ≤ k with x, y ∈ N.

Definition 2. For a facility placement profile s, a set of facility agents ∅ ⊂ M ⊆ F is a minimum neighborhood set (MNS) if for all ∅ ⊂ T ⊆ F: w(As(M)) |M| ≤ w(As(T)) |T | . We define the minimum neighborhood ratio (MNR) as ρs := w(As(M)) |M| , with M being a MNS.

We show that a MNS receives the entire weight of all clients within its range and this weight is equally distributed.

Lemma 5. For a facility placement profile s, in a client equilibrium σ, each facility fj ∈ M of a minimum neighborhood set M has a load of exactly ℓj(s, σ) = ρs.

2.1 Facility Loads in Polynomial Time

We present a polynomial-time combinatorial algorithm to compute the loads of the facility agents in a client equilibrium for a given facility placement profile s. As each facility agent only has n possible strategies, this implies that the best responses of facility agents are computable in polynomial time.

Algorithm 1 iteratively determines a MNS M, assigns to each facility in M the MNR and removes the facilities and all client agents in their range from the instance. See Figure 2 for an example of a run of the algorithm.

The key ingredient of Algorithm 1 is the computation of a MNS in Algorithm 2. Here, we first identify the MNR by a reduction to a maximum flow problem. To this end, we construct a graph, where from a common source vertex s demand flows through the clients to the facility agents in their respective ranges and then to a common sink t. See Figure 3 for an example of such a reduction. By using binary search, we find the highest capacity value of the edges from the facility agents to the sink such that the flow can fully utilize all these edges. This capacity value is the value of the MNR ρs. Note that by Lemma 4 the MNR can only attain a limited number of values. After determining the MNR, we identify the facility agents belonging to a MNS M by individually increasing the capacity of the edge to the sink t for each facility agent. Only if this does not increase the maximum flow, a facility agent belongs to M. By reusing the flow for ρs a search for an augmenting path with the increased capacity is sufficient to determine if the flow is increased.

We first prove the correctness of Algorithm 2:

Algorithm 2: computeMNS(H = (V, E, w), F, s)

1 construct directed graph G = (V ′ ,Est ∪ERange); 2 V ′ ← {s, t} ∪ V ∪F; 3 Est ← {(s, vi, w(vi)) | vi ∈ V } ∪ {(fj, t, 0) | fj ∈ F}; 4 ERange ← {(vi, fj, w(vi)) | vi ∈ V, fj ∈ As(vi)}; 5 possibleUtilities ← sorted({x/y | x, y ∈ N , 0 ≤ x ≤ ws(F), 1 ≤ y ≤ k}); 6 for binary search over i ∈ possibleUtilities do 7 ∀fj ∈ F : capacity((fj, t)) ← i; 8 h ←maximum s-t-flow in G; 9 if value(h) = i · k then i too small else i too large; 10 T ← ∅, ρ ← highest i ∈ possibleUtilities below threshold; 11 for fj ∈ F do 12 ∀fp ∈ F : capacity((fp, t)) ← ρ; 13 capacity((fj , t)) ← ∞; 14 start with flow from binary search for i = ρ; 15 if ∄ augmenting path in G then 16 T ← T ∪ {fj};

17 return T;

Theorem 2. For an instance of the load balancing 2-FLG, a facility placement profile s, Algorithm 2 computes a MNS.

Proof. We show that the MNR ρ computed by the algorithm is correct by proving that ρ is a lower and upper bound for ρs. We show that for each set of facility agents T , we get ρ ≤ w(As(T )) |T | . To this end, consider the maximum flow for i = ρ. The value of this flow must be value(h) = kρ, since ρ is below the threshold found by the binary search. As the total capacity of the edges leaving the source s towards vertices vi ∈ As(T) is upper bounded by w(As(T)) and every vertex fp with fp ∈ T is only reachable via vertices vi ∈ As(T ), the total inflow to the vertices fp ∈ T is w(As(T )). Furthermore, the capacity of each edge from a facility vertex to the sink vertex t is exactly ρ, hence each of these edges carries a flow of exactly ρ. Thus, we get |T |ρ ≤ w(As(T)) for every set of facility agents T .

For the upper bound, we show that there is a set T for which ρ ≥ w(As(T)) |T | . We consider the flow at i = ρ + δ, the value immediately above ρ in possibleUtilities. We assume that for each set T, ρ + δ ≤ w(As(T)) |T | . By Lemma 5, there must be a weight distribution σ, such that every facility agent receives ρ+δ load. Thus, setting the flow of every edge (vi, fj) in h to σ(s, vi)j for each vi ∈ V, fj ∈ F results in a flow of (ρ+δ)k. This leads to ρ+δ being below the threshold and, hence, we have a contradiction. Therefore, there must be a set of facility agents T with ρ+δ > w(As(T )) |T | . By Lemma 4, there is no value in between ρ and ρ + δ, which w(As(T )) |T| can attain. Thus, there must be a set T with ρ ≥ w(As(T)) |T | .

It remains to show that the set of facility agents M computed by the algorithm is indeed a MNS. By the feasibility of the total flow of k · ρ for the instance with capacity bounds of ρ, we have have for every set of facility agents T, w(As(T )) |T| ≥ ρ. For every fj /∈M, there exists an augmenting path where the edge (fj, t) has capacity ∞. Hence, there is a total flow strictly larger than k · ρ with flow of exactly ρ through all fq ̸= fj. As the flow through each fi is bounded by w(As(fi)), for every T with fj ∈ T, w(As(T)) |T| > ρ. Therefore, fj does not belong to the MNS.

For every fj ∈ M, the absence of an augmenting path certifies that the flow is constrained by capacity representing the clients' spending capacities. Hence, w(As(T)) |T| = ρ for every T ⊆ M.

With that, we bound the runtime of Algorithm 2.

Lemma 6. Algorithm 2 runs in O(log(ws(F)k)nk(n + k)).

We return to Algorithm 1 and prove correctness and runtime:

Theorem 3. Given a facility placement profile s, Algorithm 1 computes the agent loads for an instance of the load balancing 2-FLG in O(log(ws(F)k)nk2 (n + k)).

Proof. Correctness: By Lemma 5 the utilities determined for the client agents in the MNS M are correct for the given instance. Also by Lemma 5, the client equilibria of F \ M are independent of the facility agents in M and the clients in As(M). Therefore, we can remove M, set the weight of each client vi ∈ As(M) to w(vi) = 0 and proceed recursively.

Runtime: The recursive function is called at most k times because the instance size is decreased by at least one facility agent in each iteration. Apart from the call to Algorithm 2, all computations can be done in constant or linear time. Therefore, the algorithm runs in O(log(ws(F)k)nk2 (n+k)).

Algorithm 2 implicitly computes a client equilibrium.

Corollary 1. A client equilibrium can be constructed by using the flow values on the edges between a client and the facility agents of the MNSs computed during the binary search in Algorithm 2 as the corresponding client weight distribution.

2.2 Existence of Subgame Perfect Equilibria

We show that the load balancing 2-FLG always possesses SPE using a lexicographical potential function. For that, we show that when a facility agent fp changes her strategy, no other facility agent fq's load decreases below fp's new load.

Lemma 7. Let s be a facility placement profile and fp a facility agent with an improving move s′p such that ℓp((s′p , s-p), σ′ ) > ℓp(s, σ), where σ, σ′ are client equilibria. For every facility agent fq with ℓq((s′p , s-p), σ′ ) < ℓq(s, σ), we have that ℓq((s′p , s-p), σ′ ) ≥ ℓp((s′p , s-p), σ′ ). With this lemma, we prove the FIP and, hence, existence of a SPE by a lexicographic potential function argument.

Theorem 4. The load balancing 2-FLG has the FIP.

Proof. Let Φ(s) ∈ Rk be the vector that lists the loads {ℓ1(s, σ), ℓ2(s, σ), . . . , ℓk(s, σ)} in an increasing order.

Let s be a facility placement profile and fp a facility agent with an improving move s′p such that ℓp((s′p , s-p), σ′ ) > ℓp(s, σ), where σ, σ′ are client equilibria. We show that Φ(s′p , s-i) <lex Φ(s). Let Φ(s) be of the form Φ(s) = (φ1, . . . , φα, ℓp(s, σ), φα+1, . . . , φβ, φβ+1, . . . , φk-1), for some α ≤ β ≤ k - 1, such that for every 1 ≤ j ≤ β: φj < ℓp((s′p , s-p), σ′ ) and for every j ≥ β + 1 : φj ≥ ℓp((s′p , s-p), σ′ ).

By Lemma 7, we have for all facility agents fq with a load ℓq(s, σ) ∈ {φ1, . . . , φβ) that their loads did not decrease. and for agents fq with ℓq(s, σ) ∈ {φβ+1, . . . , φk) we have ℓq((s′p , s-p), σ′ ) ≥ ℓp((s′p , s-p), σ′ ). With the improvement of fp, Φ(s′p , s-p) >lex Φ(s) holds. By Lemma 4, there is a finite set of values that the loads can attain, thus, Φ is an ordinal potential function and the game has the FIP.

3 Arbitrary Client Behavior

In the following, we investigate the quality of stable states of the 2-FLG with arbitrary client behavior, i.e., the client costs are arbitrarily defined, and provide an upper and lower bound for the PoA as well as a lower bound for the PoS. Additionally, we show that computing the social optimum is NP-hard.

Theorem 5. The PoA of the 2-FLG is at most 2.

Proof. Fix a 2-FLG with k facility players. Let OPT be a facility placement profile that maximizes social welfare and let (SPE, σSPE) be a SPE. Let C(SPE) be the set of clients vi which are covered in SPE and C(OPT) be the set of clients vi which are covered in OPT, respectively. Let UNCOV = C(OPT) \ C(SPE) be the set of clients which are covered in OPT but uncovered in SPE.

Assume that W(OPT) > 2W(SPE) and hence, ∑v∈UNCOV w(v) > W(SPE). Then, there exists a facility player fp that receives in OPT more than W(SPE) k load from the clients in UNCOV. Now consider a facility agent fq with load ℓq (SPE, σSPE) ≤ W(SPE) k . By changing her strategy and selecting the position of facility agent fp in OPT, agent fq receives the weight of all clients in UNCOV which are covered by fp in OPT since they are currently uncovered and therefore, obtains more than W(SPE) k load. As this contradicts the assumption of (SPE, σSPE) being a SPE, we have that W(OPT) ≤ 2W(SPE).

We contrast the upper bound of the PoA with a lower bound for the PoA and PoS.

Theorem 6. The PoA and PoS of the 2-FLG is at least 2- 1k .

Proof. We prove the statement by providing an example of an instance I which has a unique equilibrium. Let x ≥ 4, x ∈ N. We construct a 2-FLG with k facility players, a host graph H(V,E,w) with V = {v1, . . . , vk, v1,1, . . . , v1,x-1, v2,1, . . . , vk-1,x-1, vk,1, . . . , vk,kx}, for all v ∈ V , w(v) = 1 and E = {(vi, vi,j) | i ∈ [1, k-1], j ∈ [1, x-1]} ∪{(vk, vk,i) | i ∈ [1, kx]} ∪ {(vk,i, vi,1) | i ∈ [1, k - 1]}. See Figure 4.

We note that H consists of a large star Sk with central vertex vk, leaf vertices (vk,1, . . . , vk,kx) and k - 1 small stars Si for i ∈ [1, k - 1] with central vertices vi and leaf vertices (vi,1, . . . , vi,x-1). Each star Si is connected to Sk via an edge between a leaf vertex of Sk and Si, i.e., (vk,i, vi,1).

If the k facility players are placed on sOPT = (v1, . . . , vk), all clients are covered by exactly one facility. Hence, W(OP T (H, k)) = |V | = kx + k + (k - 1)(x - 1).

In any equilibrium, a facility fj for j ∈ [1, k] must receive a load of at least kx+1 k = x+ 1k as otherwise switching to vertex vk with kx + 1 adjacent vertices yields an improvement. However, any other vertex in H has at most x - 1 adjacent vertices, hence, every facility player gets a load of at most x. Therefore, the unique SPE is sSPE = (vk, . . . , vk) with W(sSPE) = kx + 1 and P oA = P oS = kx+k+(k-1)(x-1) kx+1 = (2k-1)x+1 kx+1 . We get lim ( (2k-1)x+1 kx+1 ) = 2k-1 k = 2- 1k .

By a reduction from 3SAT, we show that computing OPT(H, k) is an NP-hard problem.

Theorem 7. Given a host graph H and a number of k facilities, computing the facility placement maximizing the weighted participation rate OPT(H, k), is NP-hard.

4 Conclusion and FutureWork

We provide a general model for non-cooperative facility location with both strategic facilities and clients. Our load balancing 2-FLG is a proof-of-concept that even in this more intricate setting it is possible to efficiently compute and check client equilibria. Also, in contrast to classical one-sided models and in contrast to Kohlberg's two-sided model, the loadbalancing 2-FLG has the favorable property that stable states always exist and that they can be found via improving response dynamics. Moreover, our bounds on the PoA and the PoS show that the broad class of 2-FLGs is very well-behaved since the societal impact of selfishness is limited.

The load balancing 2-FLG is only one possible realistic instance of a competitive facility location model with strategic clients; other objective functions are conceivable, e.g., depending on the distance and the load of all facilities in their shopping range. Also, besides the weighted participation rate other natural choices for the social welfare function are possible, e.g., the total facility variety of the clients, i.e., for each client, we count the facilities in her shopping range. This measures how many shopping options the clients have. Moreover, we are not aware that the total facility variety has been considered for any other competitive facility location model.