Keywords

1 Introduction

Research in the field of competitive location problems was initiated in [1], where the process of choosing the location of facilities and the choice of the policy of pricing by two competitors in a finite segment with a uniform distribution of buyers were considered. The last decades, more and more attention is drawn to problems in which the decision to place and pricing is taken by players competing with each other [2,3,4,5]. To date, many relevant problems are being addressed in this area and many interesting results have been obtained. In this paper, we consider a model that is in some ways an extension of the model of competitive location and pricing from [6].

Let us describe in more detail the problem with its novelty and differences from previous models. The problem is based on the Stackelberg game of two players - the leader and the follower. The players select their locations and then set prices in order to maximize their profits. The leader makes the decision first, and then the follower makes his move. Players consistently place their facilities in the finite set of predetermined locations. When all facilities are placed, the players set prices for a homogeneous product. Here, a discriminatory pricing strategy is used, when the player assigns a price for each client at each facility. In [6], the well-known Bertrand model was used to determine prices and distribute customers by facilities. In this model, the client is monopolized by the facility, where the minimum cost of maintenance is achieved and the monopoly price is assigned. In this paper, a new situation is considered when players can share the demand of clients when it is profitable for them. Obviously, if a player at his facility assigns a price to a client that does not exceed the minimum cost of services at the follower’s facilities, then a rational client will prefer to be serviced by the leader since the follower can not offer a lower price. On the other hand, players can agree among themselves to establish the prices at the level of the maximum purchasing power of the client, and divide the customer’s demand among themselves. We suppose that the demand will be shared equally. In other words, the client will make purchases at the facility of the leader, in a half of cases, and at the facility of the follower, in other cases.

In the paper, the main emphasis is placed on the computational complexity of finding of exact and approximate solutions for different variants of the problem [7].

The paper is organized as follows. In the next section, we formulate the problem. The third section contains results on the computational complexity of the general problem. In the fourth section, we consider the special cases of the problem, their complexity, and algorithms for their solution.

2 The Competitive Location and Pricing Problem with the Uniform Split of the Demand

We introduce the following notation:

\(I=\{1,...,m\}\) is the set of locations for the facilities of the leader and the follower;

\(J=\{1,...,n\}\) is the set of clients;

p is the number of facilities placed by the leader;

r is the number of facilities placed by the follower;

\(t_{i}\) is the unit cost of production in location i;

\(b_{j}\) is the budget of the client of j;

\(d_{j}\) is the demand for the client of j;

\(c_{ij}\) is the unit cost of transportation of product from the facility i to the client j.

To identify the placement of facilities of the leader and follower, we use the following variables:

