1 Introduction

Ever since the seminal work of Hotelling (1929), competitive location models have been intensively studied in the economic and operations research literature. This is reflected in the large amount of review articles and special issues that have appeared over the past decades, such as Drezner (1995), Eiselt et al. (1993), Eiselt and Laporte (1996), Kress and Pesch (2012b), Plastria (2001), Serra and ReVelle (1995), Friesz (2007) and Santos-Peñate et al. (2007). Essentially, one seeks to locate (physical or nonphysical) facilities in some given space with respect to some objective function, incorporating the fact that location decisions have been or will be made by independent decision-makers (players) who will subsequently compete with each other.

A well known competitive location problem, formally introduced by Hakimi (1983), is the (r|X p )-medianoid problem. Here, given a network with customers located in the vertices and a predefined set of p leaders’s (or incumbent’s) facilities X p , a follower (or entrant) wants to enter the market with a given number of r facilities so that the market share is maximized. When restricting the set of potential facility sites to the vertex set of the network, this problem is sometimes referred to as the maximum capture problem (MAXCAP, ReVelle 1986) or discrete (r|X p )-medianoid problem. Obviously, when players compete for market share, the researcher needs to apply some kind of customer choice model. Typically, as in Hakimi (1983), customer choice is assumed to be binary, i.e. it is assumed to be deterministic from the perspective of the players with the total demand of each customer being served by a single facility. For example, one may suppose that customers patronize the closest facility only.Footnote 1Fernández et al. (2007) and Benati and Hansen (2002), among others, deviate from this assumption. In the latter paper, the authors introduce the maximum capture problem with random utilities. Here, probabilistic customer behavior is modeled by random utility functions that are composed of deterministic and stochastic components. They select the multinomial logit approach, which is well established in the economics, marketing and operations research literature (see, for example, Anderson et al. 1992; Hensher et al. 2005; Train 2003), to model the decision process of utility maximizing customers. In their definition of the deterministic component, the authors focus on incorporating effects of distances from customers to facility locations. An overview of other location models utilizing probabilistic choice models can be found in the review papers mentioned above. Braid (1988) and Chisholm and Norman (2004), for instance, consider the choice of locations of two or more (single-product or multiple-product) firms on small chain networks under the multinomial logit model.

As Hotelling (1929) considers not only location, but also price decisions, another stream of research focuses on the incorporation of price competition into competitive location models. The majority of these models is concerned with one-dimensional location spaces (see Kress and Pesch 2012b, for a recent overview). For example, de Palma et al. (1985) consider equilibrium locations of two or more firms along a line segment with uniformly spread customers with and without price competition under the multinomial logit model. Another related example is Lederer (2003). Fik and Mulligan (1991), Fik (1991) and Braid (1993) are examples of (economic) models of spatial competition that consider network structures with discrete and continuous (customers are dispersed over the edges of the network) demand distributions. Serra and ReVelle (1999) consider the maximum capture problem on networks under a binary choice rule, where players are allowed to compete in prices after having chosen locations.

As proposed by Benati and Hansen (2002), this paper contributes to the literature by applying the idea of competition in prices to the maximum capture problem with random utilities in order to “improve the realism of the model”. Hence, our research is closely related to de Palma et al. (1985). Related models can also be found in the field of product positioning, cf. Choi et al. (1990) and Rhim and Cooper (2005). We additionally contribute to the literature by providing complexity results for the resulting location problem. In order to compute equilibrium prices under multinomial logit demand, we adapt a fixed-point iteration approach that has previously been introduced in the literature by Morrow and Skerlos (2011) (cf. also Morrow 2008). In this context, we present examples of problem instances with fixed location sets of the players, that demonstrate the potential non-existence of price equilibria and the case of multiple local equilibria in prices. Finally, we show that different price sensitivity levels of customers may actually affect optimal locations of facilities, and we provide first insights into the performance of heuristic algorithms for the location problem.

This paper proceeds as follows. First, we introduce the basic notation and definitions in Section 2. A detailed problem formulation is given in Section 3 with results concerning the existence of price equilibria and the computational complexity in Sections 3.1 and 3.2, respectively. In Section 4 we are concerned with the aforementioned fixed-point iteration approach (Section 4.1), example instances (Section 4.2) and some computational tests (Section 4.3). Heuristic approaches for solving the location problem are subject of Section 5. The paper closes with a conclusion in Section 6.

2 Notation and Definitions

In the course of this paper we assume the reader to be familiar with the basic concepts of graph theory (see, for example, Gross and Yellen 2004; Swamy and Thulasiraman 1981) and game theory. We refer to Fudenberg and Tirole (1991) for an excellent introduction to the latter topic.

We use the graph theoretic notation of Bandelt (1985), Bauer et al. (1993), Kress and Pesch (2012a). Hence, we will denote a network by N=(V,E,λ), with V (|V|=n) being the (finite) vertex set and E (|E|=m) being the (finite) edge set of the underlying graph. The mapping \(\lambda : E \rightarrow \mathbb {R}^{+}\) defines the lengths of the network’s edges. An edge e∈E joining two vertices u and v is denoted by e=[u,v]. We assume that the networks considered in this paper are undirected, connected and that there are no multiple edges. Moreover, we assume that there are no loops at the vertices. We denote the length of a shortest path (distance) connecting two vertices x and y of a network by d(x,y)=d x y .

We will consider games in strategic form that have three basic elements (Fudenberg and Tirole 1991, p. 4): A set of players Θ which we assume to be finite (Θ={1,...,𝜃}), a (pure) strategy space Ψ i for each player i∈Θ, and a payoff function u i (ψ) for each player i∈Θ that assigns a utility level to every vector of strategies ψ=(ψ 1,...,ψ 𝜃 ), ψ i ∈Ψ i . A strategy vector \(\boldsymbol {\psi }^{N} = ({\psi _{1}^{N}},...,\psi ^{N}_{\theta })\) is said to be a Nash equilibrium in pure strategies, if no player can unilaterally increase his utility, i.e. \(u_{i}(\boldsymbol {\psi }^{N}) \geq u_{i}(\psi _{i}, \boldsymbol {\psi }^{N}_{{\varTheta } \setminus \{i\}})\) for all ψ i ∈Ψ i , where \(\boldsymbol {\psi }^{N}_{{\varTheta } \setminus \{i\}} = ({\psi _{j}^{N}} | j \in {\varTheta }, j \ne i)\) (cf. Gabay and Moulin 1980).

3 Problem Formulation

Consider a network N=(V,E,λ). A finite number of (homogenous) customers is located at the vertices of N. At each vertex there may be several customers or none at all. Their demand is described by a weight function \(\pi : V \rightarrow \mathbb {R}^{+}_{0}\), where π is different from the zero function. When facing real world data, this weight function will typically have to be derived via aggregation (Plastria and Vanhaverbeke 2007). A firm I (incumbent) acts as a monopolist with multiple facilities in this spatial market. I’s facilities are located at p>0 distinct vertices \(X_{p} \subseteq V\) of the network. A competitor E (entrant) wants to enter the market with an a priori fixed number of facilities r>0.Footnote 2 E’s potential facility sites are restricted to the vertex set of the network. Hence, E solves a discrete (r|X p )-medianoid problem. At most two facilities, one of the incumbent’s and one of the entrant’s facilities, may be located at each vertex. The players are profit maximizing and sell a single homogeneous product. As, in most markets, the choice of location is usually less flexible than the choice of prices, we assume that simultaneous price competition occurs after E’s location decisions have been made. Thus, the game under consideration is composed of multiple stages (see Fig. 1, cf. also Rhim and Cooper (2005)). In the first stage, E decides on the locations \(Y_{r} \subseteq V\) of the facilities. In the second stage, both players simultaneously decide on a (mill) price for the product. This stage – as characterized by Eiselt et al. (1993) – is a noncooperative game in which the strategies are prices and payoffs are profits. A solution to this stage is a pure strategy Nash equilibrium in prices, assuming that such an equilibrium exists. After the prices have been set, customers accommodate their demand and market shares are established.

