You are here

The Competitive Facility Location Problem in a Duopoly

The Competitive Facility Location Problem in a Duopoly


Coauthor(s): Y. Gur, D. Saban, and N. E. Stier-Moses
Download (PDF)

Abstract
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 maximize their market share. Focusing on the two-player case, we study conditions that guarantee the existence of a pure-strategy Nash equilibrium in this nite non- cooperative game for progressively more complicated classes of networks. For general graphs, we show that attention can be restricted to a subset of vertices we refer to as the central block. By constructing trees of maximal bi-connected components we obtain sufficient conditions for equilibrium existence. Moreover, when the central block is a vertex or a cycle (e.g., cactus graphs), this provides a complete and efficient characterization of equilibria: at equilibrium both competitors locate their facilities in a solution to the 1-median problem (generalizing the classical insight by Hotelling). We further explore relations between the equilibria locations and 1-medians, and show that indeed an equilibrium must solve the 1-median problem for additional classes of graphs such as median (including grids, an applicable representation of urban networks), quasi-median, pseudo-median, Helly and strongly-chordal graphs. We also generalize what was known for trees by establishing that selecting a 1-median is also a sufficient condition for 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 (where removing an edge can increase the performance for all players), and implies that the worst-possible equilibria are achieved in trees. While equilibria can be arbitrary inefficient relative to centralized solutions of the location problem, we quantify the inefficiency gap with parametric upper bounds that depend on topological network parameters.

Exact Citation:
Y. Gur, D. Saban, and N. E. Stier-Moses "The Competitive Facility Location Problem in a Duopoly." , Columbia Business School, (2013).
Date: 2013