$$ x_{i} = \left\{ \begin{array}{ll} 1, &{} \text{ if } \text{ the } \text{ leader } \text{ placed } \text{ the } \text{ facility } \text{ at } \text{ the } \text{ point } \, i ,\\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$
$$ y_{i} = \left\{ \begin{array}{ll} 1, &{} \text{ if } \text{ the } \text{ follower } \text{ placed } \text{ the } \text{ facility } \text{ at } \text{ the } \text{ point } \, i,\\ 0 &{} \text{ otherwise. } \\ \end{array} \right. $$

For each client and each facility, we can calculate the prime cost of service. Let vector x denote the leader’s choice and vector y denote the follower’s choice, then \(c_j(x) = \min \{d_j(t_i + c_{ij}) | x_i = 1\}\) is the prime cost of service for the client j by the leader and \(c_j(y) = \min \{d_j(t_i + c_{ij}) | y_i = 1\}\) is the prime cost of service by the follower. When the facilities have been chosen, the pricing process for each client is implemented based on the Bertrand price competition model. Companies compete by setting prices simultaneously and clients choose a company with a lower price [6, 8, 9]. A client prefers the leader if the costs of service by the leader and the follower are the same.

Let \(x_i = 1\), \(c_j(x) = d_j(t_i + c_{ij})\) and \( y_k = 1\), \(c_j(y) = d_j(t_k + c_{kj})\). Suppose, that \(c_j(x) \le c_j(y)\), i.e. for the client j, the leader is the winner. Note, that the leader can set the price at the income-making level of the follower. Denote this price as \(q^1_{ijk}\). Then from the equation \(d_j(p^1_{ijk} + c_{ij}) = d_j(t_{k} + c_{kj})\) we get the price

$$q^1_{ijk} = t_{k} + c_{kj} - c_{ij}$$

for the client j. Hence, the income of the leader at point i is \(w^1_{ijk} = d_j(q^1_{ijk}-t_i)\).

On the other hand, the revenue at the ith service point from the jth client does not exceed \(b_j - d_j(t_i + c_{ij})\). It gives one more way of formation of the price. Denote this price as \( q^2_{ij}\). Set \(b_j - d_j(c_{ij} + q^2_{ij})=0\). We get

$$ q^2_{ij} = \frac{b_j}{d_j} - c_{ij}.$$

Therefore, the income of the leader in this case is \(w^2_{ij} = d_j(q^2_{ij}-t_i) = b_j - d_j(t_i + c_{ij})\). It is easy to see that

$$w^1_{ijk} - w^2_{ij} = d_j (q^1_{ijk} - q^2_{ij}) = d_j(t_k + c_{kj}) - b_j.$$

Let \(w^3_{ij} = (d_j/2) (q^2_{ij}-t_i)\) is the income of the leader from the division of the demand in half between players.

Let’s analyze the possible cases.

1. Let \(q^2_{ij} \ge q^1_{ijk}\) and \(w^1_{ijk} \le w^3_{ij} \). That is, the income from monopolization is less than the income from the division of the demand in half between players. Therefore in our model, in this case, players agree to share the client’s demand among themselves.

2. If \(q^2_{ij}\ge q^1_{ijk}\) and \(w^1_{ijk} > w^3_{ij}\), then the leader has more income when using a monopoly price \(q^1_{ijk}\).

3. If \(q^2_{ij} < q^1_{ijk}\), then the leader gets the maximum possible income, that is equal to \(w^2_{ij} = d_j(q^2_{ij}-t_i) = b_j - d_j(t_i + c_{ij})\) using the price \(q^2_{ij}\).

Case \(c_j(x) > c_j(y)\) is analyzed in a similar way.

Now, as in [6], we replace non-Boolean variables \(q^1_{ijk}, q^2_{ij}\) with boolean variables.

$$ z^{Lc}_{ijk} = \left\{ \begin{array}{ll} 1,&{} \text{ if } \text{ the } \text{ client } \, j {\text { is serviced by the leader's facility }}\, i \\ &{} \text{ with } \text{ the } \text{ price } \, q^1_{ijk},\\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$
$$ z^{Lb}_{ijk} = \left\{ \begin{array}{ll} 1,&{} \text{ if } \text{ the } \text{ client } \, j {\text { is serviced by the leader's facility }}\, i \\ &{} \text{ with } \text{ the } \text{ price } \, q^2_{ij},\\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$
$$ z^{Fc}_{ijk} = \left\{ \begin{array}{ll} 1,&{} \text{ if } \text{ the } \text{ client } \, j {\text { is serviced by the follower's facility }}\, k\\ &{} \text{ with } \text{ the } \text{ price } \, q^1_{ijk}, \\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$
$$ z^{Fb}_{ijk} = \left\{ \begin{array}{ll} 1,&{} \text{ if } \text{ the } \text{ client } \, j {\text { is serviced by the follower's facility }}\, k\\ &{} \text{ with } \text{ the } \text{ price } \, q^2_{ij}\\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$
$$ z_{ijk} = \left\{ \begin{array}{ll} 1,&{} \text{ if } \text{ the } \text{ client } \, j {\text { is serviced by the leader from the point }} i {\text { and}}\\ &{} \text{ the } \text{ follower } \text{ from } \text{ the } \text{ point } \, k {\text { simultaneously,}}\\ 0 &{} \text{ otherwise; } \\ \end{array} \right. $$

This approach allows us to limit ourselves to only Boolean variables in the proposed model. The set \(I_j(x)\) consists of locations that the follower can use to capture the client j:

$$I_j(x)=\{i\in I : c_{ij} + t_{i} < \min \limits _{k\in I : x_k = 1} (c_{kj} + t_{k})\}.$$

The competitive location and pricing problem with the uniform split of the demand can be represented as the linear Boolean bi-level optimization program. We propose the following model for the leader

$$\begin{aligned} \sum \limits _{i\in I}\sum \limits _{j\in J}&\sum \limits _{k\in I}\bigl ( d_{j} (c_{kj} + t_{k} - c_{ij} - t_{i}) z^{Lc}_{ijk} + (b_{j} - d_{j} (c_{ij} + t_{i})) z^{Lb}_{ijk} \\&+\, 0.5 (b_{j} - d_{j} (c_{ij} + t_{i})) z_{ijk}\bigr ) \rightarrow \max _{x, y, z^{Lc}, z^{Lb}, z^{Fc}, z^{Fb}, z} \nonumber \end{aligned}$$
(1)

under constraints:

$$\begin{aligned} \sum \limits _{i\in I}x_{i}= p; \end{aligned}$$
(2)
$$\begin{aligned} (y, z^{Lc}, z^{Lb}, z^{Fc}, z^{Fb}, z)\in \mathcal {F}^{*}(x); \end{aligned}$$
(3)
$$\begin{aligned} x_{i}\in \{0,1\};i\in I. \end{aligned}$$
(4)

The objective function (1) defines the income of the leader. Here the first term corresponds to the case when the leader monopolizes the client, reducing his price to the level of the cost price of service at the follower’s facilities. That is, in terms of prices and revenues, it is the case 2: \(q^2_{ij}\ge q^1_{ijk}\) and \(w^1_{ijk} > w^3_{ij}.\) If the price of \(q^2_{ij}\), determined by the budget, is less than the monopoly price \(q^1_{ijk}\), then the second term linking the price to the budget level is used. The third term corresponds to the case when it is advantageous for the leader to share the client’s budget with the follower. That is, the income from monopolization is less than the income from the division of the demand in half between players. Constraint (2) means that the leader must open exactly p facilities. From constraint (3) it follows that the distribution of clients between players and the player’s incomes are determined on the basis of the optimal solution of the follower. Due to this constraint, our model is a bilevel programming problem. The set \(\mathcal {F}^{*}(x)\) is the set of optimal solutions for the follower’s parametric problem. As the parameter, we consider here the set of facility locations chosen by the leader.

For the follower, we propose the following model:

$$\begin{aligned} \sum \limits _{i\in I}\sum \limits _{j\in J}\sum \limits _{k\in I} \bigl ( d_{j} (c_{ij} + t_{i} - c_{kj} - t_{k}) z^{Fc}_{ijk} + (b_{j} - d_{j} (c_{kj} + t_{k})) z^{Fb}_{ijk} \\ \nonumber \, +\, 0.5 (b_{j} - d_{j} (c_{kj} + t_{k})) z_{ijk} \bigr ) \rightarrow \max _{y, z^{Lc}, z^{Lb}, z^{Fc}, z^{Fb}, z} \end{aligned}$$
(5)

under constraints:

$$\begin{aligned} \sum \limits _{i\in I}y_{i}= r; \end{aligned}$$
(6)
$$\begin{aligned} \sum \limits _{i,k\in I} (z^{Fc}_{ijk} + z^{Fb}_{ijk})\le \sum \limits _{i\in I_j(x)}y_i; j\in J; \end{aligned}$$
(7)
$$\begin{aligned} x_{i}+y_{i}\le 1;i\in I; \end{aligned}$$
(8)
$$\begin{aligned} \sum \limits _{i,k\in I}(z^{Lc}_{ijk} + z^{Lb}_{ijk} + z^{Fc}_{ijk} + z^{Fb}_{ijk} + z_{ijk}) \le 1; j\in J; \end{aligned}$$
(9)
$$\begin{aligned} \sum \limits _{k\in I}(z^{Lc}_{ijk} + z^{Lb}_{ijk} + z^{Fc}_{ijk} + z^{Fb}_{ijk} + z_{ijk})\le x_i; i\in I, j\in J; \end{aligned}$$
(10)
$$\begin{aligned} \sum \limits _{i\in I}(z^{Lc}_{ijk} + z^{Lb}_{ijk} + z^{Fc}_{ijk} + z^{Fb}_{ijk} + z_{ijk})\le y_k; k\in I, j\in J; \end{aligned}$$
(11)
$$\begin{aligned} (c_{ij} + t_{i}) (z^{Lc}_{ijk}&+ z^{Lb}_{ijk} + z^{Fc}_{ijk} + z^{Fb}_{ijk} + z_{ijk})\le (c_{i^\prime j} + t_{i^\prime }) x_{i^\prime } \\&+ \, (1-x_{i^\prime })\overline{C}; i,i^\prime ,k\in I,j\in J; \nonumber \end{aligned}$$
(12)
$$\begin{aligned} (c_{kj} + t_{k}) (z^{Lc}_{ijk}&+ z^{Lb}_{ijk} + z^{Fc}_{ijk} + z^{Fb}_{ijk} + z_{ijk})\le (c_{k^\prime j} + t_{k^\prime }) y_{k^\prime } \\&+\, (1-y_{k^\prime })\overline{C}; i,k,k^\prime \in I, j\in J; \nonumber \end{aligned}$$
(13)
$$\begin{aligned} d_{j} (c_{kj} + t_{k} - c_{ij} - t_{i}) \le 0.5 (b_{j} - d_{j} (c_{ij} + t_{i})) z_{ijk} + (1 - z_{ijk})\overline{C}; i,k\in I,j\in J; \end{aligned}$$
(14)
$$\begin{aligned} \sum \limits _{i\in I}\sum \limits _{k\in I} ( d_{j} (c_{kj} + t_{k}) - b_{j}) z^{Lc}_{ijk} \le 0; j\in J; \end{aligned}$$
(15)
$$\begin{aligned} \sum \limits _{i\in I}\sum \limits _{k\in I} ( d_{j} (c_{ij} + t_{i}) - b_{j}) z^{Fc}_{ijk} \le 0; j\in J; \end{aligned}$$
(16)
$$\begin{aligned} z^{Lc}_{ijk}, z^{Lb}_{ijk}, z^{Fc}_{ijk}, z^{Fb}_{ijk}, z_{ijk}, y_i\in \{0,1\}; i,k\in I, j\in J. \end{aligned}$$
(17)

The objective function (5) defines the income of the follower. The components of the objective function have the same meaning as the terms of the objective function of the leader. The constraint (6) means that the follower must open exactly r facilities. The constraints (7) and (9) implement the mechanism of distribution of clients between players. If \(I_j(x) = \emptyset \) then the leader monopolize the client since he has the minimal servicing cost there. Otherwise, the client may belong to the follower if he chooses one of the points of the set \(I_j(x)\) as the location for one of his facilities. The constraint (8) prohibits to the leader and follower to place facilities at the same point. From the constraints (10) and (11) it follows that the client cannot be serviced at a point where there are no open facilities. The constraints (9), (12) and (13) imply that we have selected a unique pair of open facilities for the client j, one for the leader (i) and another for the follower (k), and the chosen leader’s facility achieves the smallest servicing cost for the client. Similarly, the smallest cost of service for client in follower’s facilities is achieved at his chosen facility. Further assume that the client was monopolized by the leader and we consider the optimal solution of the bilevel problem. Then if the prices \(q^1_{ijk}\) and \(q^2_{ij}\) are nontrivial, then it follows from the restriction of (9) that one of the variables \(z^{Lc}_{ijk}\), \(z^{Lb}_{ijk}\), \(z_{ijk}\) is equal to 1. Let \(d_j(t_k + c_{kj}) - b_j \le 0\) and \(w^1_{ijk} \le w^3_{ij} = (d_j/2)(q^2_{ij}-t_i)\), that is, case 1 is executed. Then the income from monopolization is less than the income from the division of the demand in half between players. So, \(z_{ijk} = 1\) and the restriction (14) holds. Suppose, that \(d_j(t_k + c_{kj}) - b_j \le 0\) and \(w^1_{ijk}> w^3_{ij}\), then the leader has more income when using a monopoly price \(q^1_{ijk}\). Then \(z^{Lc}_{ijk} = 1\) and the restriction (15) holds. Finally, if \(d_j(t_k + c_{kj}) - b_j > 0\), then the leader gets the maximum possible income equals to \(w^2_{ij} = d_j(q^2_{ij}-t_i) = b_j - d_j(t_i + c_{ij})\) using the price \(q^2_{ij}\). Constraints (14) and (16) are interpreted in a similar way for client j monopolized by the follower.

Further, we will assume that the initial data for the problem is rational.

3 The Computational Complexity

We recall the definition of the first level of the polynomial hierarchy of complexity classes of decision problems. The first level consists of classes P, NP and co-NP. The class P contains problems solvable in polynomial time on deterministic Turing machines. The class NP is defined as the class of problems solvable in polynomial time on nondeterministic Turing machines. The third basic class co-NP consists of decision problems whose complements belong to NP. These classes are also denoted as \(\varDelta ^P_1\), \(\varSigma ^P_1\), and \(\varPi ^P_1\), respectively. The second level of the polynomial hierarchy is defined by deterministic and nondeterministic Turing machines with oracle [7]. It is said that the decision problem belongs to class \(\varDelta ^P_2\) if there exists a deterministic Turing machine with an oracle that recognizes its in polynomial time, using as oracle some language from class NP. Similarly, the decision problem belongs to class \(\varSigma ^P_2\) if there exists a nondeterministic Turing machine with an oracle that recognizes its in polynomial time, using as oracle some language from class NP.

In order to proceed optimization problems, we use the concept of the standard decision problem corresponding to the optimization problem. We associate optimization problem L with the following decision problem D(L). The input of this problem is the input of the problem L and an arbitrary rational number k. In the problem D(L) it is necessary to decide whether a feasible solution exists with the objective function value large or equal to k. Class PO (correspondingly, \(\varDelta ^P_2O\)) includes optimization problems for which the standard decision problem lies in class P (correspondingly, \(\varDelta ^P_2\)). Similarly, class NPO (correspondingly, \(\varSigma ^P_2O\)) includes optimization problems for which the standard decision problem lies in class NP (correspondingly, \(\varSigma ^P_2\)).

In this section, we analyze the complexity of the competitive location and pricing problem and its subproblems. We start from the following lemma.

Lemma 1

The competitive location and pricing problem with the uniform split of the demand belongs to the class \( \varSigma ^ P_2 O \).

Proof

In the standard decision problem, it is necessary to find a solution to the problem with the value of the objective function at least k. Such a problem can be solved by brute force enumeration of all locations of leader’s facilities and by solving the parametric problem of the follower. In other words, we can guess the necessary location x of the leader’s facilities and the corresponding optimal solution \((y, z^{Lc}, z^{Lb}, z^{Fc}, z^{Fb}, z)\) of the follower in a non-deterministic time and then check constraints (2)–(4) in polynomial time, using a suitable NP-oracle. The verification of constraints (2) and (4) is trivial. As an NP-oracle, let’s take the standard decision problem for the follower’s problem. Since the follower’s objective function is limited, with the help of the oracle and binary search we will find the optimal value of the parametric problem of the follower for the given location x of the leader’s facilities. If the variables \((y, z^{Lc}, z^{Lb}, z^{Fc}, z^{Fb}, z)\) satisfy the constraints of the follower’s problem and the value of the objective function on this feasible solution coincides with the previously found optimal value, then the constraint (3) is satisfied. Since the number of calls to an oracle is limited by the logarithm of the length of the record of the initial data of the problem, then to verify constraints (2)–(4), a polynomial time is sufficient. Thus, the problem of the leader belongs to class \( \varSigma ^ P_2 O \).

Fig. 1.
figure 1

Facilities and profitable clients that correspond to variables \(x_i\) and \(y_i\).

Full size image

Theorem 1

The competitive location and pricing problem with the uniform split of the demand is \( \varSigma ^ P_2\)-hard.

Proof

We reduce the following problem to the competitive location and pricing problem.

figure a

As shown in [10] \(\exists \forall 3,4 SAT\) is \(\varSigma ^p_2\)-complete.

Given an instance of \(\exists \forall 3,4 SAT\) and let k be the number of conjunction in \(\varphi (x,y)\).

We construct the following instance of the competitive location and pricing problem. For each variable \(x_i (y_i)\) we introduce two profitable facility locations \(x_i\) and \(\overline{x_i}\) (\(y_i\) and \(\overline{y_i}\)) corresponding to literals \(x_i\) and \(\overline{x}_i\) (\(y_i\) and \(\overline{y_i}\)), respectively. Between the facility locations \(x_i\) and \(\overline{x_i}\) (\(y_i\) and \(\overline{y_i}\)) we insert a profitable client \(j^x_i\) (\(j^y_i\)) which is connected by arcs to both facility locations (see Fig. 1). The length of arcs that connect \(j^x_i\) (\(j^y_i\)) with \(x_i\) (\(y_i\)) and \(\overline{x_i}\) (\(\overline{y_i}\)) is equal to k, i.e. \(d(x_i, j^x_i) = d(j^x_i, \overline{x_i}) = d(y_i, j^y_i) = d(j^y_i, \overline{y_i}) = k\). The budget of the client \(j^x_i\) is equal to \(16k^2 + k\) and the budget of the client \(j^y_i\) is equal to \(12k^2 + k\). We will call locations \(x_i\) and \(\overline{x_i}\) (\(y_i\) and \(\overline{y_i}\)) alternative facility locations.

For each conjunction \(\kappa _s\), we introduce two facility locations \(alt_s,\) \(sin_s\) and four clients \(j^{con}_s\), \(j^{alt}_s\), \(j^{sin}_s,\) \(j^{ad}_s.\) The reduction of \(x_i \wedge y_{i_1} \wedge y_{i_2} \wedge y_{i_3}\) is illustrated in Fig. 2. The client \(j^{con}_s\) is directly connected with five facility locations \(alt_s,\) \(x_i,\) \(\overline{y_{i_1}},\) \(\overline{y_{i_2}},\) and \(\overline{y_{i_3}}.\) We set \(d(j^{con}_s, x_i) = 10k^2 + k,\) \(d(j^{con}_s, alt_s) = 10k^2,\) and \(d(j^{con}_s, \overline{y_i})\) is equal to \(10k^2+1\) for all i. The budget of \(j^{con}_s\) is equal to \(10k^2 + k + 1\). We will call the clients \(j^{con}_s\) conflicting clients. The client \(j^{alt}_s\) is directly connected with two facility locations \(x_i\) and \(alt_s,\) wherein \(alt_s\) is located between \(j^{alt}_s\) and \(j^{con}_s.\) We set \(d(alt_s, j^{alt}_s) = 5k^2\) and \(d(x_i, j^{alt}_s) = 16k^2 - k.\) The budget of \(j^{alt}_s\) is equal to \(16k^2.\) The client \(j^{ad}_s\) is at a distance of 0 from the facility location \(\overline{x_i}\) and his budget is equal to k. The client \(j^{sin}_s\) and the facility location \(sin_s\) are removed a sufficient distance from the other vertices and \(d(sin_s, j^{sin}_s) = 0.\) The budget of \(j^{sin}_s\) is equal to \(11k^2 + \varepsilon ,\) where \(0< \varepsilon < 1.\) The transportation cost between two vertices given by the shortest path. For example, a network for the formula \(\varphi (x,y) = (\overline{x_1}\wedge y_1\wedge \overline{y_2}\wedge y_3)\vee (x_2\wedge y_2\wedge \overline{y_3})\) is described in Fig. 3. The number of leader’s facilities p coincides with the number of Boolean variables x. The number of follower’s facilities \(r=l+k,\) where l is the number of Boolean variables y.

Fig. 2.
figure 2

Representation of \(x_i \wedge y_{i_1} \wedge y_{i_2} \wedge y_{i_3}\)

Full size image

Now consider how the player’s income depends on the choice of the location of the facilities. Let \(\kappa _s=x_i\wedge y_{i_1}\wedge y_{i_2}\wedge y_{i_3}.\) Let the leader place the facility in \( x_i \) or \( \overline{x_i}.\) If the follower doesn’t occupy the alternative location then the leader will receive a income of \(16k^2\) from the client \(j^x_i,\) otherwise the leader and follower share the income from the client \(j^x_i\) and each will receive \(8k^2.\) In the latter case, the possible additional income of each of the facilities \(x_i\) and \(\overline{x_i}\) from the clients \(j^{con}_s\), \(j^{alt}_s\), \(j^{ad}_s,\) \(s=1,\ldots ,k\) will not exceed \(k^2 + k\). Thus, if both players place their facilities in \( x_i \) and \( \overline{x_i}\) their income will not exceed \(9k^2 + k.\) The maximal income at \(y_i\), \(\overline{y_i}\), \(i\in \{i_1,i_2,i_3\}\), \(alt_s\), or \(sin_s\) doesn’t exceed \(13k^2 +k\) and the minimal income at \(y_i\), \(\overline{y_i}\), \(alt_s\), or \(sin_s\) is at least \(11k^2 - k\). Therefore, the leader must place own facilities at \(x_i\) and \(\overline{x_i}\), one facility at each pair (\(x_i\), \(\overline{x_i}\)), because he knows that in this case the follower set his facilities at \(y_i\), \(\overline{y_i}\), \(alt_s\), or \(sin_s\).

Suppose that the leader took all the places near the profitable clients \(j^x_i.\) If the follower places the facility in \( y_i \) or \( \overline{y_i},\) he will receive a income of \(12k^2\) from the client \(j^y_i.\) The possible income of each of the facilities \(alt_s\) and \(sin_s\) doesn’t exceed \(11k^2+k+1.\) Thus, the follower must place r facilities at \(y_i\) and \(\overline{y_i}\), one facility at each pair (\(y_i\), \(\overline{y_i}\)). The remaining facilities of the follower should be placed in locations \(alt_s\) and \(sin_s.\) It is easy to verify that the follower must select exactly one of locations \(alt_s\) or \(sin_s,\) for each \(s=1,\ldots ,k\) and his choice will depend on the location of the leader’s facilities. We note that the income of the follower in \(sin_s\) does not depend on the location of the leader’s facilities and it is equal to \(11k^2 + \varepsilon .\) Let the leader open the facility \(x_i\). Then the income of the follower in \(alt_s\) is equal to \(16k^2 - k - 5k^2 + 10k^2 + k - 10k^2 = 11k^2\) and he prefers to open the facility \(sin_s.\) It follows that in this case, the leader receives the client \(j^{alt}_s\) and the income of k from it. Let the leader open the facility \(\overline{x_i}\). In this case, the leader does not receive the client \(j^{alt}_s\) but he receives the client \(j^{ad}_s\) the income of k from it. It follows that the total income of the leader from all clients except for conflicting clients is equal to \((16p+1)k^2\) and does not depend on the choice in which of the locations \(x_i\) or \(\overline{x_i}\) to open the facility. In turn, the follower prefers to open the facility \(alt_s.\) Indeed, the income of the follower from client \(j^{alt}_s\) in \(alt_s\) is equal to \(11k^2\) and he get an additional income of at least 1 from client \(j^{con}_s.\) It follows that the best location of follower’s facilities in vertices \(alt_s\) and \(sin_s,\) \(s=1,\ldots ,k,\) is completely determined by the location of leader’s facilities and does not depend on the location of profitable follower’s facilities. Hence, the income of each player depends on who gets conflicting clients. If the leader opens the facility \(\overline{x_i}\) then the client \(j^{con}_s\) will be served by the follower. Let the leader open the facility \(x_i\). The follower get the client \(j^{con}_s\) if and only if he opens one of the facility \(\overline{y_{i_1}},\) \(\overline{y_{i_2}},\) or \(\overline{y_{i_3}}.\) Thus, the leader gets at least one conflicting client if and only if there exists a truth assignment of x such that for all assignments of y the formula \(\varphi (x,y)\) is satisfied.

Fig. 3.
figure 3

An example of network for \(\varphi (x,y) = (\overline{x_1}\wedge y_1\wedge \overline{y_2}\wedge y_3)\vee (x_2\wedge y_2\wedge \overline{y_3})\)

Full size image

4 Special Cases

In addition to the \(\exists \forall 3,4 Sat\) problem, consider \(\exists \forall 1,2 Sat\) problem. In this problem, each conjunction contains only one variable from x and at most one variable from y. Obviously, the problem is polynomially solvable. In Theorem 1, we constructed a set of instances of competitive location and pricing problem which corresponds to \(\exists \forall 3,4 Sat\) problem. By analogy, we construct a set of instances corresponding to the \(\exists \forall 1,2 Sat\) problem. We denote the set as a CLP2SAT problem. Is the CLP2SAT problem polynomially solvable? For the answer, consider a maxmin-1,2-Sat problem. As in \(\exists \forall 1,2 Sat\) problem, we are given two vectors \(x=(x_1,\ldots ,x_p)\) and \(y=(y_1,\ldots ,y_r)\) of Boolean variables and a formula \(\varphi (x,y)\) in the disjunctive normal form. Each conjunction contains only one variable from x and at most one variable from y. We need to find x, at which the total number of satisfied conjunction is maximal for all y. Obviously, the CLP2SAT problem is equivalent to the maxmin-1,2-Sat problem.

Theorem 2

The maxmin-1,2-Sat problem is NP-hard.

Proof

Consider the NP-hard Exact Cover by 3-sets problem.

figure b

Given an instance of EC3SET and let k be the cardinality of the collection C. We construct the following instance of the maxmin-1,2-Sat problem.

For each subset \(C_r = (X_i, X_j, X_l)\), we define boolean variables \(x_r\), \(y_i\), \(y_j\), \(y_l\) and introduce conjunctions \((x_r \wedge y_i)\), \((x_r \wedge y_j)\), \((x_r \wedge y_l)\). Additionally, we introduce 3q conjunctions \((x_0 \wedge \overline{y_i})\), \(i=1,\ldots ,3q,\) k conjunctions \((\overline{x_r} \wedge y_0)\), \(r=1,\ldots , k\) and k identical conjunctions \((x_0 \wedge \overline{y_0})\). We show that an exact cover of X exists if and only if the total number of satisfied conjunctions is equal to \(2q + k.\)

It is easy to see that we need only consider the case when \(x_0\) and \(y_0\) are equal to 1. Let H be the total number of satisfied conjunctions and h be the number of variables \(x_r\) such that \(x_r=1.\) If \(h < q\) then \(H \le 3h + k - h = 2h + k < 2q + k.\) If \(h > q\) then \(H \le 3q +k - h = 2q + k - (h - q)< 2q + k.\) Let \(h=q.\) We have

$$H = 3q - s + (k - q) = 2q + k - s,$$

where s is a number of repetitions of variables y in the truth assignment of x. It follows that an exact cover of X exists if and only if the optimum is \(2q + k\).

Corollary 1

The CLP2SAT problem is NP-hard.

Consider particular cases, when leader’s and follower’s facilities are opened. In these cases, each client needs to define a facility at which he will be served. It can be done in \(O(mn^2)\) times. Therefore, the problem is polynomially solvable.

Note, the competitive location and pricing problem can be solved in \(O(C^n_p * C^{n-p}_r * mn^2) = O(mn^{p+r+2})\) by look over through all locations. Consider the following particular cases: (1) \(p = const\); (2) \(r = const\); (3) \(p,r = const\).

In the first case, the number of leader’s location is \(C^n_p\). It is a polynomial of n. Therefore, the problem belongs to \(\varDelta ^P_2 O\).

In the second case, the follower problem is polynomially solvable as \(C^{n-p}_r = Poly(n,p)\). Then, the problem belongs to NPO.

In the third case, the problem can be solved in polynomial time. Then the problem belongs to PO.

Finally, consider the cases, where \(p=0\) or \(r=0\). Then the problem is equivalent to the widely known p-median problem, which is strongly NP-hard. Therefore, these particular cases are strongly NP-hard as well.

5 Conclusion

This paper studies a new optimization model of competitive facility location and pricing. Results of the computational complexity of the model are presented. A few numbers of special cases are considered.

There are several interesting areas of research on this problem. The first of them is connected with the development of exact algorithms for solving the problem. Here, ideas from [11, 12] can be used. Another area of research is the development of algorithms for solving on the basis of local search and metaheuristics. Despite the fact that the exponential complexity of local search is theoretically shown [13], the available experience of using such methods of solution indicates their practical effectiveness [14,15,16,17,18]. It is also important to continue studying the relationships of this class of problems with the polynomial hierarchy and the approximation hierarchy. Similar results were obtained for a number of interesting problems of bilevel programming [10, 19,20,21].