Fig. 1
figure 1

Stages of the game

Full size image

The utility \(u_{ij}^{q}\) of a customer located in vertex i∈V from patronizing a facility located in vertex j∈V and belonging to player q∈{I,E} is composed of a deterministic component \(v_{ij}^{q}\) and a stochastic component \(\epsilon _{ij}^{q}\), the latter being related to unobservable, utility affecting factors:

$$ u_{ij}^{q} = v_{ij}^{q} + \epsilon_{ij}^{q}. $$
(1)

Based on Benati and Hansen (2002), we define

$$ v_{ij}^{q} := {a_{j}^{q}} - \alpha d_{ij} - \beta p_{q}, $$
(2)

where

  • \({a_{j}^{q}} \in \mathbb {R}\) is the player-specific (index q) average quality level associated with a facility located in vertex j (related to opening hours, size, etc.),

  • α≥0 is a scaling parameter for distance (“coefficient of spatial friction”, Benati and Hansen (2002)),

  • β>0 is a sensitivity parameter for price,

  • p q is the unit mill price charged at all of player q’s facilities.

In the remainder of the paper we will simplify the notation by referring to the set of facilities (choice set) by simply writing \(X_{p} \cup Y_{r}\). For an element \(l \in X_{p} \cup Y_{r}\), the appropriate player q∈{I,E} “owning” facility l will always become clear from the context. Then, the probability \(P_{ij}^{q}\) that a customer located in vertex i∈V chooses facility \(j \in X_{p} \cup Y_{r}\) of player q is

$$P_{ij}^{q} = Prob(u_{ij}^{q} > u_{ik}^{\tilde q} \; \forall \, k \in X_{p} \cup Y_{r}, k \ne j). $$

A closed form expression for \(P_{ij}^{q}\) can be derived when assuming that the stochastic components are independently and identical extreme value distributed (Gumbel distributed) with the cumulative distribution

$$F(\epsilon_{ij}^{q}) = e^{-e^{-\epsilon_{ij}^{q} \slash \delta}}. $$

The variance is δ 2 π 2/6, where δ is a scaling parameter. As δ approaches zero, customer choices become deterministic. The mean is δ γ, where γ is Euler’s constant. For the sake of notational convenience we define s:=1/δ and assume s>0. The closed form expression that one derives after some algebraic transformations corresponds to a well known random utility model, i.e. the multinomial logit model (see McFadden 1974; Train 2003, for more details):

$$ P_{ij}^{q} = \frac{e^{sv_{ij}^{q}}}{\sum\limits_{k \in X_{p} } {e^{sv_{ik}^{I} } } + \sum\limits_{k \in Y_{r} } {e^{sv_{ik}^{E} } } } \quad \forall \, i \in V, j \in X_{p} \cup Y_{r} . $$
(3)

To simplify the notation, let q∈{I,E}, and define

$$ Z_{q}:= \left\{\begin{array}{lllll} X_{p} & \text{if } q=I, \\ Y_{r} & \text{if } q=E. \end{array}\right. $$
(4)

Furthermore, define

$$ {{\Lambda}^{q}_{i}} := \ln \left( \sum\limits_{k \in Z_{q} }{ e^{s({a_{k}^{q}} - \alpha d_{ik}) } } \right) \quad \forall i \in V, q \in \{I, E\}, $$
(5)

so that

$$ P_{ij}^{q} = \frac{ e^{sv_{ij}^{q}}}{ e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}} + e^{{{\Lambda}^{E}_{i}} -s \beta p_{E}} } \quad \forall \, i \in V, j \in X_{p} \cup Y_{r} . $$
(6)

As pointed out by Choi et al. (1990), this model forces every customer to choose a facility regardless of prices. Hence, a “no purchase” option with a corresponding deterministic utility component of zero is included, so that we get

$$ P_{ij}^{q} = \frac{e^{sv_{ij}^{q}}}{e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}} + e^{{{\Lambda}^{E}_{i}} -s \beta p_{E}} + 1 } \quad \forall \, i \in V, j \in X_{p} \cup Y_{r}. $$
(7)

Let c q , q∈{I,E}, be the cost of producing one unit of the product at one of player q’s facilities. Then, given Y r , p E , X p and p I , the (expected) profit π q of player q is as follows:

$$ {\Pi}_{q} = (p_{q} - c_{q}) \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q}}{\pi(i)} P_{ij}^{q}}. $$
(8)

Additionally, we will consider an exogenous upper bound (parameter \(\bar p > \underset {q \in \{I,E\}}{\max } c_{q}\)) on the prices charged by the players. This bound may, for example, correspond to a price-cap that is imposed by a regulator of the market.

We define the binary variables

$${y_{j}^{E}} :=\left\{ {\begin{array}{ll} 1 & \text{if E locates a facility in vertex j,}\\ 0 & \text{else,} \\ \end{array}} \right. \; \forall \, j \in V.\\ $$

Then, a mathematical programming formulation for the problem under consideration is as follows:

$$\begin{array}{@{}rcl@{}} \underset{p_{I}, p_{E} ,\mathbf{y^{E}}}{\max} && {\Pi}_{E} (p_{I}, p_{E} ,\mathbf{y^{E}}) = (p_{E} - c_{E}) \sum\limits_{i \in V} {\sum\limits_{j \in V} \pi(i) {y_{j}^{E}}} \end{array} $$
(9)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad\qquad\quad ~~~~~~~~~~~{{ \frac{e^{s({a_{j}^{E}} - \alpha d_{ij} - \beta p_{E})}}{ e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}} + \sum\limits_{k \in V} {{y_{k}^{E}} e^{s({a_{k}^{E}} - \alpha d_{ik} - \beta p_{E})}} +1 }}} \\ \text{subject to} &&p_{I} \in \underset{p_{I}}{\operatorname{argmax}} \; {\Pi}_{I} (p_{I}, p_{E} ,\mathbf{y^{E}}) =(p_{I} - c_{I}) \sum\limits_{i \in V} {\pi(i)} \end{array} $$
(10)
$$\begin{array}{@{}rcl@{}} &&\qquad \qquad\qquad\qquad~~~~~~~{{\frac{e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}}}{ e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}} + \sum\limits_{k \in V} {{y_{k}^{E}} e^{s({a_{k}^{E}} - \alpha d_{ik} - \beta p_{E})}}+1 }}}, \\ &&p_{E} \in \underset{p_{E}}{\operatorname{argmax}} \; {\Pi}_{E} (p_{I}, p_{E} ,\mathbf{y^{E}}) =(p_{E} - c_{E}) \sum\limits_{i \in V} {\sum\limits_{j \in V} \pi(i) {y_{j}^{E}} } \end{array} $$
(11)
$$\begin{array}{@{}rcl@{}} &&\qquad \qquad \qquad \qquad \qquad\! {} {{ \frac{e^{s({a_{j}^{E}} - \alpha d_{ij} - \beta p_{E})}}{ e^{{{\Lambda}^{I}_{i}} -s \beta p_{I}} + \sum\limits_{k \in V} {{y_{k}^{E}} e^{s({a_{k}^{E}} - \alpha d_{ik} - \beta p_{E})}}+1 }}}, \\ && \sum\limits_{j \in V}{{y_{j}^{E}}}=r, \end{array} $$
(12)
$$\begin{array}{@{}rcl@{}} && p_{I}, p_{E} \leq \bar p, \end{array} $$
(13)
$$\begin{array}{@{}rcl@{}} && p_{I}, p_{E} \geq 0, \end{array} $$
(14)
$$\begin{array}{@{}rcl@{}} && {y_{j}^{E}} \in \{0,1\} \qquad \forall j \in V. \end{array} $$
(15)

