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: For each consumer-producer pair: 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). 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 formula_1, then the social welfare after the sequence is at least formula_2 times the optimum. This latter result is true in much more general class of games, called utility games. Facility location (competitive