Search

We consider a competitive facility location problem on a network where consumers located on vertices wish to connect to the nearest facility. Knowing this, each competitor locates a facility on a vertex, trying to maximize market share. We focus on the two-player case and study conditions that guarantee the existence of a pure-strategy Nash equilibrium 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 (for example, in cactus graphs), this provides a complete and efficient characterization of equilibria. In that case, we show that 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. Funding: This work was partially supported by the Chazen Institute of International Business at Columbia Business School, by Conicet Argentina [Grant Resolucion 4541/12] and by ANPCyT Argentina PICT-2012-1324. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/opre.2017.1694. Keywords: competitive facility location * Hotelling competition * 1-median * Nash equilibrium * Voronoi game, 1. Introduction Facility location problems study how to best locate facilities, anticipating that consumers will be attracted by the facility that is most convenient to them. Such problems are related [...]

We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that [...]