The objective function Eq. 9 corresponds to the entrant’s (expected) profit maximization. Equations 10 and 11 enforce a Nash equilibrium in prices, assuming that such an equilibrium exists. Equation 12 guarantees that exactly r facility locations are selected. The remaining constraints, Eqs. 13, 14, and 15, define the domains of the variables, including the restriction of the prices by the upper bound \(\bar p\).

We will refer to the problem defined by Eqs. 9–15 as the location-then-price game under a logit assumption and denote it by LPL. We will use index q∈{I,E} to refer to the players of LPL throughout the remainder of this paper. Moreover, given a player q∈{I,E}, we will refer to the opposing player by \(\bar q := \{I,E\} \setminus q\).

Note that there exists an (endogenous) upper bound on prices even if we set \(\bar p = \infty \), which is well known for logit choice probabilities (including a no purchase option):

Lemma 1

Even if \(\bar p = \infty \) , there exist finite upper bounds on the prices charged by the incumbent and the entrant, i.e. \(p_{q} < \infty \) , q∈{I,E}.

Proof

It is easy to verify that

$$ \frac{\partial P_{ij}^{q}}{\partial p_{q}} = -s \beta P_{ij}^{q} \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right), $$
(16)

for all i∈V and j∈Z q , q∈{I,E}, as defined in Eq. 4.

We have

$$\underset{p_{q} \to \infty }{\lim } {{\Pi}_{q}} = \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i) \cdot \underset{p_{q} \to \infty }{\lim } { \frac{p_{q}-c_{q}}{({P_{ij}^{q}})^{-1}} } }}. $$

Using L’Hospital’s rule for any i∈V, j∈Z q , we get

$$\begin{array}{@{}rcl@{}} \underset{p_{q} \to \infty }{\lim } { \frac{p_{q}-c_{q}}{({P_{ij}^{q}})^{-1}} } \!&=&\! \underset{p_{q} \to \infty }{\lim } { \frac{1}{\frac{\partial ({P_{ij}^{q}})^{-1}}{\partial p_{q}}} } \,=\,\underset{p_{q} \to \infty }{\lim } { \frac{1}{- \frac{1}{({P_{ij}^{q}})^{2}} \frac{\partial P_{ij}^{q}}{\partial p_{q}}}} \,=\, \underset{p_{q} \to \infty }{\lim } { \frac{1}{s \beta \left( \frac{1}{P_{ij}^{q}} - \frac{\sum\nolimits_{k \in Z_{q}}{P_{ik}^{q}}}{P_{ij}^{q}} \right)}}\\ & =& \underset{p_{q} \to \infty }{\lim } { \frac{1}{s \beta \left( \frac{1}{P_{ij}^{q}} - \sum\nolimits_{k \in Z_{q}}{e^{s({a_{k}^{q}}-{a_{j}^{q}}-\alpha(d_{ik}-d_{ij}))}} \right)}} = 0 \end{array} $$

because

$$\begin{array}{@{}rcl@{}} \underset{p_{q} \to \infty }{\lim } {P_{ij}^{q}} &=& \underset{p_{q} \to \infty }{\lim } \frac{e^{s({a_{j}^{q}} - \alpha d_{ij} - \beta p_{q})}}{\sum\limits_{k \in X_{p} } {e^{s({a_{k}^{I}} - \alpha d_{ik} - \beta p_{I}) } } + \sum\limits_{k \in Y_{r} } {e^{s({a_{k}^{E}} - \alpha d_{ik} - \beta p_{E}) } } + 1 }\\ & =&\underset{p_{q} \to \infty }{\lim } \frac{1}{\sum\limits_{k \in Z_{q} } { e^{s({a_{k}^{q}}-{a_{j}^{q}}-\alpha(d_{ik}-d_{ij}))} } + \frac{c}{e^{s({a_{j}^{q}} - \alpha d_{ij} - \beta p_{q})}} } = 0, \end{array} $$

where we define

$$ c := \left\{\begin{array}{lllll} \sum\limits_{k \in Y_{r} } {e^{s v_{ik}} } + 1 & \text{if } q=I, \\ \sum\limits_{k \in X_{p} } {e^{s v_{ik} } } + 1 & \text{if } q=E. \end{array}\right. $$
(17)

Thus, the players have no incentive to charge infinite prices. This proves the assertion. □

3.1 Pricing Stage: Nash Equilibria and Local Equilibria

In this section, we provide a sufficient condition for the existence of a pure strategy Nash equilibrium in prices. Similar results are due to Choi et al. (1990) and Rhim and Cooper (2005). Note, however, that their proofs and discussions do not directly apply to the case r,p>1.

Observe that π q , q∈{I,E}, is negative for any p q <c q . Thus, it is reasonable to assume that prices are bounded below by the unit production costs, i.e. c q ≤p q , for the remainder of this paper. Then we may restrict the player q’s strategy space to the nonempty, compact and convex interval \([c_{q}, \bar p]\).

The following theorem is well known (see, for instance, Fudenberg and Tirole 1991):

Theorem 1

Let Θ be a nonempty set of players and consider a strategic-form game whose strategy spaces Ψ i , i ∈ Θ, are nonempty, compact and convex subsets of an Euclidean space. If the payoff functions u i are continuous in ψ and quasiconcave in ψ i , then there exists a pure strategy Nash equilibrium.

Based on this theorem, a sufficient condition for the existence of a pure strategy Nash equilibrium in prices can easily be derived. To do so, we will require the payoff functions π q , q∈{I,E}, to be concave in p q on \([c_{q}, \bar p]\). Hence, for each player, a unique best response exists for each strategy of the opponent.

Theorem 2

A sufficient condition for the existence of a pure strategy Nash equilibrium in prices is

$$ s \beta \leq \frac{2}{\bar p - c_{q}} $$
(18)

for q∈{I,E}.

Proof

It is easy to verify that the payoff functions stated in Eq. 8 are continuous in \([c_{I}, \bar p] \times [c_{E}, \bar p]\). In the following we will derive sufficient conditions for the concavity of the payoff functions in p q on \([c_{q}, \bar p]\).

Define Z q , q∈{I,E}, as in Eq. 4. From Eq. 16, we get

$$ \frac{\partial^{2} P_{ij}^{q}}{\partial {p_{q}^{2}}} = s \beta P_{ij}^{q} \sum\limits_{k \in Z_{q} } {\frac{\partial P_{ik}^{q}}{\partial p_{q}}} - s \beta \frac{\partial P_{ij}^{q}}{\partial p_{q}} \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) , $$
(19)

for all i∈V and j∈Z q , and hence

