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. The game has the following components:
The game is a sequential game with three steps:
  1. Each producer selects a location for placing its facility.
  2. Each producer set a price for each user.
  3. Each consumer selects a facility to connect to.
For each consumer-producer pair:
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. Suppose the locations are ordered in increasing order of the cost, i.e, the locations are L1, L2,... such that CostStep 1 - the facility-location step - is more challenging to analyze. It is possible to prove that this is a potential game. 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.
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, then the social welfare after the sequence is at least times the optimum. This latter result is true in much more general class of games, called utility games.