# 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 problem on a network in which consumers located on
vertices wish to connect to the nearest facility. Knowing this, each competitor locates a facility on a vertex,
trying to maximize her market share. We focus on the two-player case and 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. For general graphs, we show that attention can be restricted to a subset
of vertices referred 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 a well-known insight
arising from Hotelling's model. We further show that an equilibrium must solve the 1-median problem
in other classes of graphs, including grids which essentially capture the topology of urban networks. In
addition, when both players select a 1-median, the solution must be at equilibrium for strongly-chordal
graphs, generalizing a previously known result for trees. We perform an efficiency analysis and show that
removing edges from a graph whose central block is a cycle or a vertex increases the consumer cost. This
implies that the worst-possible equilibria are achieved in trees. While equilibria can be arbitrarily inefficient
relative to centralized solutions, we quantify the inefficiency gap with parametric upper bounds that depend
on topological network parameters. Finally, we consider the practical robustness of our results by taking
random neighborhoods of a real city and solving for equilibria. We show that the insights derived from theory
hold with high probability for urban topologies even when not a grid or when players are not homogeneous.

**Exact Citation:**

*Y. Gur, D. Saban, and N. E. Stier-Moses "The Competitive Facility Location Problem in a Duopoly." , Columbia Business School, (2014).*

**Date:**

*2014*