Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Some competitive location models attempt to find the locations of facilities at which profit is maximized. Profit is strongly affected by both the locations of facilities of the competing firms and the price set by firms in each customer area. If the firms enter simultaneously in the market, the maximization of their profit can be seen as a two-stage game. In the first stage, the firms simultaneously choose their facility locations. In the second stage, the firms will compete on price. The division into two stages is motivated by the fact that the choice of location is usually prior to the decision on price. Observe that location decision is relatively permanent whereas price decision can be easily changed. The two stage game can be reduced to a location game if there exists a price equilibrium in the second stage which is determined by the locations chosen by the firms in the first stage. Once the facility locations are chosen, the firms would set the equilibrium prices, and then their profit would be determined. Thus, the location-price problem could be considered as a game in which firms decide only on facility location. Other similar location games where the payoffs are given by market share or profit can be seen in [1, 7, 17, 20, 27].

The existence of a price equilibrium in the second stage of the game depends on the price policy to be considered, among other factors. Most of the papers dealing with the location-price problem consider two competing firms under any of the two following policies: mill pricing and delivered pricing. With mill pricing, a price equilibrium rarely exists (see for instance [4, 13, 14, 24]). Then the location-price problem has been studied as a location game by taking prices as parameters. For two competing firms on a tree network, it has been proved that a Nash equilibrium (NE) exists with locations at the median nodes if both firms set equal prices (see [9, 10]). For more than two firms, a location NE on a tree may not exist for equal prices as it has been proved in [11]. The profit maximization problem for an entering firm has been studied on a general network (see [26, 28]), but existence of a Nash equilibrium on a general network has not been proved when firms compete simultaneously on location. With delivered pricing, a price equilibrium always exists under quite general conditions. The existence of a price equilibrium was shown for the first time by Hoover [19], who analyzed spatial discriminatory pricing for firms with fixed locations and concluded that the local price set by a firm serving a particular market will be constrained by the delivery cost of the other firms serving that market. In situations where demand elasticity is ‘not too high’, the equilibrium price at a given market is equal to the delivery cost of the firm with the second lowest delivery cost. This result was extended later to spatial duopoly (see [21, 22]) and to spatial oligopoly for different types of location spaces (see [9, 14]).

Under delivered pricing, the equilibrium prices are usually determined by the locations of the facilities, then the location-price problem can be reduced to a location game. This location game has been scarcely studied in the location literature. For completely inelastic demand, the existence of a location Nash equilibrium has been proved. In a duopoly with constant marginal production costs, Lederer and Thisse [22] showed that a location Nash equilibrium exists which is a global minimizer of the social cost. The social cost is defined as the total delivered cost if each customer were served with the lowest marginal delivered cost. In oligopoly, the same result is obtained in [6], where the authors present a model in which firms compete with delivery pricing and locate single facilities on a network of connected but spatially separated markets. If demand is price sensitive or marginal production costs are not constant, the minimizers of social cost may not be a location NE (see [16, 18]). The profit maximization problem for an entering firm has been studied with price sensitive demand (see [15]), but existence of a location Nash equilibrium has not been proved when firms compete simultaneously on location.

The problem of minimizing the social cost on a network has been studied for two competing firms when marginal delivered costs are concave. This problem is equivalent to the r-median problem if the marginal delivered cost from each site location to each demand point is the same for all competing firms (see [25]). There is an extensive literature on algorithms to solve the r-median problem on networks which can be used to find a location NE (see for instance [2]). If marginal delivery cost from each site location to each demand point is different for each competitor the problem has been solved by using a Mixed Integer Linear Programming (MILP) formulation (see [25]). The problem of minimizing the social cost on a plane has been solved for two competing firms which locate single facilities (see [5, 12]).

The aim of this chapter is to extend the main results on the above mentioned location-price problem with delivered pricing to a general framework where there are more than two competing firms, each of them locating multiple facilities. The problem is studied for constant and variable demand which is located at the nodes of a transportation network. The chapter is organized as follows: In Sect. 2, it is shown how the location-price problem is reduced to a game with decisions on location. In Sect. 3, the existence and determination of location NE is studied for constant demand. In Sect. 4, the existence and determination of location NE is studied for variable demand. Finally, the selection of a location NE when there are multiple location NE is discussed in Sect. 5.

2 The Location-Price Problem

Let us consider N firms that sell an homogeneous product and compete for demand in a certain region. The firms manufacture and deliver the product to the customers, which buy from the firm that offers the lowest price. The firms have to choose their facility locations in some predetermined location space. Once their facility locations are fixed, the firms will set delivered prices at each customer area. Thus, each firm has to make decisions on location and price in order to maximize its profit.

As location space we will take a transportation network G = (V, E, l), where V is the set of nodes, E is the set of edges, and \(l: E \rightarrow \mathbb{R}\) with l(e) being the length of edge e. Distance between two points a and b in the network is measured as the length of the shortest path linking the two points and it is denoted by d(a, b). It is assumed that customers are grouped at the nodes, then the set of customer areas is given by V = { 1, 2, …, m}. The firms are supposed to locate their facilities at points on the network, then the set of location candidates for each firm is L = V ∪ E.

The following notation will be used:

Indices

$$\displaystyle{\begin{array}{lll} n&\mbox{ index of the firms, $n = 1,\ldots,N$}\\ k &\mbox{ index of the nodes, $k = 1,\ldots, m.$}\\ \end{array} }$$

Data

$$\displaystyle{\begin{array}{ll} q_{k}(p) &\mbox{ demand function at node $k$} \\ c_{x}^{n} &\mbox{ marginal production cost of firm $n$ at location $x$} \\ t_{xk}^{n} &\mbox{ marginal transportation cost of firm $n$ from location$x$} \\ &\mbox{ to node $k$} \\ C_{xk}^{n} = c_{x}^{n} + t_{xk}^{n}&\mbox{ marginal delivered cost (or minimum delivered price)} \\ &\mbox{ of firm $n$}\\ &\mbox{ from location $x$ to node $k$}\\ \end{array} }$$

Decision variables

$$\displaystyle{\begin{array}{ll} X^{n} &\mbox{ set of facility locations for firm $n$} \\ p_{k}^{n}&\mbox{ price the firm $n$ sets at node $k$}\\ \end{array} }$$