$$\begin{array}{@{}rcl@{}} \frac{\partial {\Pi}_{q}}{\partial p_{q}} &= \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i)P_{ij}^{q}}} + (p_{q} - c_{q}) \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i)} \cdot \frac{\partial P_{ij}^{q}}{\partial p_{q}}}, \end{array} $$
(20)
$$\begin{array}{@{}rcl@{}} \frac{\partial^{2} {\Pi}_{q}}{\partial {p_{q}^{2}}} &= 2\sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i) \frac{\partial P_{ij}^{q}}{\partial p_{q}}}} + (p_{q} - c_{q}) \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i)} \cdot \frac{\partial^{2} P_{ij}^{q}}{\partial {p_{q}^{2}}}}. \end{array} $$
(21)

π q , q∈{I,E}, is concave in p q if

$$\frac{\partial^{2} {\Pi}_{q}}{\partial {p_{q}^{2}}} \leq 0. $$

This is guaranteed if

$$2 \frac{\partial P_{ij}^{q}}{\partial p_{q}} + (p_{q} - c_{q}) s \beta P_{ij}^{q} \sum\limits_{k \in Z_{q} } {\frac{\partial P_{ik}^{q}}{\partial p_{q}}}- (p_{q} - c_{q}) s \beta \frac{\partial P_{ij}^{q}}{\partial p_{q}} \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) \leq 0 $$

for all i∈V and j∈Z q . It is easy to see that \(\partial P_{ij}^{q} \slash \partial p_{q} < 0\) for all i∈V and j∈Z q . Thus,

$$ (p_{q} - c_{q}) s \beta P_{ij}^{q} \sum\limits_{k \in Z_{q} } {\frac{\partial P_{ik}^{q}}{\partial p_{q}}} \leq 0, $$
(22)

for all i∈V and j∈Z q , so that it is sufficient to require

$$2 \frac{\partial P_{ij}^{q}}{\partial p_{q}} - (p_{q} - c_{q}) s \beta \frac{\partial P_{ij}^{q}}{\partial p_{q}} \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) \leq 0, $$

or, equivalently,

$$2 - (p_{q} - c_{q}) s \beta \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) \geq 0, $$

for all i∈V and j∈Z q . Given Eq. 18, the latter inequality holds for all i∈V and j∈Z q , since

$$0 < \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) < 1, $$

for all i∈V. This proves the claim. □

The derivation of a less restrictive existence result, for example by providing a better upper bound than the one used in Eq. 22, is left for future research. Similarly, apart from the rather trivial uniqueness result of Section 3.2, the “complexity of the demand function prohibits the derivation of a [more general] global uniqueness condition” (Choi et al. 1990), for example by requiring strict diagonal dominance of the Jacobian of the first order conditions for profit maximization (Gabay and Moulin 1980). Hence, when Eq. 18 do not hold, we must rely on local conditions for optimality of prices (Morrow and Skerlos 2011; Morrow 2008):

Definition 1 (Morrow (2008))

A price vector \(\mathbf {p}=(p_{I},p_{E}) \in [c_{I}, \bar p] \times [c_{E}, \bar p]\) is called a local (global) price equilibrium, if element p q is a local (global) maximizer of \({\Pi }_{q}(p_{q},\hat p_{\bar q})\) for each q∈{I,E}, where \(\hat p_{\bar q}\) denotes a fixed price of player \(\bar q\).

Note that any global price equilibrium is a pure strategy Nash equilibrium in prices. Additionally observe that, when Eqs. 18 hold, any local price equilibrium is a global price equilibrium.

3.2 Computational Complexity

In this subsection we will show that LPL, i.e. the problem defined by Eqs. 9–15, is NP-hard.

Lemma 2

Let

$$ s \beta \leq \frac{1}{\bar p - c_{q}} $$
(23)

for q∈{I,E}. Then there exists a unique pure strategy Nash equilibrium in prices with \(p_{I} = p_{E} = \bar p\) for all feasible location settings.

Proof

Let q∈{I,E} and Z q as defined in Eq. 4. We will show that π q is strictly monotonic increasing in p q on the interval \(I=[c_{q},\bar p]\) if Eq. 23 holds. This will prove the claim.

π q is strictly monotonic increasing on I if

$$\frac{\partial {\Pi}_{q}}{\partial p_{q}} = \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i)P_{ij}^{q}}} + (p_{q} - c_{q}) \sum\limits_{i \in V }{\sum\limits_{j \in Z_{q} }{\pi(i)} \cdot \frac{\partial P_{ij}^{q}}{\partial p_{q}}} > 0 $$

on I. It is sufficient to require

$$P_{ij}^{q} + (p_{q} - c_{q}) \frac{\partial P_{ij}^{q}}{\partial p_{q}} = P_{ij}^{q} - (p_{q} - c_{q}) s \beta P_{ij}^{q} \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) > 0 $$

or, equivalently,

$$1 - (p_{q} - c_{q}) s \beta \left( 1 - \sum\limits_{k \in Z_{q} } {P_{ik}^{q}} \right) > 0 $$

for all i∈V and j∈Z q . It is easy to see that this condition holds if we assume Eq. 23 to hold. □

The maximum capture problem with random utilities (Benati and Hansen 2002; Benati 2000) (MAXCAP-R) is closely related to LPL. The former problem considers stages 1 (location) and 3 (sales) of Fig. 1 only and uses the definition \({v_{ij}^{q}}^{\prime }:={{a_{j}^{q}}}^{\prime } - \alpha ^{\prime } d_{ij}\) instead of Eq. 2. A no purchase option is not considered in MAXCAP-R, i.e. we have Eq. 6 instead of Eq. 7. Furthermore, c I =c E =0. The model defined by Eqs. 9–15 “reduces” to:Footnote 3

$$\begin{array}{@{}rcl@{}} &&\underset{\mathbf{y^{E}}}{\max}~~~{\Pi}^{\prime}_{E} (\mathbf{y^{E}}) = \sum\limits_{i \in V} {\sum\limits_{j \in V} \pi(i) {y_{j}^{E}} \cdot} {{ \frac{e^{s({{a_{j}^{E}}}^{\prime} - \alpha^{\prime} d_{ij})}}{ e^{{{{\Lambda}^{I}_{i}}}^{\prime}} + \sum\limits_{k \in V} {{y_{k}^{E}} e^{s({{a_{k}^{E}}}^{\prime} - \alpha^{\prime} d_{ik})}}}}}\end{array} $$
(24)

subject to Eqs. 12 and 15.

Note that MAXCAP-R can not directly be interpreted to be a special case of LPL even if LPL’s no purchase option is dropped, since we assume β>0 and \(\bar p > \underset {q \in \{I,E\}}{\max } c_{q}\).

Theorem 3 (Benati and Hansen (2002), Benati (2000))

MAXCAP-R is NP-hard.

In the following, we will adapt the NP-hardness proof of Theorem 3 as presented by Benati (2000) and Benati and Hansen (2002) to the MAXCAP-R with an additional no purchase option (MAXCAP-RNP).Footnote 4 Here, the probability that a customer located in vertex i∈V chooses facility \(j \in X_{p} \cup Y_{r}\) of player q is given by

$${{P_{ij}^{q}}^{\prime}}=\frac{e^{s({{a_{j}^{q}}}^{\prime} - \alpha^{\prime} d_{ij})}}{ e^{{{{\Lambda}^{I}_{i}}}^{\prime}} + e^{{{{\Lambda}^{E}_{i}}}^{\prime}} +1}. $$

