Facility location (competitive game)

The competitive facility location game is a kind of competitive game in which service-providers select locations to place their facilities in order to maximize their profits.^[1]^[2]^{: 502–506} The game has the following components:

There are several consumers who need a certain service, e.g, electricity connection.
There are several producers that can supply this service, e.g, electricity companies.
Each producer can build its facility (e.g, a power station) in one of several locations.
For every pair of consumer (C) and location (L), there is a fixed cost of serving C from L (e.g, depending on the distance between the power station and the consumer's house). This cost is denoted Cost[C,L].

The game is a sequential game with three steps:

Each producer selects a location for placing its facility.
Each producer set a price for each user (price discrimination is allowed, since there is a different cost for serving different consumers).
Each consumer selects a facility to connect to.

Each consumer has a certain private value for accepting the service.

For each consumer-producer pair:

The gain of the consumer for connecting to the producer's facility is his value minus the price;
The gain of the producer is the price minus the cost of serving the consumer;
The social welfare of this pair is the sum of the gains, i.e, the consumer's value minus the service cost.

Equilibrium

We analyze the game using backward induction.

Step 3 is simple: each consumer just selects the cheapest facility.

Step 2 is also quite simple. Suppose a producer P has its facility in location L. Then, the price it takes from consumer C must be at least Cost[C,L]. Suppose the locations are ordered in increasing order of the cost, i.e, the locations are L1, L2, ... such that Cost[C,L1]<Cost[C,L2]<... Then, the producer whose facility in location L1 can always win the consumer by offering him the price Cost[C,L2]. This is because the producer whose facility is L2 cannot offer a lower price. Therefore, in step 2 each producer sets the price to consumer C according to the cost of the next-cheapest producer.

Step 1 - the facility-location step - is more challenging to analyze (this is why the game is named after this step). It is possible to prove that this is a potential game (The potential is the total social-welfare; when a new producer enters the game, the increase in social-welfare exactly equals the producer's profit).^[2]^{: 503–504} Therefore, this step has a pure, Nash equilibrium, and the entire game has a pure subgame perfect equilibrium.

Moreover, every maximum-welfare outcome is also a maximum-potential outcome, so it must also be a Nash equilibrium. This means that the price of stability is 1.

The facility-location game may have other pure Nash equilibria, in which the social welfare is not maximal. However, it is possible to prove that the social welfare in such equilibria is at least half the optimum. Therefore, the price of anarchy is at most 2.^[2]^{: 505–506}

Moreover, it is possible to show that the price-of-anarchy is at most 2 even when the game does not converge to equilibrium. Consider a random sequence of best-response moves. If the length of the sequence is $O(n\cdot \ln(1/\epsilon ))$ , then the social welfare after the sequence is at least $1/2-\epsilon$ times the optimum. This latter result is true in much more general class of games, called utility games.^[3]^[4]

References

^ Vetta, A. (2002). "Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. p. 416. doi:10.1109/SFCS.2002.1181966. ISBN 0-7695-1822-2.
^ ^a ^b ^c Eva Tardos and Tom Wexler, "Network Formation Games". Chapter 19 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
^ Mirrokni, Vahab S.; Vetta, Adrian (2004). "Convergence Issues in Competitive Games". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 3122. p. 183. doi:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.
^ Goemans, M.; Mirrokni, V.; Vetta, A. (2005). "Sink Equilibria and Convergence". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). p. 142. doi:10.1109/SFCS.2005.68. ISBN 0-7695-2468-0.

[vetta-1] Vetta, A. (2002). "Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. p. 416. doi:10.1109/SFCS.2002.1181966. ISBN 0-7695-1822-2.

[agt-2] Eva Tardos and Tom Wexler, "Network Formation Games". Chapter 19 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[3] Mirrokni, Vahab S.; Vetta, Adrian (2004). "Convergence Issues in Competitive Games". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 3122. p. 183. doi:10.1007/978-3-540-27821-4_17. ISBN 978-3-540-22894-3.

[4] Goemans, M.; Mirrokni, V.; Vetta, A. (2005). "Sink Equilibria and Convergence". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). p. 142. doi:10.1109/SFCS.2005.68. ISBN 0-7695-2468-0.

[1]

[2]

[3]

[4]

Facility location (competitive game)

Equilibrium

See also

References