Miscellaneous

$$\displaystyle{\begin{array}{ll} C_{k}^{n}(X^{n}) = min\left \{C_{xk}^{n}: x \in X^{n}\right \}&\mbox{ minimum price the firm $n$ can set at node $k$} \\ C_{k}(X) = min\{C_{xk}: x \in X\} &\mbox{ minimum price the facilities in the set $X$} \\ &\mbox{ can set at node $k$} \end{array} }$$

Let q k (p) be continuous and strictly decreasing at all p in [0, p k max], where p k max is the maximum price that customers in market k are willing to pay for the product. We consider that the demand function q k (p) in market k may be different from the demand function in other markets. In order to make competition effective in each market k, we assume that the competing firms are able to price below the maximum price, i.e. C k n(X n) < p k max for all X n, n = 1, 2, …, N.

Marginal delivered costs are supposed to be independent of the amounts delivered and firms use linear prices. Thus, the profit any firm gets from market k, serving the full market at price p, is Π k (p) = q k (p)(p − c), where c is the marginal delivered cost of the firm. Then the monopoly price in market k is the optimal solution to the problem:

$$\displaystyle\begin{array}{rcl} \max \ \{\varPi _{k}(p): c \leq p \leq p_{k}^{max}\}& & {}\\ \end{array}$$

and it will be denoted by p k mon(c).

The following assumptions concerning the previous maximization problem are considered:

Assumption 1

Π k (p) is a unimodal quasi-concave function in [0,p k max ].

Assumption 2

c< p k mon (c), for each c ≥ 0.

Assumption 3

p k mon (c) is a continuous increasing function at all c in [0,p k max ].

The first assumption guarantees the existence of a unique maximizer of the profit function, and therefore a unique monopoly price for each c value. The second assumption avoids trivial cases in which the optimal price is the marginal delivered cost, and consequently the profit is zero. The third assumption will be used to prove a convexity property of the maximum profit. There exists a variety of demand functions for which the previous assumptions are verified. Some examples are shown in Table 1.

Table 1 Some demand functions and their monopoly prices
Full size table

The previous location-price problem can be seen as a two-stage game. In the first stage the firms compete on location. In the second stage, once the facility locations are fixed, the firms will compete on price.

2.1 The Second Stage of the Game

First, we will show the existence of a unique price equilibrium for any set of facility locations. Let us consider that customers do not have any preference concerning the supplier and they buy from the firm that offers the lowest price. It is assumed that each firm cannot offer a price below its marginal delivered cost and each facility can supply all demand placed on it. Thus, each firm n will set a price at node k which is greater than, or equal to, C k n(X n) for any set of facility locations X n, n = 1, 2…, N.

If two firms offer a minimum price at node k, the one with the minimum marginal delivered cost can lower its price and it obtains all the demand in node k. Then we consider that ties in price are broken in favour of the firm with the lowest marginal delivered cost. If the tied firms have the same marginal delivered cost in node k, no tie breaking rule is needed to share demand at node k because they will obtain zero profit from node k as a result of price competition.

In the long-term competition, customers at node k will not buy from firm n if C k n(X n) > min{C k u(X u): u = 1, 2, …, N}. Therefore, each node will be served by the firm with the minimum marginal delivered cost and such a firm will set a price which maximizes its profit. Let X = (X 1, X 2, …, X N) denote the set of fixed facility locations. For n = 1, 2, …, N, let \(C_{k}^{com}(X^{n}) =\min \left \{C_{xk}^{u}: x \in X^{u},u = 1,\ldots,N,u\neq n\right \}\) denote the minimum delivered cost of the competitors of firm n.