Given a set Y r of entrant locations, we define \(z_{i}(Y_{r}):= \sum \limits _{j \in Y_{r}} \pi (i) {P_{ij}^{E}}'\).

The proof is based on a reduction of the NP-hard Dominating Set (DS) problem (Garey and Johnson 1979): Given a network N=(V,E,λ) with λ(u v)=1 for all [u,v]∈E and a positive integer r≤|V|, is there a set \(V' \subseteq V\) with \(|V^{\prime }| \leq r\) and \(D(i,V^{\prime }):= \min \{d(i,j)|j \in V^{\prime }\} \leq 1\) for all i∈V?

Given an instance I D S of DS, we construct an instance I M of MAXCAP-RNP as follows. Set π(v)=1 for every vertex v∈V and add a vertex z with π(z)=0. Denote the augmented vertex set by \(V^{\prime }\). Connect z to every vertex v∈V by an edge [z,v] of length λ(z v)=2. Set p=1 and locate the incumbent’s facility in z. Moreover, choose \({{a^{E}_{j}}}^{\prime }= 1.5 \alpha ^{\prime }\) for all potential entrant facility sites j and \({{a^{I}_{z}}}^{\prime }= 1.5 \alpha ^{\prime }\) for the incumbent facility in z. Set s=1. We will prove (in analogy to Benati 2000) that there exists a value \(\alpha ^{\prime } > 0\) such that any optimal solution to I M provides a dominating set of I D S if one exists.

Given a solution Y r to I M , define V 0:={v∈V|D(v,Y r )=0}, V 1:={v∈V|D(v,Y r )=1} and V 2:={v∈V|D(v,Y r )≥2}. Note that Y r may contain vertex z while this is not the case for the sets V 0 to V 2. V 0 and V 1 are referred to as dominated sets of V, V 2 is the non-dominated set of V. The elements are called dominated and non-dominated vertices, respectively. Observe that z z (Y r )=0.

Lemma 3

Let i∈V 2 . Then, for every 𝜖 1 >0, there exists a value \(\alpha ^{\prime }_{1}\) , such that for every \(\alpha ^{\prime } \geq \alpha ^{\prime }_{1}\) we have z i (Y r )≤𝜖 1.

Proof

It is easy to see that \({\sum }_{j \in Y_{r}} e^{{{a_{j}^{E}}}^{\prime }-\alpha ^{\prime } d_{ij}} \leq r e^{-0.5 \alpha ^{\prime }}\). Therefore,

$$z_{i}(Y_{r}) \leq \frac{r e^{-0.5 \alpha^{\prime}}}{r e^{-0.5 \alpha^{\prime}}+ e^{-0.5 \alpha^{\prime}} +1} = \frac{r}{r+1+e^{0.5 \alpha^{\prime}}}. $$

Now \(\underset {\alpha ^{\prime } \rightarrow \infty }{\lim } \frac {r}{r+1+e^{0.5 \alpha ^{\prime }}} = 0\) which proves the claim. □

Lemma 4

Let \(i \in V_{0} \cup V_{1}\) . Then, for every 𝜖 2 >0, there exists a value \(\alpha ^{\prime }_{2}\) , such that for every \(\alpha ^{\prime } \geq \alpha ^{\prime }_{2}\) we have z i (Y r )≥1−𝜖 2.

Proof

It is easy to see that \({\sum }_{j \in Y_{r}} e^{{{a_{j}^{E}}}^{\prime }-\alpha ^{\prime } d_{ij}} \geq e^{0.5 \alpha ^{\prime }}\). Therefore,

$$z_{i}(Y_{r}) \geq \frac{e^{0.5 \alpha^{\prime}}}{e^{0.5 \alpha^{\prime}}+ e^{-0.5 \alpha^{\prime}} +1} = \frac{1}{1+e^{-\alpha^{\prime}} + e^{-0.5\alpha^{\prime}}} = 1 - \frac{e^{-\alpha^{\prime}} + e^{-0.5\alpha^{\prime}}}{1+ e^{-\alpha^{\prime}} + e^{-0.5\alpha^{\prime}}}. $$

Now \(\underset {\alpha ^{\prime } \rightarrow \infty }{\lim } \left (1 - \frac {e^{-\alpha ^{\prime }} + e^{-0.5\alpha ^{\prime }}}{1+ e^{-\alpha ^{\prime }} + e^{-0.5\alpha ^{\prime }}} \right ) = 1\) which proves the claim. □

Lemma 5 (Benati (2000))

There exists a finite value \(\hat \alpha ^{\prime }\) such that any optimal solution to I M dominates the maximum number of vertices of V.

Proof

Let \({Y_{r}^{1}}\) and \({Y_{r}^{2}}\) be two feasible solutions to I M with \(|V_{0} \cup V_{1}| = \tau \) and \(|V_{0} \cup V_{1}| = \kappa \), respectively. That is, \({Y_{r}^{1}}\) dominates τ vertices and \({Y_{r}^{2}}\) dominates κ vertices of V. Assume τ>κ. Then, from Lemma 4 we get \({\sum }_{i \in V^{\prime }} z_{i}({Y_{r}^{1}}) \geq \tau (1-\epsilon _{2})\), where we define \(\epsilon _{2} :=\frac {e^{-\alpha ^{\prime }} + e^{-0.5\alpha ^{\prime }}}{1+ e^{-\alpha ^{\prime }} + e^{-0.5\alpha ^{\prime }}}\). Similarly, from Lemma 3 we get \({\sum }_{i \in V^{\prime }} z_{i}({Y_{r}^{2}}) \leq \kappa + (n-\kappa ) \epsilon _{1}\), where we define \(\epsilon _{1} := \frac {r}{r+1+e^{0.5 \alpha ^{\prime }}}\).

Define \(\epsilon := \max \{\epsilon _{1}, \epsilon _{2}\}\). We want to guarantee that \({\sum }_{i \in V^{\prime }} z_{i}({Y_{r}^{1}}) > {\sum }_{i \in V^{\prime }} z_{i}({Y_{r}^{2}})\). A sufficient condition is τ(1−𝜖)>κ+(n−κ)𝜖, or, equivalently, τ−κ>(n−κ+τ)𝜖. It is easy to see that the latter statement is true if 𝜖<1/(2n), because τ−κ≥1 and (n−κ+τ)≤2n. Since we can make 𝜖 arbitrarily small by increasing \(\alpha ^{\prime }\), we have proven the claim. □

It is easy to confirm that 𝜖<1/(2n) (as required in the proof of Lemma 5) is true if \(\alpha ^{\prime }> 2 \ln (4rn)\). Therefore, there exists a polynomially bounded, finite value \(\hat \alpha ^{\prime }\) which guarantees that any optimal solution to I M provides a dominating set of I D S if one exists. The fact that MAXCAP-RNP is NP-hard follows readily:

Theorem 4

MAXCAP-RNP is NP-hard.

We conclude:

Theorem 5

LPL is NP-hard.

Proof

Consider an arbitrary instance I M of MAXCAP-RNP. Now construct an instance I L P L of LPL on the same network and with the same number and predefined locations of incumbent and entrant facilities, by setting c I =c E =0 and choosing arbitrary values \(\bar p>0\) and β>0 such that Eqs. 23 hold. I L P L reduces to a pure location game with parametric prices \(p_{I} = p_{E} = \bar p\) (Lemma 2). Set \(\alpha = \alpha ^{\prime }\) and \({a_{j}^{q}} = {{a_{j}^{q}}}^{\prime } + \beta \bar p\), q∈{I,E} for all of the players’ potential facility locations j.

It is easy to see that any optimal solution of I L P L is optimal for I M as well. Observe that the objective function values differ by a factor of \(\bar p\) as chosen above. Thus, we have shown that, given an instance of the NP-hard MAXCAP-RNP, there exists a polynomial transformation to an instance of LPL, which, in turn, proves that LPL is NP-hard. □

4 Pricing Stage

In this section we will analyze numerical approaches to computing local price equilibria. Since the players are profit maximizers, the first order conditions (stationary conditions) for finding an equilibrium are as follows:

$$ \frac{{\partial {\Pi}_{q} }}{{\partial p_{q} }}(p_{I}, p_{E}) \left\{\begin{array}{llll} \leq 0 & \textit{if } p_{q} = c_{q},\\ = 0 & \textit{if } 0 < p_{q} < \bar p,\\ \geq 0 & \textit{if } p_{q} = \bar p, \end{array}\right. \qquad q \in \{I, E\}. $$
(25)

Observe, that, due to the restriction of the players’ strategy spaces by upper and lower bounds, a local price equilibrium will not necessarily be characterized by ∂π q /∂ p q =0 for both players q∈{I,E}. Figure 2 depicts the contour plot of an example instance.Footnote 5 The curves (called contours) track the finite zeros of the partial profit derivatives of the players. In Fig. 2 these lines divide the plane into areas of positive and negative partial profit derivatives. The unique Nash equilibrium is \({p^{N}_{I}}=\bar p =100\) (∂π I /∂ p I >0), \({p^{N}_{E}} = 85.87\) (∂π E /∂ p E =0). We will refer to equilibria of this type as degenerate. Numerical approaches will have to suitably address the potential existence of such degenerate equilibria.

Fig. 2
figure 2

Nash equilibrium with ∂π I /∂ p I >0

Full size image

It is easy to show that

$$\begin{array}{@{}rcl@{}} \frac{\partial^{2} {\Pi}_{q} }{\partial {p_{q}^{2}}}(p_{I}, p_{E}) &=& -2s \beta \sum\limits_{i \in V } { \pi(i) (Z_{iq}-Z_{iq}^{2})} \\&&+ (p_{q} - c_{q})s^{2} \beta^{2} \sum\limits_{i \in V } { \pi(i) (2Z_{iq}^{3}-3Z_{iq}^{2}+Z_{iq})}, \end{array} $$
(26)

where Z q is defined as in Eq. 4 and we define \(Z_{iq}:= \sum \nolimits _{k \in Z_{q}}{P_{ik}^{q}}\) for a given i∈V, by applying results of Section 3.1 (see, in particular, Eqs. 16–21). To make sure that a solution p=(p I ,p E ) to Eq. 25 locally maximizes the payoff function of each player in the player’s price (second order conditions), we proceed as follows: If both elements of p are smaller than \(\bar p\) and larger than c I and c E , respectively, we check if Eq. 26 is strictly smaller than zero for both players q∈{I,E}. Similarly, if exactly one element p q , q∈{I,E}, of p is at its upper bound and \(p_{\bar q} > c_{\bar q}\), we check if the opposing player \(\bar {q}\)’s second order condition Eq. 26 is strictly smaller than zero. For each element p q , q∈{I,E}, of p, however, that is at its upper bound, we check, if

  • \({\frac {\partial {\Pi }_{q} } {{\partial p_{q} }}} (\mathbf {p}) > 0\), or

  • \({\frac {\partial {\Pi }_{q} }{{\partial p_{q} }}} (\mathbf {p}) = 0\) and \(\frac {{\partial ^{2} {\Pi }_{q} }}{{\partial {p_{q}^{2}} }} (\mathbf {p}) < 0\), or

  • \(\frac {{\partial {\Pi }_{q} }}{{\partial p_{q} }}(\mathbf {p}) = 0\), \(\frac {{\partial ^{2} {\Pi }_{q} }}{{\partial {p_{q}^{2}} }}(\mathbf {p}) = 0\), and \(\frac {{\partial {\Pi }_{q} }}{{\partial p_{q} }}(p_{q} - \epsilon , p_{\bar q}) > 0\) for a sufficiently small 𝜖.

We proceed analogously if elements of p are at their lower bounds.

4.1 Computing Equilibrium Prices

As shown by Morrow and Skerlos (2011), natural (numerical) candidates to solving Eq. 25 include Newton’s method and fixed-point iteration approaches.Footnote 6 The authors show a specific fixed-point iteration to result in a reliable method for computing stationary points. In the following, we will have to adapt their approach to include upper and lower bounds on prices and, thus, be able to potentially find degenerate local price equilibria. The fixed-point iteration is based on reformulating ∂π q /∂ p q =0 by substituting Eqs. 16 and 20 and applying some straightforward algebraic operations:

$$ \left( \begin{array}{l} p_{I} \\ p_{E} \\ \end{array} \right) = \left( \begin{array}{l} c_{I} \\ c_{E} \\ \end{array} \right) + \left( \begin{array}{l} \zeta_{I}(p_{I}, p_{E}) \\ \zeta_{E}(p_{I}, p_{E}) \\ \end{array} \right), $$
(27)

where we define

$$ \left( \begin{array}{l} \zeta_{I}(p_{I}, p_{E}) \\ \zeta_{E}(p_{I}, p_{E}) \\ \end{array} \right) := \left( \begin{array}{l} (p_{I}-c_{I}) \frac{\sum\nolimits_{i \in V } { \pi(i) Z_{iI}^{2}(p_{I},p_{E})}}{\sum\nolimits_{i \in V } { \pi(i) Z_{iI}(p_{I},p_{E})}} \\ (p_{E}-c_{E}) \frac{\sum\nolimits_{i \in V } { \pi(i) Z_{iE}^{2}(p_{I},p_{E})}}{\sum\nolimits_{i \in V } { \pi(i) Z_{iE}(p_{I},p_{E})}} \\ \end{array} \right) + \left( \begin{array}{l} \frac{1}{s \beta} \\ \frac{1}{s \beta} \\ \end{array} \right). $$
(28)

In analogy to Morrow and Skerlos (2011), we will refer to Eq. 27 as a markup equation. This name is motivated by the fact that, on the right hand side of Eq. 27, a nonnegative value (markup) is added to the cost c q of player q∈{I,E}.

The combined conditions of Eq. 25 are, by definition, equivalent to the Mixed Complementary Problem (Munson 2000; Ferris and Pang 1997)

$$ c_{q} \leq p_{q} \leq \bar p \, \, \quad \bot \quad -\frac{{\partial {\Pi}_{q} }}{{\partial p_{q} }}(p_{I}, p_{E}), \qquad q\in \{I,E\}. $$
(29)

Because

$$-\frac{{\partial {\Pi}_{q} }}{{\partial p_{q} }}(p_{I}, p_{E})\! =\! s \beta\! \left( \sum\limits_{i \in V }{\pi(i) Z_{iq}(p_{I}, p_{E})} \right) \left[ p_{q} \,-\, c_{q} \,-\, \zeta_{q} (p_{I}, p_{E})\right], \quad q\in \{I,E\}, $$

and, because \(s \beta \sum \nolimits _{i \in V }{\pi (i) Z_{iq}(p_{I}, p_{E})} > 0\), the combined conditions of Eq. 25 are equivalently

$$ c_{q} \leq p_{q} \leq \bar p \quad \bot \quad p_{q} - c_{q} - \zeta_{q}(p_{I}, p_{E}), \qquad q\in \{I,E\}. $$
(30)

Define

$$ {\Gamma}_{q}(p):= \max \{ \min \{ p, \bar p \}, c_{q} \}, \qquad q\in \{I,E\}, $$
(31)

to be the Euclidean projection of \(p \in \mathbb {R}\) onto \([c_{q}, \bar p]\). The solutions to (30) are projections of the zeros of the Normal Map (Dirkse 1994). In this case,

$$p_{q} - c_{q} - \zeta_{q}({\Gamma}_{I}(p_{I}),{\Gamma}_{E}(p_{E}))=0, \qquad q\in \{I,E\}, $$

for any \((p_{I},p_{E}) \in \mathbb {R}^{2}\) if and only if (Γ I (p I ),Γ E (p E )) solves (30). Hence, we can do a fixed-point iteration

$$p_{q} \leftarrow c_{q} + \zeta_{q}({\Gamma}_{I}(p_{I}),{\Gamma}_{E}(p_{E})), \qquad q\in \{I,E\}, $$

but this iterates over \(\mathbb {R}^{2}\). We can, however, work with \([c_{I},\bar p] \times [c_{E}, \bar p]\) by projecting after updating:

$$ p_{q} \leftarrow {\Gamma}_{q} \left( c_{q} + \zeta_{q}(p_{I},p_{E}) \right) , \qquad q\in \{I,E\}, $$
(32)

given that the outer projection keeps iterates within \([c_{I},\bar p] \times [c_{E}, \bar p]\), Eq. 31.

In the remainder of this paper we will refer to fixed-point iteration (32) as FPI. Note that FPI may converge to stationary points that do not correspond to local price equilibria, as these points might relate to a local profit minimum of a player’s profit function when taking the price of the other player as given. Thus, we provide 625 starting price vectors, being equally dispersed over \([c_{I},\tilde p_{I}]\times [c_{E}, \tilde p_{E}]\), where \(\tilde p_{q}\), q∈{I,E}, is computed by applying Algorithm 1 (see Appendix A) to avoid starting FPI in areas of low profits and small partial profit derivatives of both players (recall that \(\lim _{p_{q} \to \infty } {{\Pi }_{q}} = 0\) and note that \(\lim _{p_{q} \to \infty } {\frac {\partial {\Pi }_{q}}{\partial p_{q}}} = 0\) for q∈{I,E}, see Appendix B). Basically, the algorithm gradually “cuts off” parts of the domain of prices until the profit of at least one of the players is larger than 10−4 at the resulting vector of maximal prices. We set the maximum number of FPI iterations in each call to 230.

4.2 Some Example Instances

Figure 3 presents the contour plot of an example instance without a local equilibrium in prices.Footnote 7 Note that we have \({\partial ^{2} {\Pi }_{I}} \slash {{\partial {p^{2}_{I}} }} > 0\) in the intersection point (p I =39.98, p E =118.83) of the incumbent and entrant contour (see Fig. 4). Furthermore, even if we increase the value of \(\bar p\) by an arbitrarily large value, this instance will not have an equilibrium in prices. However, it is easy to see that we can enforce a degenerate equilibrium in prices when lowering \(\bar p\) to - for example - a value of 80.

Fig. 3
figure 3

Contour plot of example instance without local equilibrium

Full size image
Fig. 4
figure 4

Profit functions of example instance without local equilibrium

Full size image
Fig. 5
figure 5

Contour plot of example instance with multiple local equilibria

Full size image

Similarly, Fig. 5 depicts the contour plot of an example instance with multiple local equilibria in prices (marked by circles), (10.87,12.43) and (12.27,16.05).Footnote 8 Figure 6 shows the corresponding profit functions of the players. It is easy to see that neither of the local equilibria represent a Nash equilibrium in prices. As before, we can enforce a degenerate equilibrium in prices when lowering \(\bar p\) to a sufficiently small value.

Fig. 6
figure 6

Profit functions of example instance with multiple local equilibria

Full size image

4.3 Computational Experiments

In order to analyze the performance of FPI, we have conducted a series of computational experiments with the location stage being excluded from the numerical tests by randomly selecting the players’ facility sites from the vertex set of the test networks. Test instances were run on a laptop with an Intel Core i7-4700MQ CPU, 2.4 GHz, 8GB system memory, running under the 64bit Windows 7 Professional operating system.

All test instances have been generated randomly with each parameter being drawn from a uniform distribution over a specific interval. The underlying networks are complete with edge length λ(u v)∈[1,50] for all [u,v]∈E and customer demand π(u)∈[0,100] for all u∈V. Moreover, c q ∈[1,10], q∈{I,E}. If not stated otherwise, we fix s to one (as frequently done in the literature), we set n=100, and we select \({a_{j}^{q}}\) from the interval [10,50] for all \(j \in Y_{r} \cup X_{p}\). All algorithms have been coded in C++.

Sensitivity parameters for price and distance typically range from zero to about 4 in the literature (for similar ranges of the other parameters as above), see, for example, Rhim and Cooper (2005), Benati and Hansen (2002), Thomadsen (2005), Benati (2000). We have therefore generated six sets of LPL instances with n=100 and 10,000 instances in each set. Table 1 presents the underlying ranges for the random generation of the corresponding parameters. Note that Theorem 2 holds for every instance of Set 1. Hence, the players’ payoff functions are concave and every local price equilibrium is a pure strategy Nash equilibrium in prices.

Table 1 Sets of test instances
Full size table

Figures 7 and 8 provide results on the convergence behavior of FPI (with potentially more than one starting price vector, as described in Section 4.1) for the test sets. Figure 7a shows that almost all calls of FPI converge to a local equilibrium in prices instantly (given that a local equilibrium exits). Only one instance of set 5 and two instances of set 6 required additional FPI calls with different starting price vectors. Two instances of set 5 and 28 instances of set 6 do not have a local price equilibrium (Fig. 7b, cf. also Section 4.2). The nonexistence of local price equilibria has been manually confirmed for all those instances.

Fig. 7
figure 7

Computational results - FPI convergence

Full size image
Fig. 8
figure 8

Computational results - FPI running time

Full size image

Computational times are rather small, as can be seen from Fig. 8. The figure presents average (Fig. 8a) and maximum (Fig. 8b) running times of FPI over the instances that have local price equilibria. It is apparent from these figures that a (combined) increase of the upper bounds on the sensitivity parameters α and β induces the need for more computational effort.

As to be expected (Morrow and Skerlos 2011), we conclude that FPI reliably converges to local price equilibria in case of their existence.

When analyzing the effects of increasing sensitivity parameters separately, we found that α’s effect on the potential nonexistence of local price equilibria is stronger than β’s influence. Hence, Fig. 9a takes a closer look at α’s effect on the existence of local equilibria. Here, we have increased both, the upper and lower bound on α, simultaneously for 1,000 test instances in 16 test sets for three different values of \(\bar p\) and β∈[0.015,0.5]. p and r have been fixed to 5. For each test set, α’s lower bound equals the upper bound of the prior test set, with a lower bound of zero in the first set. Increasing coefficients of spatial friction at first increase the amount of instances without local price equilibria. If we keep increasing α, however, instances tend to “regain” local equilibria. The latter statement holds for decreasing values of \(\bar p\) as well.

Fig. 9
figure 9

Existence of equilibria and influence of network size

Full size image

Figure 9b presents results on the effect of increasing network size on computational times. The plot is based on 1,000 test instances in six sets with α∈[0.015,1.5], β∈[0.015,1.5], \(\bar p = 150\) and r=p=5. Corresponding instances of different sets vary in network size and facility locations. We find an almost linear increase of average computational times over the network size.

5 Location Stage

Benati and Hansen (2002) provide examples, showing that the incorporation of random utility models into competitive location models may actually affect the optimal locations of facilities. It is the aim of this section to show that including an additional pricing game supports the same reasoning.

Let r=p=1, consider the network and the parameters of Fig. 10 (edge weights correspond to edge lengths) and set X 1={0} (gray vertex), α=1.974, \(\bar p = 42\), c I =2.87, c E =4.1 and s=1. For all potential entrant locations and three different price sensitivity levels, Table 2 presents the corresponding unique Nash equilibria in pricesFootnote 9 and entrant’s profits. As claimed above, we find a strong effect of β on the optimal entrant’s choice (marked by an asterisk in Table 2). While β≈0 induces co-location of the players, larger price sensitivity levels enforce differentiation of locations (in the case of the example instances).Footnote 10

Hence, we may conclude that price competition is worth being considered in competitive location models that utilize random utility models. This, of course, is only true if this is not necessarily accompanied by large computational costs. Therefore, in order to roughly analyze solution times and qualities of related heuristics, we have implemented two straight forward algorithms that apply FPI (Section 4.1) in C++. The development of more sophisticated approaches is left for future research. Especially, such approaches will need to provide adequate strategies to overcome FPI’s major drawback, i.e. the fact that (in the case of existence of at least one local price equilibrium) it determines one local price equilibrium only. In our analysis, we will refer to a entrant’s choice of r different locations as a solution to an instance of LPL, if there exists a corresponding local equilibrium in prices.

Fig. 10
figure 10

Example network

Full size image
Table 2 Optimal entrant locations under different price sensitivity levels
Full size table

The greedy algorithm proceeds as follows: Initialize it:=1 and Y 0:=∅ (none of the entrant’s facilities have been located). Repeat for all potential facility sites v∈V∖Y it−1: Set \(Y_{\text {\textit {it}}}=Y_{\text {\textit {it}}-1} \cup \{v\}\), determine a local equilibrium in prices (if an equilibrium exists) by calling FPI, calculate the corresponding entrant’s profit (if no equilibrium exists, assume the entrant’s profit to be -1) and reset Y it =Y it−1. Eventually, locate j in the candidate location v ′ yielding the maximal profit, \(Y_{\text {\textit {it}}}=Y_{\text {\textit {it}}-1} \cup \{v'\}\). If no local equilibrium in prices exists for any candidate location, choose a random (and feasible) vertex. If all facilities have been located, i.e. it=r, and a local equilibrium in prices exists, then stop. Otherwise, if it<r proceed by setting it=it+1 and locating the next facility in the same manner. If it=r and a local equilibrium in prices does not exist, keep generating random sets of entrant’s locations until a set with an existing local price equilibrium is found. If no such set is found within a time limit t m a x , then stop.

Additionally, we have implemented a basic tabu search heuristic (cf. Glover and Laguna 1997, for an introduction to tabu search) with the following neighborhood structure: For a set of entrant’s locations Y r and for every i∈Y r and j∈V∖Y r , generate \(Y_{r} \setminus \{i\} \cup \{j\}\) (1-interchange moves, denoted by \((\bar i,j)\)). Evaluate each set of locations by calling FPI as in the greedy algorithm. Execute the best non-tabu move. Additionally, apply a simple aspiration criterion, i.e. allow a tabu move if it results in a solution with an objective value that is better than the currently best known entrant’s profit. If no neighboring set of locations has a local equilibrium in prices, choose a random neighbor. If a move \((\bar i,j)\) is executed, record the opposing move \((\bar j,i)\) and, additionally, the same move as tabu for tl iterations. Start the procedure by selecting a random set of p different locations. If circling around a local optimum is detected, restart the search process at a randomly generated set of locations (diversification). Terminate the tabu search heuristic after a fixed number of maxit iterations or if the same local optimum has been found maxloc times.

We have randomly generated a total of 400 test instances as described in Section 4.3, with λ(u v)∈[1,50] for all [u,v]∈E, π(u)∈[0,100] for all u∈V, s=1, \(\bar p = 150\), c q ∈[1,10], \({a_{j}^{q}} \in [30,40]\) for all j∈V and q∈{I,E}. The test instances are grouped with respect to their (randomly drawn) sensitivity parameters, as well as their network sizes and the number of players’ facilities; see Tables 3 and 4. Five instances were generated in each group. The incumbent’s locations were randomly drawn from the vertex set. The tabu search parameters have been fixed to t l=25, m a x i t=100 and m a x l o c=4.

Table 3 Average solution quality of location heuristics
Full size table
Table 4 Average solution time of location heuristics (minutes)
Full size table

Table 3 depicts results on the quality of the heuristics’ solutions. Solution quality is measured in terms of objective function values (at the corresponding local price equilibria) in relation to the objective function values of the best solutions found by complete enumeration over all potential location settings. However, as before, we apply FPI to determine a local price equilibrium for each of these location settings, so that the enumeration algorithm is not guaranteed to find optimal solutions. All cell entries in Table 3 are average values over the corresponding group of test instances. Table 4 presents the corresponding average computational times.

These basic results indicate that our observations of Section 4.3 (reliable convergence behavior of FPI within rather small computational times) result in standard heuristics tending to determine high quality solutions within acceptable time, even for “challenging” ranges of the sensitivity parameters. Thus, as claimed above, it seems to be reasonable to include price competition into basic location problems that utilize random utility models. As to be expected, the tabu search heuristic outperforms the simple greedy algorithm in terms of solution quality. Additionally, note that we did not encounter test instances without any locational setting with an existing local price equilibrium.

6 Conclusion

In this paper, we have discussed a competitive location problem – the (r|X p )-medianoid problem – with an additional pricing stage (price competition). As in Benati and Hansen (2002), we have assumed customers to be utility maximizers and we have applied the well known multinomial logit approach to model their behavior. Hence, customer behavior has been assumed to be probabilistic.

We have provided insights into the existence of (local) price equilibria and the computational complexity of the problem. Additionally, we have provided examples of problem instances with fixed location sets of the players, that demonstrate the potential non-existence of price equilibria and the case of multiple local equilibria. We have adapted a reliable fixed-point iteration method to quickly determine local equilibria in prices, assuming that the players’ locations are given. Based on this numerical method, we have presented first insights into heuristic algorithms to solving the location problem itself. Finally, we have shown that different price sensitivity levels of customers affect optimal entrant’s locations

Future research may focus on several issues. First, adequate strategies to finding global equilibria (Nash equilibria) in prices may be developed. Furthermore, the model may be generalized in multiple ways. For example, one may let the players charge different prices in different locations. Research may also focus on the incorporation of other, more general, random utility models and the estimation of the corresponding parameters from real world data (see, for example, Cherchi and de Dios Ortúzar, 2008; de Grange et al. 2015; Yáñez et al. 2011). Other than the multinomial logit model, such models may, for instance, take account of flexible substitution patterns, as their non-consideration is one of the most limiting factors of our model (cf. already Benati and Hansen 2002). Additionally, more general existence and uniqueness conditions on price equilibria may be derived and analyzed. Here, one may also analyze the economical reasons and effects of nonexistence of price equilibria.