The Competitive Facility Location Problem in a Duopoly
Coauthor(s): Y. Gur, D. Saban, and N. E. Stier-Moses
We consider a competitive facility location game on a network in which consumers who are located on the vertices wish to connect to the nearest facility. Knowing this, each competitor locates a facility on a vertex, trying to capture the largest-possible market share. Focusing in the two-player case, we study conditions that guarantee the existence of a pure-strategy Nash equilibrium in this finite non-cooperative game for progressively more complicated classes of networks. The case of trees, which extends the classic Hotelling model, is well-studied: equilibrium locations are characterized by 1-medians of the tree. We find that equilibria in cycles exist when there is at least one vertex with a sufficiently big demand, in which case it must also be a 1-median of the cycle. For a general graph, we construct a tree of maximal bi-connected components, which allows us we show that we can restrict our attention to a subset of vertices that we refer to as the central block. When that central block is a vertex or a cycle (e.g., cactus graphs), this provides a complete and efficient characterization of equilibria. For that class of graphs, at equilibrium both competitors locate their facilities in a solution to the 1-median problem, generalizing the classical insight by Hotelling from a line to more complicated networks. We further explore relations between the location of equilibria and 1-medians, and show that indeed, an equilibrium must solve the 1-median problem for additional classes of graphs such as median, quasi-median, pseudo-median, Helly and strongly-chordal graphs. Importantly, median graphs include grids which are good representations of urban networks. In the converse direction, we generalize what was known for trees by establishing that selecting a 1-median is also a sufficient condition for achieving equilibria in strongly-chordal graphs. Finally, we show that removing edges from a graph with a central block that is a cycles or a vertex increases the consumer cost. This precludes situations like the Braess paradox, whereby removing an edge can increase the performance for all players. These results imply that the networks with the worst-possible equilibria are achieved in trees because they are minimal instances with respect to inclusion. While equilibria can be arbitrary inefficient with respect to centralized solutions to the location problem, we quantify the inefficiency with parametric upper bounds that depend on topological parameters of the network.
Y. Gur, D. Saban, and N. E. Stier-Moses "The Competitive Facility Location Problem in a Duopoly." , Columbia Business School, (2012).