The price competition is as follows:

  1. 1.

    If C k n(X n) < C k com(X n), then firm n obtains a maximum profit from node k by offering a price equal to the optimal solution of the following problem:

    $$\displaystyle\begin{array}{rcl} Max\{\varPi _{k}^{n}(p) = q_{ k}(p)(p - C_{k}^{n}(X^{n})): C_{ k}^{n}(X^{n}) \leq p \leq C_{ k}^{com}(X^{n})\}& & {}\\ \end{array}$$

    The optimal solution to this problem is unique and it depends on the set of facility locations X. The solution is given by:

    $$\displaystyle\begin{array}{rcl} \hat{p}_{k}^{n}(X) = \left \{\begin{array}{lll} p_{k}^{mon}(C_{ k}^{n}(X^{n}))&if &p_{ k}^{mon}(C_{ k}^{n}(X^{n})) <C_{ k}^{com}(X^{n})\\ & & \\ C_{k}^{com}(X^{n}) &if &p_{k}^{mon}(C_{k}^{n}(X^{n})) \geq C_{k}^{com}(X^{n})\end{array} \right.& & {}\\ \end{array}$$
  2. 2.

    If C k n(X n) ≥ C k com(X n), then firm n obtains zero profit from node k. In this case, firm n sets a price \(\hat{p}_{k}^{n}(X) = C_{k}^{n}(X^{n})\) to make its competitors obtain a minimum profit from node k.

It is clear that no firm n can get a greater profit from node k by changing the price \(\hat{p}_{k}^{n}(X)\) while the other firms keep such prices. Then \(\hat{p}_{k}^{n}(X)\), n = 1, 2, …, N, are the unique equilibrium prices in market k.

2.2 The First Stage of the Game

Let us assume that for any fixed set X = (X 1, X 2, …, X N), the firms will set the equilibrium prices \(\hat{p}_{k}^{n}(X)\), n = 1, 2, …, N. Observe that price competition lead to each firm n will monopolize a group of nodes from which the firm gets a positive profit. This group of nodes not only depends on the locations of the facilities of firm n, but it also depends on the locations of the facilities of its competitors. Such group of nodes is denoted by M n(X) and it is given by:

$$\displaystyle\begin{array}{rcl} M^{n}(X) =\{ k: C_{ k}^{n}(X^{n}) <C_{ k}^{com}(X^{n})\}& & {}\\ \end{array}$$

Then, the profit obtained by firm n is:

$$\displaystyle\begin{array}{rcl} \varPi ^{n}(X) =& \sum \limits _{ k=1}^{m}q_{ k}(\hat{p}_{k}^{n}(X))(\hat{p}_{ k}^{n}(X) - C_{ k}^{n}(X)) = & {}\\ & \sum \limits _{k\in M^{n}(X)}q_{k}(\hat{p}_{k}^{n}(X))(\hat{p}_{k}^{n}(X) - C_{k}^{n}(X))& {}\\ \end{array}$$

If the competing firms set the equilibrium prices, the location-price problem can be seen as a location game LG = { N, X n, Π n: n = 1, …, N}, where N is the number of firms (players), X n represents the set of facility locations chosen by firm n, and Π n is the payoff firm n obtains. This game captures the idea that, when firms select their locations, they all anticipate the consequences of their choice on price.

For simplicity, given X = (X 1, X 2, …, X N), we will use the notation X = (X n, X −n), where X −n is the set of locations of the competing firms but n. Then a location Nash equilibrium (NE) is defined as a set of locations \(\hat{X} = (\hat{X}^{1},\hat{X}^{2},\ldots,\hat{X}^{N})\) such that for any n it is verified that:

$$\displaystyle\begin{array}{rcl} \varPi ^{n}(\hat{X}^{n},\hat{X}^{-n}) \geq \varPi ^{n}(X^{n},\hat{X}^{-n}),& & \forall X^{n} {}\\ \end{array}$$

In the following we will study the problem of existence of location NE, and the problem of finding such equilibria if they exist. We will distinguish between essential and non essential products.

3 Location Nash Equilibria with Essential Products

Let us assume that firms sell essential products. This means that demand does not change when price changes. Then the amount of demand at each node k is given by a constant function, q k (p) = Q k , k = 1, …, m.

3.1 Existence of NE

For constant demand functions, the existence of a location NE can be proved by using the concept of social cost. The social cost is defined as the total cost incurred to supply demand to customers if each customer would pay for the product the minimum delivered cost. Then, for any fixed set of locations X = (X 1, X 2, …, X n), the social cost is given by:

$$\displaystyle\begin{array}{rcl} S(X) =\sum _{ k=1}^{m}Q_{ k}\min \left \{C_{k}^{1}(X^{1}),C_{ k}^{2}(X^{2}),\ldots,C_{ k}^{N}(X^{N})\right \}& & {}\\ & & {}\\ \end{array}$$

Firstly, it is shown that the profit obtained by any firm is the total cost that would be experienced by its competitors serving the entire market with the minimum delivered cost minus the social cost. Secondly, a characterization of location NE is obtained. Finally, the existence of a location NE is proved.

Property 1

If the firms set the equilibrium prices in each market, then for n = 1,…,N, it is verified that:

$$\displaystyle\begin{array}{rcl} \varPi ^{n}(X)& =& \sum _{ k=1}^{m}C_{ k}^{com}(X^{n})Q_{ k} - S(X) {}\\ \end{array}$$

Proof

Since q k (p) = Q k , the equilibrium prices are given by:

$$\displaystyle\begin{array}{rcl} \hat{p}_{k}^{n}(X) = \left \{\begin{array}{ll} C_{k}^{com}(X^{n})&\text{if }C_{ k}^{n}(X^{n}) <C_{ k}^{com}(X^{n}) \\ C_{k}^{n}(X^{n}) &otherwise. \end{array} \right.& & {}\\ \end{array}$$

Then the profit obtained by firm n can be expressed as follows:

$$\displaystyle\begin{array}{rcl} \varPi ^{n}(X)& =& \sum _{ k\in M^{n}(X)}Q_{k}\left (C_{k}^{com}(X^{n}) - C_{ k}^{n}(X^{n})\right ) {}\\ & =& \sum _{k\in M^{n}(X)}Q_{k}\left (C_{k}^{com}(X^{n}) - C_{ k}^{n}(X^{n})\right ) {}\\ & & +\sum _{k\notin M^{n}(X)}Q_{k}C_{k}^{com}(X^{n}) -\sum _{ k\notin M^{n}(X)}Q_{k}C_{k}^{com}(X^{n}) {}\\ & =& \sum _{k=1}^{m}Q_{ k}C_{k}^{com}(X^{n}) -\sum _{ k=1}^{m}Q_{ k}\min \left \{C_{k}^{n}(X^{n}),C_{ k}^{com}(X^{n})\right \} {}\\ & =& \sum _{k=1}^{m}Q_{ k}C_{k}^{com}(X^{n}) - S(X). {}\\ \end{array}$$

 □ 

Property 2

\(\hat{X}\) is a location NE if and only if for n = 1,…,N, it is verified that:

$$\displaystyle\begin{array}{rcl} S(\hat{X}^{n},\hat{X}^{-n}) \leq S(X^{n},\hat{X}^{-n})& & \forall X^{n}. {}\\ \end{array}$$

Proof

Note that \(\hat{X}\) is a location NE if and only if for n = 1, 2, …, N, it is verified that:

$$\displaystyle\begin{array}{rcl} \varPi ^{n}(\hat{X}^{n},\hat{X}^{-n}) \geq \varPi ^{n}(X^{n},\hat{X}^{-n})& & \forall X^{n}. {}\\ \end{array}$$

From Property 1, these inequalities are equivalent to the following ones:

$$\displaystyle\begin{array}{rcl} S(\hat{X}^{n},\hat{X}^{-n}) \leq S(X^{n},\hat{X}^{-n})& & \forall X^{n}. {}\\ \end{array}$$

 □ 

Property 3

Any global minimizer of S(X) is a location NE.

Proof

It follows from Property 2. □ 

The existence of a global minimizer of social cost is proved by considering the following assumptions:

Assumption 4

For n = 1,2,…,N the marginal production cost, c x n , is a positive concave function when x varies along any edge in the network, and it is independent of the quantity produced.

Assumption 5

For n = 1,2,…,N the marginal transportation cost, t xk n , is a positive, concave and increasing function with respect to the distance from x to each node k.

Concavity of marginal production cost and marginal transportation cost is realistic in certain situations as it has been remarkable by many authors (see for instance [20, 22, 27]). Under such assumptions, as d xk is a concave function at x, for any node k and x varying along any fixed edge, it is verified that the marginal delivered cost, C xk n = C x n + t xk n, is also a concave function for any node k and x varying along any fixed edge.

Property 4

Under Assumptions  4 and  5 , there exists a set of nodes which is a global minimizer of the social cost.

Proof

Let X = (X 1, X 2, …, X N) be an arbitrary set of facility locations on the network. If x ∈ X n is not a node, then x is in the interior of some edge e = (a, b) ∈ E. Assume that all points in X are fixed, but the point x, which varies on the edge e. Under Assumptions 1 and 2, it results that the minimum price to serve market k, \(\min \left \{C_{k}^{1}(X^{1}),C_{k}^{2}(X^{2}),\ldots,C_{k}^{N}(X^{N})\right \}\), is a concave function when x varies on the edge e and the other locations are fixed. Since the sum of weighted concave functions, with non-negative weights, is also concave, it follows that the social cost, S(X), is concave when x varies on the edge e and the other locations are fixed. Therefore, the social cost reaches its minimum value on edge e for x = a or x = b.

Therefore, if we replace each non-node point in X by the corresponding minimizer node of the social cost when the other locations of the facilities are fixed, we will obtain sets of nodes V 1, V 2, …, V N for which S(V 1, V 2, …, V N) ≤ S(X 1, X 2, , …, X N). Consequently, there exists a set of nodes \(\hat{V } = (V ^{1},V ^{2},\ldots,V ^{N})\) which minimizes the social cost. □ 

3.2 Finding a Location NE

From Property 4, it follows that a location NE can be found by minimizing the social cost on the set of nodes. For any set of nodes X = (X 1, X 2, …, X N) every set X n can be represented by a vector x n = (x 1 n, x 2 n, …, x m n) with components:

$$\displaystyle\begin{array}{rcl} x_{i}^{n} = \left \{\begin{array}{lll} 1&&\text{if node }i \in X^{n} \\ 0&&otherwise. \end{array} \right.& & {}\\ \end{array}$$

Let x = (x 1, x 2, …, x N). With this representation of X, the social cost S(x) is given by the optimal value of the following optimization problem:

$$\displaystyle\begin{array}{rcl} SC(x) =& \text{Min}& \sum \limits _{k=1}^{m}Q_{ k}\left (\sum \limits _{i=1}^{m}C_{ ik}^{1}z_{ ik}^{1} +\sum \limits _{ i=1}^{m}C_{ ik}^{2}z_{ ik}^{2} +\ldots +\sum \limits _{ i=1}^{m}C_{ ik}^{N}z_{ ik}^{N}\right ) \\ & \text{s.t.} & \sum \limits _{i=1}^{m}z_{ ik}^{1} +\sum \limits _{ i=1}^{m}z_{ ik}^{2} +\ldots +\sum \limits _{ i=1}^{m}z_{ ik}^{N} = 1;\ k = 1,\ldots,m {}\end{array}$$
(1)
$$\displaystyle\begin{array}{rcl} & & z_{ik}^{n} \leq x_{ i}^{n};n = 1,2,\ldots,N;\ i,k = 1,2,\ldots,m \\ & & z_{ik}^{n} \in \left \{0,1\right \};\ n = 1,2,\ldots,N;\ i,k = 1,2,\ldots,m{}\end{array}$$
(2)

Constraints (1) mean that for any k, only one variable z ik n will be equals to 1, the one corresponding to the minimum delivered cost from the locations of the facilities to node k. Constraints (2) mean that variable z ik n may take the value 1 if x i n = 1.

For each k, note that the optimal solution to the previous problem is obtained by assigning the value 1 to one variable z ik n for which the following two conditions are verified: C ik n = min{C jk n: j = 1, 2, …, m and x j n = 1} and C ik n ≤ C k com(X n). The value 0 is assigned to the other variables.

Therefore, the problem of minimizing the social cost when locations are nodes becomes into the problem:

$$\displaystyle\begin{array}{rcl} (SCM):& \text{Min}\ & \sum \limits _{k=1}^{m}Q_{ k}[\sum \limits _{n=1}^{N}\sum \limits _{ i=1}^{m}C_{ ik}^{n}z_{ ik}^{n}] \\ & \text{s.t.} & \sum \limits _{n=1}^{N}\sum \limits _{ i=1}^{m}z_{ ik}^{n} = 1;\ k = 1,\ldots,m{}\end{array}$$
(3)
$$\displaystyle\begin{array}{rcl} & & z_{ik}^{n} \leq x_{ i}^{n};\ n = 1,\ldots,N;\ i,k = 1,\ldots,m{}\end{array}$$
(4)
$$\displaystyle\begin{array}{rcl} & & \sum \limits _{i=1}^{m}x_{ i}^{n} = r_{ n};\ n = 1,\ldots,N \\ & & z_{ik}^{n},x_{ i}^{n} \in \left \{0,1\right \};\ n = 1,\ldots,N;\ i,k = 1,\ldots,m{}\end{array}$$
(5)

Constraints (5) show that each firm n selects r n facility locations, where r n is the number of facilities to be located by firm n. Let \(\hat{x}_{i}^{n}\) be the optimal values of variables x i n, then a location NE is given by \(\hat{X} = (\hat{X}^{1},\hat{X}^{2},\ldots,\hat{X}^{N})\) where \(\hat{X}^{n} =\{ i:\hat{ x}_{i}^{n} = 1\}\), n = 1, 2, …, N.

Problem (SCM) can be solved by any standard ILP-optimizer (Xpress, Cplex, …). However, computational difficulties may occur when the number of binary variables, which is Nm(m + 1), is large. To solve more efficiently problem (SCM), the constraints \(z_{ik}^{n} \in \left \{0,1\right \}\) can be replaced by z ik n ≥ 0. Note that for both sets of constraints the same value of SC(x) is obtained. Therefore, an optimal solution of (SCM) can be obtained by talking either the sets of constraints \(z_{ik}^{n} \in \left \{0,1\right \}\), or the set of constraints z ik n ≥ 0.

3.3 Firms with Equal Marginal Delivered Costs

If the marginal delivered costs are equal for all the firms, C ik n = C ik for n = 1, 2, …, N, the previous formulation of the social cost minimization problem can be simplified. In fact, once the facility locations are fixed, note that any node k is served from the facility with the minimum delivered cost. Since the marginal delivered cost from each node is the same for all the firms, the minimum delivered cost to node k only depends on the nodes where the facilities are located, no matter which of the firms is the owner of the facility. Thus, if we consider the following variables:

$$\displaystyle\begin{array}{rcl} x_{i} = \left \{\begin{array}{lll} 1&&\text{if a facility is located at node}\ i\\ 0 & &otherwise \end{array} \right.& & {}\\ z_{ik} = \left \{\begin{array}{lll} 1&&\text{if node}\ k\ \text{is served from node}\ i\\ 0 & &otherwise \end{array} \right.& & {}\\ \end{array}$$

then the social cost minimization problem becomes into the following problem:

$$\displaystyle\begin{array}{rcl} (SCM1):& \text{Min}& \sum \limits _{k=1}^{m}Q_{ k}[\sum \limits _{i=1}^{m}C_{ ik}z_{ik}] \\ & \text{s.t.} & \sum \limits _{i=1}^{m}z_{ ik} = 1;\ k = 1,\ldots,m{}\end{array}$$
(6)
$$\displaystyle\begin{array}{rcl} & & z_{ik} \leq x_{i};\ i,k = 1,\ldots,m{}\end{array}$$
(7)
$$\displaystyle\begin{array}{rcl} & & \sum \limits _{i=1}^{m}x_{ i} = r \\ & & z_{ik} \geq 0,x_{i} \in \left \{0,1\right \};\ i,k = 1,\ldots,m{}\end{array}$$
(8)

Constraints (6) mean that each node will be served by one facility, the one with the minimum delivered cost. Constraints (7) show that node k can be served from node i if x i  = 1. Constraint (8), where r = r 1 + … + r N , represents the total number of facilities to be located. The constraints \(z_{ik} \in \left \{0,1\right \}\) have been replaced by the constraints z ik  ≥ 0. The number of variables is now equal to m(m + 1), where m of them are binary and the other are non negative. Then large size problems can be solved by using standard optimizers. Observe that (SCM1) is a formulation of the well known r−median problem (see [2, 23]).

If \(\hat{X}\) is the set of nodes corresponding to the optimal solution \(\hat{x}= (\hat{x} _{1},\ldots,\hat{x}_{m})\) of problem (SCM1), i.e., \(\hat{X}=\{ i: \hat{x} _{i} = 1\}\), then any partition \((\hat{X} ^{1}, \hat{X} ^{2},\ldots, \hat{X} ^{N})\) of \(\hat{X}\) verifying \(\vert \hat{X} ^{n}\vert = r_{n}\), n = 1, 2, …, N, is a location NE. This is true due to \(\hat{X}\) is a global minimizer of social cost. Consequently, there exist a large number of location NE. The problem of selecting one of such equilibria is considered in Sect. 5.

4 Location Nash Equilibria with Non Essential Products

Let us now consider that demand is sensible to price. This happens for products considered as not necessary to the customer. The demand at each node k is given by a function q k (p). We first prove a convexity property of the maximum profit that is obtained by any firm at each node. This property will be used to show that for any firm n, there is a set of optimal locations at the nodes for any fixed locations of its competitors.

4.1 Convexity of the Maximum Profit at a Node

Let us consider that the locations of the facilities of firm n, X n, may change, but the locations of the facilities of its competitors are fixed. Given a node k, for simplicity let c = C k n(X n) and c k com = C k com(X n). The maximum profit of firm n at node k, as a function of the marginal delivered cost, is given by:

$$\displaystyle\begin{array}{rcl} \varPi _{k}^{n}(c) = \left \{\begin{array}{lcl} \max \{q_{k}(p)(p - c): c \leq p \leq c_{k}^{com}\}&if &c <c_{ k}^{com} \\ 0 &if &c \geq c_{k}^{com} \end{array} \right.& & {}\\ \end{array}$$

Since p k mon(c) is a continuous increasing function (Assumption 3), it follows that p k mon(c) < c k com if and only if c < c k for someone threshold value c k . Then the maximum profit in market k is given by the following function (see Fig. 1):

$$\displaystyle\begin{array}{rcl} \varPi _{k}^{n}(c) = \left \{\begin{array}{lccl} q_{k}(p_{k}^{mon}(c))(p_{k}^{mon}(c) - c)&&if &c <c_{k} \\ q_{k}(c_{k}^{com})(c_{k}^{com} - c) &&if &c_{k} \leq c <c_{k}^{com} \\ 0 &&if &c_{k}^{com} \leq c \end{array} \right.& & {}\\ \end{array}$$
Fig. 1
figure 1

Maximum profit function

Full size image

Observe that Π k n(c) depends on the demand function q k (p) and it can be nonlinear in the interval [0, c k ], but it is always linear in [c k , c k com].

Property 5

Π k n (c) is a decreasing convex function in [0,p k max ].

Proof

It is clear that function Π k n(c) is decreasing at c, so we will show that it is convex. Let c 1 and c 2 be in [0, p k max], and c λ  = λ c 1 + (1 −λ)c 2, 0 < λ < 1. For simplicity, let p 1 = p k mon(c 1), p 2 = p k mon(c 2), p λ  = p k mon(c λ ). From Assumption 3, as c 1 < c λ  < c 2, it follows that p 1 < p λ  < p 2.

We have to prove that Π k n(c λ )  ≤ λ Π k n(c 1)+(1 −λ)Π k n(c 2), for which we consider the three following possible cases:

  1. i)

    If c λ  < c k , then:

    $$\displaystyle\begin{array}{rcl} \varPi _{k}^{n}(c_{\lambda })& =& q_{ k}(p_{\lambda })(p_{\lambda } - c_{\lambda }) = q_{k}(p_{\lambda })(p_{\lambda } -\lambda c_{1} - (1-\lambda )c_{2}) {}\\ & =& \lambda q_{k}(p_{\lambda })(p_{\lambda } - c_{1}) + (1-\lambda )q_{k}(p_{\lambda })(p_{\lambda } - c_{2}) {}\\ \end{array}$$

    Since c λ  < c k and c 1 < p k mon(c 1) = p 1 < p λ , it follows that c 1 < p λ  < c k com, and therefore q k (p λ )(p λ − c 1) ≤  Π k n(c 1). Since p λ  < c k com, it is verified that q k (p λ )(p λ − c 2) ≤  Π k n(c 2). Then we obtain:

    $$\displaystyle{\varPi _{k}^{n}(c_{\lambda }) \leq \lambda \varPi _{ k}^{n}(c_{ 1}) + (1-\lambda )\varPi _{k}^{n}(c_{ 2})}$$
  2. ii)

    If c k  ≤ c λ  < c k com, then:

    $$\displaystyle\begin{array}{rcl} \varPi _{k}^{n}(c_{\lambda })& =& q_{ k}(c_{k}^{com})(c_{ k}^{com} - c_{\lambda }) = q_{ k}(c_{k}^{com})(c_{ k}^{com} -\lambda c_{ 1} - (1-\lambda )c_{2}) {}\\ & =& \lambda q_{k}(c_{k}^{com})(c_{ k}^{com} - c_{ 1}) + (1-\lambda )q_{k}(c_{k}^{com})(c_{ k}^{com} - c_{ 2}). {}\\ \end{array}$$

    Since c 1 < c λ and c λ  < c k com, then c 1 < c k com. Therefore, q k (c k com)(c k com − c 1) ≤  Π k n(c 1). On the other hand, we have that q k (c k com)(c k com − c 2)  ≤ Π k n(c 2) if c 2 < c k com and q k (c k com)(c k com − c 2) ≤  0 ≤ Π k n(c 2) if c 2 ≥ c k com. Then we obtain:

    $$\displaystyle{\varPi _{k}^{n}(c_{\lambda }) \leq \lambda \varPi _{ k}^{n}(c_{ 1}) + (1-\lambda )\varPi _{k}^{n}(c_{ 2})}$$
  3. iii)

    If c k com ≤ c λ , then: Π k n(c λ ) = 0  ≤ λ Π k n(c 1) + (1 −λ)Π k n(c 2). □ 

4.2 Existence of Location NE

For variable demand functions q k (p), k = 1, …, m, the social cost is given by:

$$\displaystyle\begin{array}{rcl} S(X) =\sum \limits _{ k=1}^{m}q_{ k}(C_{k}(X))\ C_{k}(X)& & {}\\ \end{array}$$

where C k (X) = min{C k 1(X 1), C k 2(X 2), …, C k N(X N)}. Contrary to what happens for constant demand functions, a minimizer of the social cost may not be a location NE, as it is shown by the following example.

Consider two competing firms on the network shown in Fig. 2, each firm locating one facility. The number in each edge (i, k) is the marginal delivered cost, C ik n, between i and k, being C ik 1 = C ik 2. Demand in each node k is linear and given by q k (p) = 4 − p, 0 ≤ p ≤ 4.

Fig. 2
figure 2

Transportation network

Full size image

Let X = (i, j) be facility locations, where node i is the facility location for firm 1, and node j is the facility location for firm 2. Since C ik 1 = C ik 2, it is verified that S(i, j) = S(j, i) and Π 1(i, j) = Π 2(j, i) for all (i, j). In Table 2, the values S(X), Π 1(X) and Π 2(X) are shown for the different combinations (i, j), i < j. Note that pairs (2, 3) and (2, 4) are location NE while the minimizer of social cost, the pair (3, 4), it is not a location NE.

Table 2 Social cost and profits
Full size table

The previous example shows that social cost cannot be used to obtain a location NE if demand is sensible to price. In this case, to our knowledge, no proof has been given to guarantee the existence of a location NE.

4.3 Finding a Location NE

We propose to use the best response procedure to find a location NE. This procedure has extensively been used in Game Theory to find NE when they exist (see [8]).

In our location game, the best response function is obtained as follows:

  • Given a set X = (X 1, X 2, …, X N) of facility locations, for each firm n the following optimization problem is solved:

    $$\displaystyle\begin{array}{rcl} P^{n}(X^{-n}):\ Max\{\varPi ^{n}(Y ^{n},X^{-n}): \vert Y ^{n}\vert = r_{ n},Y ^{n} \subset L\}& & {}\\ \end{array}$$

  • Let \(\hat{X}^{n}\) be an optimal solution of problem P n(X −n), then the best response of firm n to the locations of the facilities of its competitors X −n is defined as follows:

    $$\displaystyle\begin{array}{rcl} R^{n}(X) = \left \{\begin{array}{lll} \hat{Y }^{n} &&if\ \varPi ^{n}(\hat{Y }^{n},X^{-n})>\varPi ^{n}(X^{n},X^{-n}) \\ X^{n}&&otherwise\end{array} \right.& & {}\\ \end{array}$$

  • The best response function is R(X) = (R 1(X), R 2(X), …, R N(X)).

It is clear that X is a Nash equilibrium if and only if R(X) = X. Therefore, the following algorithm can be used to obtain a location NE.

Algorithm BR

Step 1:

Start with any feasible set of facility locations,

 

X = (X 1, X 2, …, X N).

Step 2:

For each n:

 

i) Find an optimal solution \(\hat{Y }^{n}\) to problem P n(X −n).

 

ii) Determine R n(X).

 

Set R(X) = (R 1(X), R 2(X), …, R N(X)).

Step 3:

If X = R(X), X is a location NE, STOP.

 

Otherwise, set X = R(X) and go to Step 2.

Algorithm BR requires to solve problem P n(X −n) for each firm n. The following property will be used to solve such a problem.

Property 6

Under Assumptions  4 and  5 , there exists a set of nodes which is an optimal solution to problem P n (X −n ) for each n.

Proof

Let \(\hat{X}^{n}\) be an optimal solution to P n(X −n). Assume that there is a location \(x_{i} \in \hat{ X}^{n}\) which is an interior point on some edge (a, b). Let us consider all locations in \(\hat{X}^{n}\) are fixed but x i which is assumed to vary in (a, b).

Since the minimum of concave functions is also concave and \(C_{x_{i}k}\) is a concave function at x i in (a, b), then \(C_{k}^{n}(\hat{X}^{n}) =\min \{ C_{x_{i}k},C_{k}^{n}(\hat{X}^{n}\setminus x_{i})\}\) is also concave at x i in (a, b). From Property 5 we have that \(\varPi _{k}^{n}(C_{k}^{n}(\hat{X}^{n}))\), as function of \(C_{k}^{n}(\hat{X}^{n})\), is decreasing and convex. From the theorem of composition of convex functions (see [3]) we obtain that \(\varPi _{k}^{n}(C_{k}^{n}(\hat{X}^{n}))\) is convex at x i in (a, b) if \(\hat{X}^{n}\setminus x_{i}\) is fixed.

The sum of convex functions is also convex, therefore the profit function defined as \(\varPi (\hat{X}^{n}) =\sum _{ k=1}^{m}\varPi _{k}^{n}(C_{k}^{n}(\hat{X}^{n}))\) is convex at x i in (a, b) if \(\hat{X}^{n}\setminus x_{i}\) is fixed. This function reaches a maximum value in an extreme point of the edge (a, b) when x i varies in (a, b). Then the location set \(\hat{X}^{n}\) can be improved by replacing point x i by one of the nodes a or b (the one for which a maximum profit is obtained).

Therefore, if the set of optimal locations \(\hat{X}^{n}\) contains non nodes points, each non node point can be replaced by one node so that a new set of locations V n is obtained whose points are nodes and \(\varPi (\hat{X}^{n}) =\varPi (V ^{n})\). Consequently, there exists a set of nodes which is an optimal solution to P n(X −n). □ 

If Assumptions 4 and 5 hold, from Property 6 an optimal solution to problem P n(X −n) can be found as follows:

Let us define the following sets and variables:

$$\displaystyle\begin{array}{rcl} & & L_{k}^{n} =\{ i: C_{ ik}^{n} <C_{ k}(X^{-n})\} {}\\ & & M^{n} =\{ k: L_{ k}^{n}\neq \emptyset \} {}\\ & & x_{i}^{n} = \left \{\begin{array}{ll} 1\ \mbox{ if a facility is located at node }\ i \\ 0\ \mbox{ otherwise} \end{array} \right. {}\\ & & z_{ik}^{n} = \left \{\begin{array}{ll} 1\ \mbox{ if node}\ k\ \mbox{ is served by firm}\ n\ \text{from node}\ i \\ 0\ \mbox{ otherwise} \end{array} \right.{}\\ \end{array}$$

Note that L k n is the set of locations at which firm n can price below its competitors at node k. M n is the set of nodes where firm n can get a positive profit. x i n and z ik n are location and allocation variables, respectively.

If node k is served from node i ∈ L k n, the equilibrium price is:

$$\displaystyle\begin{array}{rcl} \hat{p}_{k}^{n}(i) = \left \{\begin{array}{lll} p_{k}^{mon}(C_{ ik}^{n})&if &p_{ k}^{mon}(C_{ ik}^{n}) <C_{ k}(X^{-n})\\ & & \\ C_{k}(X^{-n}) &if &p_{k}^{mon}(C_{ik}^{n}) \geq C_{k}(X^{-n}) \end{array} \right.& & {}\\ \end{array}$$

Then the problem P n(X −n) can be formulated as follows:

$$\displaystyle\begin{array}{rcl} P^{n}(X^{-n}):\ & \max & \sum \limits _{ k\in M^{n}}\sum \limits _{i\in L_{k}^{n}}q_{k}(\hat{p}_{k}^{n}(i))(\hat{p}_{ k}^{n}(i) - C_{ ik}^{n})z_{ ik}^{n} \\ & \mbox{ s.t.}& \sum \limits _{i\in L_{k}^{n}}z_{ik}^{n} \leq 1,\mbox{ }k \in M^{n} {}\end{array}$$
(9)
$$\displaystyle\begin{array}{rcl} & & z_{ik}^{n} \leq x_{ i}^{n},\ k \in M^{n},i \in L_{ k}^{n}{}\end{array}$$
(10)
$$\displaystyle\begin{array}{rcl} & & \sum \limits _{i\in L_{k}^{n}}x_{i}^{n} = r_{ n},\ k \in M^{n} \\ & & x_{i}^{n},z_{ ik}^{n} \in \{ 0,1\},\ k \in M^{n},i \in L_{ k}^{n}{}\end{array}$$
(11)

The objective function of problem P n(X −n) represents the profit of firm n. Observe that the prices \(\hat{p}_{k}^{n}(i)\) depend on the set X −n. Constraints (9) mean that each node k ∈ M n can be served from at most one of the facilities of firm n (the facility with the minimum marginal delivered cost in the optimal solution). Constraints (10) imply that variable z ik n may be positive only if firm n locates a facility at i. Constraint (11) represents the number of facilities to be located by firm n.

The above problem is a Binary Integer Linear Programming (BILP) problem which contains a lot of binary variables. However, the number of binary variables can be notably reduced as follows. Let \(\hat{x}_{i}^{n}\) denote an optimal solution for variables x i n, then an optimal solution for variables z ik n is given by:

$$\displaystyle\begin{array}{rcl} \hat{z}_{ik}^{n} = \left \{\begin{array}{ll} 1&\mbox{ if}\ c_{ik} =\min \{ c_{hk}: h \in L_{k}^{n},x_{h}^{n} = 1\} \\ 0&\mbox{ otherwise} \end{array} \right.& & {}\\ \end{array}$$

As the allocation variables are determined by the decision variables in the optimal solution, z ik n can be taken as non negative variable instead of a binary variable. Then, replacing constraints z ik n ∈ { 0, 1} by z ik n ≥ 0 in the above formulation, we obtain an equivalent problem which is a Mixed Integer Linear Programming (MILP) problem.

It may occur that Algorithm BR does not stop, and therefore it does not find a NE. It may also occur that a location NE does not exist but if it exists Algorithm BR could find it.

5 Existence of Multiple Location Nash Equilibria

In the case of an essential product, social cost minimization at the nodes of the network is a combinatorial optimization problem that may have multiple global optima. Then more than one location NE could exist. Furthermore, if X is a global minimizer of social cost and C ik n = C ik for all n, then any partition of the set of optimal locations X into sets X 1, …, X N such that | X n | = r n , n = 1, …, N, is a location NE. Thus, the number of location NE corresponding to such partitions is \(\frac{r!} {r_{1}!r_{2}!\cdots r_{N}!}\).

In the case of a non essential product, minimizers of social cost may not be location NE and the previous result does not hold, but it is possible the existence of more than one location NE as it was shown in the example of Sect. 4.

When more than one location NE are found, the competing firms could agree to select a Pareto optimum equilibrium. Thus, if \(\hat{X}\) and \(\tilde{X}\) are location NE and it is verified that \(\varPi ^{n}(\hat{X}) \geq \varPi ^{n}(\tilde{X})\), n = 1, …, N, with at least one strict inequality, then the firms could agree to select \(\hat{X}\) better than \(\tilde{X}\).

5.1 Aggregated Profit Maximization

Let X be a set of nodes corresponding to an optimal solution to problem (SCM1). We want to determine a partition of the set X into N subsets X 1, …, X N such that the aggregated profit obtained by the firms is maximized.

Then we have to solve the following problem:

$$\displaystyle\begin{array}{rcl} \begin{array}{lll} P(X):&Maximize&\sum \limits _{n=1}^{N}\varPi ^{n}(X^{n})\\ && \\ &s.t. &X^{n} \subset X\mbox{ and }\vert X^{n}\vert = r_{n},n = 1,\ldots,N.\end{array} & & {}\\ \end{array}$$

The aggregated profit associated to X is given by:

$$\displaystyle\begin{array}{rcl} \begin{array}{ll} \sum \limits _{n=1}^{N}\varPi ^{n}(X)& =\sum \limits _{ n=1}^{N}(\sum \limits _{k=1}^{m}Q_{k}C_{k}^{com}(X^{n}) - S(X)) =\\ & \\ & =\sum \limits _{ k=1}^{m}Q_{k}(C_{k}^{com}(X^{1}) + C_{k}^{com}(X^{2}) +\ldots +C_{k}^{com}(X^{N})) - NS(X)\end{array}& & {}\\ \end{array}$$

We consider the following variables:

$$\displaystyle\begin{array}{rcl} & y_{jn} = & \left \{\begin{array}{ll} 1\ \mbox{ if }j \in X^{n} \\ 0\ \mbox{ otherwise} \end{array} \right. {}\\ & C_{k}^{n} =& min\{C_{jk}: j \in X,y_{jn} = 0\} {}\\ \end{array}$$

Note that variables y jn define a partition (X 1, …, X N) of set X, and each variable C k n takes the value C k com(X n) associated to the partition (X 1, …, X N).

Then the problem of determining the partition of X with the maximum aggregated profit can be formulated as follows:

$$\displaystyle\begin{array}{rcl} P(X):& Maximize& \sum \limits _{k=1}^{m}Q_{ k}(C_{k}^{1} + C_{ k}^{2} +\ldots +C_{ k}^{N}) - NS(X) \\ & s.t. & \sum \limits _{j\in X}y_{jn} = r_{n};\ n = 1,\ldots,N {}\end{array}$$
(12)
$$\displaystyle\begin{array}{rcl} & & C_{k}^{n} \leq C_{ jk}(1 - y_{jn}) + Dy_{jn};\ n = 1,\ldots,N,k = 1,\ldots,m,j \in X\qquad \\ & & y_{jn} \in \{ 0,1\},C_{k}^{n} \geq 0;\ n = 1,\ldots,N,k = 1,\ldots,m,j \in X {}\end{array}$$
(13)

Constraints (12) mean that each firm n locates r n facilities which are selected from the set X. Constraints (13) guarantee that each variable C k n will take the value C k com(X n) corresponding to the optimal partition (X 1, …, X N) of X. D is a fixed positive value greater than any cost C jk .

Let \(\hat{y}_{jn}\) be the values of variables y jn corresponding to an optimal solution to problem P(X). Then the location NE which maximize the aggregated profit is \(\hat{X}^{n} =\{ j \in X:\hat{ y}_{jn} = 1\}\), n = 1, …, N.

5.2 Equity Constraints

Any firm n could disagree with the partition \((\hat{X}^{1},\ldots,\hat{X}^{N})\) of X which maximizes the aggregated profit if \(\varPi ^{n}(\hat{X}^{n})\) is not high enough. An alternative way of selecting a partition of X is by including equity constraints. The aim of such constraints is to determine a location equilibrium, so that the firms get similar profits per facility. Let \(\hat{\varPi }\) denote the maximum aggregated profit, which can be obtained by solving problem P(X). For a fixed value λ, 0 ≤ λ ≤ 1, any firm n could agree on selecting a partition of X (location NE) if the average profit per facility the firm obtains is greater than, or equal to, \(\lambda \hat{\varPi }/r\), where r is the total number of facilities. A location equilibrium verifying the equity constraints, for which the aggregated profit is maximum, could be obtained by solving the following MILP problem:

$$\displaystyle\begin{array}{rcl} \begin{array}{lll} P_{\lambda }(X):&Maximize&\sum \limits _{k=1}^{m}Q_{k}(C_{k}^{1} + C_{k}^{2} +\ldots +C_{k}^{N})\\ && \\ &s.t. &C_{k}^{n} \leq C_{jk}(1 - y_{jn}) + Dy_{jn};\ n = 1,\ldots,N,k = 1,\ldots,m,j \in X\\ && \\ & &\sum \limits _{j\in X}y_{jn} = r_{n};\ n = 1,\ldots,N\\ && \\ & & \frac{1} {r_{n}}\left (\sum \limits _{k=1}^{m}Q_{k}C_{k}^{n} - S(X)\right ) \geq \lambda \frac{\hat{\varPi }} {r};\ n = 1,\ldots,N\\ && \\ & &y_{jn} \in \{ 0,1\},C_{k}^{n} \geq 0;\ n = 1,\ldots,N,k = 1,\ldots,m,j \in X\end{array} & & {}\\ \end{array}$$

Observe that P λ (X) reduces to P(X) for λ = 0. For small values of λ problem P λ (X) is feasible, but it could be unfeasible for values of λ close to 1. In order to select a location equilibrium, a sequence of problems P λ (X) can be solved for fixed increasing λ values until one not feasible problem is found. Let \(\overline{\lambda }\) be the greater value of λ for which P λ (X) is feasible, then firms could select the location equilibrium given by the following partition:

$$\displaystyle\begin{array}{rcl} \hat{X}^{n} =\{ j \in X:\hat{ y}_{ jn} = 1\}& & {}\\ \end{array}$$

where \(\hat{y}_{jn}\) are the optimal values for variables y jn in problem \(P_{\overline{\lambda }}(X)\).