1 Introduction

We consider a specific symmetric finite game in strategic form with two players that may enrich discrete location theory. As this game can be classified as a discrete variant of the continuous Hotelling game of pure location [2–4], we refer to it as the Hotelling bi-matrix game.

It is appropriate to introduce the Hotelling bi-matrix game with parameters n (a positive integer) and w (\(\in ] {0},{1} ] \)) with a little real-world interpretation as follows. Consider the \(n+1\) points \( \{0,1, \ldots , n\}\) on the real line, to be referred to as locations. There are two players, denoted by 1 and 2, who simultaneously and independently choose a location. If player 1 chooses location \(x_1\) and player 2 location \(x_2\), then the payoff \(f_1(x_1,x_2)\) to player 1 is determined by the locations nearer to \(x_1\) than to \(x_2\) and the locations at an equal distance from \(x_1\) and \(x_2\) as follows: a location x contributes \(w^{|x_1-x|}\) if \(|x_1- x | < |x_2-x|\) and it contributes \(w^{|x_1-x|}/2\) if \(|x_1- x | = |x_2-x|\). The definition of \(f_2\) is similar. This may for example correspond to real-world situations where each location contains a consumer that buys from the closets sellers. If \(w=1\), then each consumer buying from a seller contributes the same to this seller; if \(w < 1\), then such a consumer contributes less the further away from the seller he is and the smaller w is.

Here is a visualization in the case \(n=5\) and \(w=1/4\) of the situation for the strategy profile (1, 3):

The payoffs are \(f_1(1,3) = w + 1 + \frac{1}{2} w = 1 \frac{3}{8}\) and \(f_2(1,3) = \frac{1}{2} w + 1 + w + w^2 = 1 \frac{7}{16}\).

As the Hotelling bi-matrix game is finite, it can be represented in a natural way (indeed) as a bi-matrix with rows and columns indexed by \(0,\ldots ,n\). For \(w=1\), the game is a special case of a class of games considered in for example [7] and called there ‘Voronoi games’. There is little literature available on such games

It is well known that a finite game in strategic form has a Nash equilibrium in mixed strategies, but not necessarily a pure strategy equilibrium. A natural question is whether the Hotelling bi-matrix game has a pure Nash equilibrium and more generally what the set of such equilibria looks like and depends on w (and n); we write \(E_w\) for the (Nash) equilibrium set. For \(w=1\) the problem turns out to be simple, but for \( w \ne 1\) it is not. Computer simulations in [1] suggest that the Hotelling bi-matrix game has (for all parametric values) an equilibrium. In the present article we prove that this is indeed the case.

As far as we know, equilibrium existence for the Hotelling bi-matrix game cannot be derived from general equilibrium existence results. We prove equilibrium existence by determining the equilibrium set \(E_w\) and observing that it is not empty. In this proof, two symmetries play an important role. In terms of the best response correspondences \(R_1\) and \(R_2\), the first is that \(R_1 = R_2 \;=: \; R\) (as the game is symmetric) and the second that \(R(n-x) = \{n \}- R(x)\). These symmetries make that we can define a natural subset of strategy profiles \(\mathbf {H}^{\star }\) such that \(E^{\star }_w := \mathbf {H}^{\star } \cap E_w\) determines \(E_w\) for \(w \ne 1\) (see Theorem 1). The proof then further concentrates on determining \(E^{\star }_w\). The set \(E_w^{\star }\) is determined by showing, among other things (in Theorem 4), that for various strategy profiles belonging to \(\mathbf {H}^{\star }\) first-order conditions are already sufficient. This result is related to ‘demi-modality properties’ of the conditional payoff functions.

It seems that a better understanding of the Hotelling bi-matrix game also may lead to a new class of finite (symmetric) games in strategic form that have a pure Nash-equilibrium (see Sect. 6).

The organisation of the article is as follows. Section 2 provides the formulas for the payoff functions of the Hotelling bi-matrix game. Section 3 provides the definition of \(E_w^{\star }\) and its relation to \(E_w\). The main result, Theorem 2, is presented in Sect. 4 in terms of \(E_w^{\star }\). Section 5 is devoted to the proof of this theorem and in doing so provides some additional results: in particular Theorem 3, which guarantees that for each equilibrium \(\mathbf {e}\) it holds that \(n-2 \le e_1 + e_2 \le n+2\). Section 6 contains some concluding remarks and a conjecture. There is an appendix which contains some useful formulas and inequalities that easily follow from the explicit expressions of the payoff functions.

2 The game

The Hotelling bi-matrix game is a game in strategic form with players 1 and 2 with the same strategy set \(H := \{ 0,1,\ldots ,n\}\) and with payoff functions \(f_1, f_2: H \times H \rightarrow \mathbb {R}\). Formulas for the payoff functions will be given below. For the moment we do not need them as various results already follow from the real-world description.

Example 1

For \(n=1\) the bi-matrix is

$$\begin{aligned} \left( \begin{array}{c@{\quad }c} \frac{1}{2} (1+w) ; \frac{1}{2} (1+w) &{} 1;1 \\ 1;1 &{} \frac{1}{2} (1+w) ; \frac{1}{2} (1+w) \end{array} \right) . \end{aligned}$$

For \(w < 1\): \(E_w = \{ (0,1), (1,0) \}\).

For \(w=1\): \(E_w = \{ (0,0), (0,1), (1,0), (1,1) \}\).

For \(n=2\) the bi-matrix is

$$\begin{aligned} \left( \begin{array}{l@{\quad }c@{\quad }c@{\quad }c} \frac{1+w+w^2}{2}; \frac{1+w+w^2}{2} &{} 1;1+w &{} 1 + \frac{w}{2}; 1 + \frac{w}{2} \\ 1+w;1 &{} \frac{1+2w}{2}; \frac{1+2w}{2} &{} 1 + w ;1 \\ 1+\frac{w}{2}; 1+\frac{w}{2}; &{} 1; 1+w &{} \frac{1+w+w^2}{2}; \frac{1+w+w^2}{2} \end{array} \right) . \end{aligned}$$

For \(w < \frac{1}{2}\): \(E_w = \{ (0,1), (1,0), (1,2), (2,1) \}\).

For \(w = \frac{1}{2}\): \(E_w = \{ (0,1), (1,0), (1,1), (1,2), (2,1) \}\).

For \(w > \frac{1}{2}\): \(E_w = \{ (1,1) \}\).

A first fundamental observation is that for all \((x_1,x_2) \in H \times H\)

$$\begin{aligned} f_2(x_2,x_1)= & {} f_1(x_1,x_2), \end{aligned}$$
(1)
$$\begin{aligned} f_i(x_1,x_2)= & {} f_i(n-x_1,n-x_2) \; (i=1,2). \end{aligned}$$
(2)

With \(\{i, j \} = \{1, 2 \}\) we define for \(x_j \in H\) the (conditional payoff) function \(f_i^{(x_j)}: H \rightarrow \mathbb {R}\) of player i by

$$\begin{aligned} f_i^{(x_j)}(x_i) := f_1(x_1,x_2). \end{aligned}$$

We denote by \( R_i: H \multimap H\) the best response correspondence of player i, i.e. \( R_i(x) := \mathrm {argmax} \, f_i^{(x)}\). As H is finite, \(R_i\) is proper, i.e. \(R_i(x) \ne \emptyset \; (x \in H)\). As, by (1), the game is symmetric, we have

$$\begin{aligned} R_1 = R_2 \; =: \; R \end{aligned}$$

and with (2) it follows that also (in terms of Minkowski sums)

$$\begin{aligned} R(n-x) = \{ n \} - R(x) \; (x \in H). \end{aligned}$$
(3)

Given n, let

$$\begin{aligned} p := n/2 \text{ if } n \text{ even }, \;\; p := (n-1)/2 \text{ if } n \text{ odd }. \end{aligned}$$

It is clear that the following proposition holds.

Proposition 1

  1. (1)

    If n is even and \(w=1\), then \( R(x) = \left\{ \begin{array}{c} \{ x+1 \} \text{ if } x < p, \\ { x} \text{ if } x = p, \\ \{ x - 1 \} \text{ if } x > p. \end{array} \right. \)

  2. (2)

    If n is odd and \(w=1\), then \( R(x) = \left\{ \begin{array}{c} \{ x+1 \} \text{ if } x < p, \\ \{x,x+1\} \text{ if } x = p, \\ \{x-1,x \} \text{ if } x =p+1, \\ \{ x - 1 \} \text{ if } x > p+1. \end{array} \right. \)

  3. (3)

    If n is even, then \(E_1 = \{ (p,p) \} \).

  4. (4)

    If n is odd, then \(E_1 = \{ (p,p), \; (p,p+1), \; (p+1,p), \; (p+1,p+1) \}\).

Determining the equilibrium set \(E_w\) for \(w \ne 1\) is much more difficult. Before proceeding, we will first provide the formulas for the payoff functions and derive an important formula in Proposition 2. (1) and (2) make the game in fact predetermined by providing n, w and \(f_1(x_1,x_2)\) for \(x_1 \le x_2\). It is a straightforward exercise to provide explicit formulas for the payoff functions. We provide just the result here.

For an integer x let

$$\begin{aligned} \delta _{x} := \left\{ \begin{array}{c} 1 \text{ if } x \text{ is } \text{ even, } \\ \frac{1}{2} \text{ if } x \text{ is } \text{ odd. } \end{array} \right. \end{aligned}$$

In the case \(w=1\)

$$\begin{aligned} f_1(x_1,x_2) := \left\{ \begin{array}{ll} \frac{x_1 + x_2+1}{2}&{}\quad \text{ if } x_1 < x_2, \\ \frac{n+1}{2}&{}\quad \text{ if } x_1 = x_2, \\ n+1 - \frac{x_1 + x_2+1}{2}&{}\quad \text{ if } x_1 > x_2 \end{array}\right. \end{aligned}$$

and in the case \(w \in ] {0},{1} \, [ \)

$$\begin{aligned} f_1(x_1,x_2) = \left\{ \begin{array}{c} \frac{1-w^{x_1+1} }{1-w} + \frac{ 1- w^{ \lfloor \frac{x_2-x_1}{2} \rfloor } }{ 1- w} + \delta _{x_1+ x_2 + 1} w^{ \lfloor \frac{x_2-x_1}{2} \rfloor } - 1\quad \text{ if } x_1 < x_2, \\ \frac{ 1 + w -w^{x_1+1} - w^{n-x_1+1} }{2(1-w) }\quad \text{ if } x_1 = x_2, \\ \delta _{x_1 + x_2+1} w^{ \lfloor \frac{x_1 - x_2}{2} \rfloor } + \frac{1 - w^{ \lfloor \frac{x_1 - x_2}{2} \rfloor }}{1-w} + \frac{ 1- w^{n-x_1+1} }{1-w} - 1\quad \text{ if } x_1 > x_2. \end{array} \right. \end{aligned}$$

Notation: for a function \(g: H \rightarrow \mathbb {R}\), define \(\Delta g: H\setminus \{0\} \rightarrow \mathbb {R}\) by

$$\begin{aligned} \Delta g(x) := g(x) - g(x-1). \end{aligned}$$

It is important to have a formula for \(\Delta f_1^{(x_2)}(x_1)\). For this it is useful to define for \(i, m \in H\) with \(0 < i < m\) the function \(q_{i;m}: ] {0},{1} ] \rightarrow \mathbb {R}\) by

$$\begin{aligned} q_{i;m}(w) := w^i - \frac{1}{2} w^{ \lfloor \frac{m-i+1}{2} \rfloor }. \end{aligned}$$
(4)

Proposition 2

If \(0 < x_1 < x_2\), then \( \Delta f_1^{(x_2)}(x_1) = q_{x_1;x_2}(w)\).

Proof

If \(w=1\), then, by the formula for the payoff functions, \( f_1^{(x_2)}(x_1)- f_1^{(x_2)}(x_1-1) = \frac{1}{2} = q_{x_1;x_2}(1)\). Now suppose \(w \ne 1\). We have \( f_1^{(x_2)}(x_1-1) = \frac{1-w^{x_1} }{1-w} + \frac{ 1- w^{ \lfloor \frac{x_2-x_1+1}{2} \rfloor } }{ 1- w} + \delta _{x_1+x_2} w^{ \lfloor \frac{x_2-x_1+1}{2} \rfloor } - 1\) and \( f_1^{(x_2)}(x_1) = \frac{1-w^{x_1+1} }{1-w} + \frac{ 1- w^{ \lfloor \frac{x_2-x_1}{2} \rfloor } }{ 1- w} + \delta _{x_1+1+x_2} w^{ \lfloor \frac{x_2-x_1}{2} \rfloor } - 1\). Therefore \( f_1^{(x_2)}(x_1) - f_1^{(x_2)}(x_1-1) = \frac{ w^{x_1} + w^{ \lfloor \frac{x_2-x_1+1}{2} \rfloor } - w^{x_1+1} - w^{ \lfloor \frac{x_2-x_1}{2} \rfloor } }{ 1- w} - \delta _{x_1+x_2} w^{ \lfloor \frac{x_2-x_1+1}{2} \rfloor } +\) \( \delta _{x_1+1+x_2} w^{ \lfloor \frac{x_2-x_1}{2} \rfloor }\). Finally, distinguish between even and odd \(x_2-x_1\). \(\square \)

3 Symmetries

As the game is symmetric, we have

$$\begin{aligned} (e_1,e_2) \in E_w \; \Rightarrow \; (e_2,e_1) \in E_w. \end{aligned}$$
(5)

And with (2) we obtain

$$\begin{aligned} (e_1,e_2) \in E_w \; \Rightarrow \; (n-e_1,n-e_2) \in E_w. \end{aligned}$$
(6)

For the analysis and presentation it is convenient to define

$$\begin{aligned} \mathbf {H}^{\star } := \left\{ (x_1,x_2) \in H \times H \; | \; x_1 \le \lfloor \frac{n+1}{2} \rfloor \le x_2 \; \wedge x_1+x_2 \le n \right\} , \end{aligned}$$
$$\begin{aligned} E_w^{\star } := \mathbf {H}^{\star } \cap E_w. \end{aligned}$$
(7)

Proposition 3

Suppose \(w \ne 1\) or n is even. Let \(x \in H\).

  1. (1)

    \(x > \frac{n}{2} \; \Rightarrow \; R(x) \subseteq \{ 0, \ldots , x-1 \}\).

  2. (2)

    \(x < \frac{n}{2} \; \Rightarrow \; R(x) \subseteq \{ x+1, \ldots , n \}\).

  3. (3)

    \(x \ne \frac{n}{2} \; \Rightarrow \; x \not \in R(x)\).

  4. (4)

    If \((e_1,e_2) \in E_w\), then \(e_2 > \frac{n}{2} \; \Rightarrow \; e_1 \le \frac{n}{2}\), and \(e_2 < \frac{n}{2} \; \Rightarrow \; e_1 \ge \frac{n}{2}\).

  5. (5)

    If \((e_1,e_2) \in E_w\) with \(e_1=e_2\), then \(e_1=\frac{n}{2}\) and so n is even.

Proof

  1. 1.

    Fix \(x_1 \in R(x)\). Lemma 6(2a, 2b) implies \(x_1 \ne x\). We now prove by contradiction that \(x_1 \le x-1\) and then the proof is complete. So suppose \(x_1 \ge x\). As \(x_1 \ne x\), we have \(\frac{n}{2} < x < x_1 \le n\) and \( 1 \le x_1 - x \le n -x\). By Lemma 6(3), \(f_1^{(x)}(x-(x_1-x)) > f^{(x)}_1(x+(x_1-x))= f^{(x)}_1(x_1) \). Thus \(x_1 \not \in R(x)\), a contradiction.

  2. 2.

    Suppose \( x < \frac{n}{2}\). As \(n -x > \frac{n}{2}\), part 1 implies \(R(n-x) \subseteq \{ 0, \ldots , n-x -1 \}\). So, by (3), \(\{ n \} - R(x) \subseteq \{0,\ldots , n-x-1 \}\). This implies the desired result.

  3. 3.

    By parts 1 and 2.

  4. 4.

    First statement: by contradiction suppose \( e_2 > \frac{n}{2}\) and \(e_1 > \frac{n}{2}\). As \(e_2 \in R(e_1)\) and \(e_1 \in R(e_2)\), part 1 implies \(e_2 < e_1\) and \(e_1 < e_2\). This is absurd. Second statement: by contradiction suppose \( e_2 < \frac{n}{2}\) and \(e_1 < \frac{n}{2}\). As \(e_2 \in R(e_1)\) and \(e_1 \in R(e_2)\), part 2 implies \(e_2 > e_1\) and \(e_1 > e_2\). This is absurd.

  5. 5.

    Now \(e_1 \in R(e_2) = R(e_1)\). Apply part 3. \(\square \)

Notation: for \(A \subseteq H \times H\), let \( \tilde{A} := \{ (x_2,x_1) \; | \; (x_1,x_2) \in A \}\).

Theorem 1

For each positive integer n and \(w \in ] {0},{1} ] \): if \(w \ne 1\) or n is even, then \( E_w = E_w^{\star } \cup \widetilde{E_w^{\star }} \cup ( (n,n) - E_w^{\star } ) \cup ( (n,n) - \widetilde{E_w^{\star }} )\).

Proof

(5) and (6) imply ’\(\supseteq \)’. For example, suppose \((x_1,x_2) \in (n,n) - \widetilde{E_w^{\star }}\). Let \((y_1,y_2) \in \widetilde{E_w^{\star }}\) be such that \((x_1,x_2) = (n-y_1,n-y_2)\). By (5) and (6), \((n-y_1,n-y_2) \in E_w\). Now we prove ’\(\subseteq \)’.

If \(w=1\), then n is even and Proposition 1 implies the desired result. Now suppose \(w \ne 1\), \((e_1,e_2) \in E_w\) and \((e_1,e_2) \not \in E_w^{\star }\). We will prove that \((e_1,e_2) \in \widetilde{E_w^{\star }}\) or \((e_1,e_2) \in (n,n) - E_w^{\star } \) or \((e_1,e_2) \in (n,n) - \widetilde{E_w^{\star }} \).

Well, as \((e_1,e_2) \not \in E_w^{\star }\), we have \(\lnot (e_1 \le \lfloor \frac{n+1}{2} \rfloor \le e_2)\) or \(e_1+ e_2 > n\). We distinguish between three cases.

  • Case \(\lnot (e_1 \le \lfloor \frac{n+1}{2} \rfloor \le e_2)\) and \(e_1+ e_2\le n\): Subcase \(e_1 > \lfloor \frac{n+1}{2} \rfloor \): \(e_2 \le n - e_1 < n - \lfloor \frac{n+1}{2} \rfloor \le \lfloor \frac{n+1}{2} \rfloor \). Subcase \(e_2 < \lfloor \frac{n+1}{2} \rfloor \wedge e_1 \le \lfloor \frac{n+1}{2} \rfloor \): Proposition 3(3, 4) implies in the case n is even that \(e_2 \le \frac{n}{2}-1 \wedge e_1 = \frac{n}{2}\) and in the case n is odd that \(e_2 \le \frac{n-1}{2} \wedge e_1 = \frac{n+1}{2}\). Thus \(e_2 \le \lfloor \frac{n+1}{2} \rfloor \le e_1\). It follows that \((e_2,e_1) \in E_w^{\star }\) and thus \((e_1,e_2) \in \widetilde{E_w^{\star }}\).

  • Case \(e_1 \le \lfloor \frac{n+1}{2} \rfloor \le e_2\) and \(e_1+ e_2 > n\): Subcase n is even: \(e_1 \le \frac{n}{2} \le e_2\), so \(n-e_2 \le n - \frac{n}{2} = \lfloor \frac{n+1}{2} \rfloor \le n - e_1\). Subcase n is odd: \(e_1 \le \frac{n+1}{2} \le e_2\) and therefore \(n-e_2 \le n - \frac{n+1}{2} = \frac{n-1}{2}\). As \(e_2 \ge \frac{n+1}{2}\), Proposition 3(4) implies \(e_1 \le \frac{n}{2}\), and as n is odd, \(e_1 \le \frac{n-1}{2}\). Thus \(n - e_2 \le \lfloor \frac{n+1}{2} \rfloor \le n - e_1\). It follows that \((n-e_2,n-e_1) \in E_w^{\star }\). So \((n-e_1,n-e_2) \in \widetilde{E_w^{\star }}\) and thus \((e_1,e_2) = (n,n) - (n- e_1, n-e_2) \in (n,n) - \widetilde{E_w^{\star }}\).

  • Case \(\lnot (e_1 \le \lfloor \frac{n+1}{2} \rfloor \le e_2)\) and \(e_1+ e_2 > n\): Subcase \(e_1 > \lfloor \frac{n+1}{2} \rfloor \): now \(n-e_1 < n - \lfloor \frac{n+1}{2} \rfloor = \lfloor \frac{n}{2} \rfloor \). By Proposition 3(4), \(e_2 \le \frac{n}{2}\) and so \(n -e_2 \ge \frac{n}{2}\). As \(n-e_2\) is an integer, we have \(n -e_2 \ge \lfloor \frac{n+1}{2} \rfloor \). Subcase \(e_2 < \lfloor \frac{n+1}{2} \rfloor \): \(n -e_2 > n - \lfloor \frac{n+1}{2} \rfloor = \lfloor \frac{n}{2} \rfloor \). So \(n - e_2 \ge \lfloor \frac{n+2}{2} \rfloor \). Also \(n - e_1 < e_2 < \lfloor \frac{n+1}{2} \rfloor \). Thus \(n-e_1 \le \lfloor \frac{n+1}{2} \rfloor \le n-e_2\). It follows that \((n-e_1,n-e_2) \in E_w^{\star }\). Thus \((e_1,e_2) = (n,n) - (n- e_1, n-e_2) \in (n,n) - E_w^{\star }\). \(\square \)

As Proposition 1(4) shows, Theorem 1 does not hold if \(w=1\) and n is odd.

4 Main result

Having Theorem 1, we can state the main theorem; for its proof see the next section. In order to state the theorem it is convenient to introduce some objects: the function \(w: \mathbb {R}_+ \cup \{ + \infty \} \rightarrow \mathbb {R}\) is defined by

$$\begin{aligned} w_x := 2^{-1/x} \; ( x \in \mathbb {R}_+\setminus \{ 0 \}), \; w_0 := 0, \; w_{\infty } := 1. \end{aligned}$$

Note that w is strictly increasing. Given n, for an integer \(k \ge 0\), put

$$\begin{aligned} \mathbf {a}_k := (p-k,p+k), \;\; \mathbf {b}_k^- := (p-k-1,p+k), \;\; \mathbf {b}_k^+ := (p-k,p+k+1). \end{aligned}$$

The next theorem presents the contents of the sets \(E_w^{\star }\). Together with Theorem 1 this provides all Nash equilibrium sets in the case \(w \ne 1\) or n is even; for the case where \(w=1\) and n is odd see Proposition 1(4).

Theorem 2

For each positive integer n and for every \(w \in ] {0},{1} ] \) the Hotelling bi-matrix game has a Nash equilibrium. Even:

  1. I.

    Suppose n is even.

    1. (a)

      \(w \in ] {w_{p-2k}},{w_{p-2k+1}} \, [ \) with \(k \ge 1\) s.t. \(p-2k \ge 0\): \( E_w^{\star } = \{ \mathbf {a}_k \}\).

    2. (b)

      \(w \in ] {w_{p-2k-1}},{w_{p-2k}} \, [ \) with \(k \ge 0\) s.t. \(p-2k-1 \ge 0\): \( E_w^{\star } = \{ \mathbf {b}_k^- \}\).

    3. (c)

      \(w= w_{p-2k-1}\) with \(k \ge 0\) s.t. \(p-2k-1 > 0\): \(E_w^{\star } = \{ \mathbf {b}_k^-, \; \mathbf {a}_{k+1} \}\).

    4. (d)

      \(w= w_{p-2k}\) with \(k \ge 0\) s.t. \(p-2k > 0\): \( E_w^{\star } = \{ \mathbf {b}_k^-, \; \mathbf {a}_{k} \}\).

    5. (e)

      \(w \in ] {w_p},{w_{\infty }} ] \): \( E_w^{\star } = \{ \mathbf {a}_0 \}\).

  2. II.

    Suppose n is odd.

    1. (a)

      \(w \in ] { w_{p-2k-1} },{ w_{p-2k+1} } \, [ \setminus \{ w_{p-2k} \} \) with \(k \ge 1\) s.t. \(p- 2k + 1 > 0\): \( E^{\star }_ w = \{ \mathbf {b}_k^+ \}\).

    2. (b)

      \(w = w_{p-2k}\) with \(k \ge 1\) s.t. \(p-2k > 0\): \( E^{\star }_ w = \{ \mathbf {b}_k^-, \;\; \mathbf {b}_k^+ \}\).

    3. (c)

      \(w = w_{p-2k+1}\) with \(k \ge 1\) s.t. \(p-2k+1 > 0\): \( E^{\star }_ w = \{ \mathbf {a}_k, \; \mathbf {b}_{k-1}^+, \; \mathbf {b}_k^+ \}\).

    4. (d)

      \(w \in ] {w_{p-1}},{w_{\infty }} \, [ \) with \(p-1 > 0\): \( E^{\star }_ w = \{ \mathbf {b}_0^+ \}\).

    5. (e)

      \(w= w_{\infty }\): \( E_w^{\star } = \{ \mathbf {b}_0^+ \}\).

Remark: always \(w > 0\). In particular this holds in Theorem 2(IIa) (in case \(p=2k\)) and in for example Lemma 4(1) below (in case \(p=1\)).

5 Proof of Theorem 2

5.1 First-order conditions and their consequences

For \(x_1, x_2 \in H\) with \(0 < x_1 <n\), we have the following first-order condition:

$$\begin{aligned} x_1 \in R(x_2) \; \Rightarrow \; \Delta f_1^{(x_2)} (x_1+1) \le 0 \le \Delta f_1^{(x_2)} (x_1). \end{aligned}$$
(8)

Indeed: as \(x_1 \in R(x_2) = R_1(x_2)\), we have \(\Delta f_1^{(x_2)} (x_1) = f_1^{(x_2)}(x_1) - f_1^{(x_2)}(x_1-1) \ge 0\) and \(\Delta f_1^{(x_2)} (x_1+1) = f_1^{(x_2)}(x_1+1) - f_1^{(x_2)}(x_1) \le 0\).

Proposition 4

Suppose \(x_2 \in H\). If \(n \ge 3\), then \(R(x_2) \subseteq \{ 1, \ldots , n - 1\}\).

Proof

For \(w=1\), apply Proposition 1. Suppose \(w \ne 1\). Suppose \(0 \in R(x_2)\). Proposition 3(2) applies and implies \(x_2 \ge \frac{n}{2}\). As \(n \ge 3\), we obtain \(0 < 1 < x_2 \le n\). As \(x_2 \ge 2\) we have \( q_{1;x_2}(w) = w^1 - \frac{1}{2} w^{ \lfloor \frac{x_2}{2} \rfloor } > w - w^{ \lfloor \frac{x_2}{2} \rfloor } \ge 0\). So, by Proposition 2, \(0 < q_{1;x_2}(w) = \Delta f_1^{(x_2)}(1) = f_1^{(x_2)}(1) - f_1^{(x_2)}(0)\), which is a contradiction with \(0 \in R(x_2)\). Thus \(0 \not \in R(x_2)\). (3) implies \(n \not \in R(x_2)\). \(\square \)

So if \(n \ge 3\), then we see with (8) and Proposition 4 that for \((x_1,x_2) \in E_w\) we have \(\Delta f_1^{(x_2)} (x_1) \ge 0 \ge \Delta f_1^{(x_2)} (x_1+1)\) and \(\Delta f_1^{(x_1)} (x_2) \ge 0 \ge \Delta f_1^{(x_1)} (x_2+1)\).

Theorem 3

For each positive integer n, \(w \in ] {0},{1} ] \) and \((e_1,e_2) \in E_w\) we have \(e_1+e_2 \in \{ n-2, n-1, n, n+1, n+ 2\}\). Even:

  1. (1)

    if n is even and \(e_2-e_1\) is even, then \(e_1+e_2 =n\);

  2. (2)

    if n is even and \(e_2-e_1\) is odd, then \(e_1+e_2 \in \{ n-1, n+1 \}\);

  3. (3)

    if n is odd and \(e_2-e_1\) is even, then \(e_1+e_2 \in \{ n-1, n+1 \}\);

  4. (4)

    if n is odd and \(e_2-e_1\) is odd, then \(e_1+e_2 \in \{ n-2, n, n+2 \}\).

Proof

For \(n=1\), the statements are almost trivial. Example 1 shows that the statements also hold for \(n=2\). For \(w=1\) the statements hold by Proposition 1. Further suppose \(n \ge 3\) and \(w \ne 1\). It is sufficient to prove the statements for \((e_1,e_2) \in E_w^{\star }\). So fix \((e_1,e_2) \in E_w^{\star }\).

If \(e_2=e_1\), then, by Proposition 3(5), n is even and \(e_1=e_2 = \frac{n}{2}\); so then the statements hold. Now further suppose \(e_1 \ne e_2\). This implies \( e_1 < e_2\). By Proposition 4, \(e_1 > 0\) and \(e_2 < n\). We distinguish between two cases.

  • Case \(e_2 - e_1 = 1\): if \(e_1 = \lfloor \frac{n+1}{2}\rfloor \), then \(e_1 + e_2 = 2 \lfloor \frac{n+1}{2} \rfloor + 1\) and so the statements hold. Now suppose \(e_1 < \lfloor \frac{n+1}{2} \rfloor \). This implies \(e_1 < \frac{n}{2}\). Proposition 3(4) implies \(e_2 \ge \frac{n}{2}\) and it follows that \((e_1,e_2) = (\frac{n}{2}-1, \frac{n}{2})\) if n is even and \((e_1,e_2) = (\frac{n-1}{2}, \frac{n+1}{2})\) if n is odd. So again the statements hold.

  • Case \(e_2 - e_1 \ge 2\): (8) implies

    $$\begin{aligned} \Delta f_1^{(e_2)}(e_1+1) \le 0 \le \Delta f_1^{(e_2)}(e_1) \; \wedge \; \Delta f_1^{(e_1)}(e_2+1) \le 0 \le \Delta f_1^{(e_1)}(e_2). \end{aligned}$$

    Subcase \(e_2-e_1\) is even: Lemma 8(1) gives

    $$\begin{aligned} w^{\frac{2n-3e_2+e_1}{2}} \ge \frac{1}{2} \ge w^{\frac{3e_1-e_2+2}{2}} \text{ and } w^{\frac{3e_1-e_2}{2}} \ge \frac{1}{2} \ge w^{\frac{2n-3e_2+e_1+2}{2}}. \end{aligned}$$

    As \(w \ne 1\), this implies \(2n-3e_2+e_1 \le 3e_1-e_2+2\) and \(3e_1-e_2 \le 2n-3e_2+e_1+2\). From this, \(n-1 \le e_1+ e_2 \le n+1\). Thus \(e_1 + e_2 \in \{ n-1,n,n+1 \}\). Subcase \(e_2-e_1\) is odd: Lemma 8(2) gives

    $$\begin{aligned} w^{\frac{2n-3x_2+x_1-1}{2}} \ge \frac{1}{2} \ge w^{\frac{3x_1-x_2+3}{2}} \text{ and } w^{\frac{3x_1-x_2-1}{2}} \ge \frac{1}{2} \ge w^{\frac{2n-3x_2+x_1+3}{2}}. \end{aligned}$$

    This finally implies \( e_1+e_2 \in \{n-2, n-1, n, n+1, n+2 \}\). Having the above results, the other desired results also follow. \(\square \)

5.2 Demi-modality

In this subsection we identify situations where the first-order conditions (8) also are sufficient.

Lemma 1

Suppose \(i,m \in H\) with \(0< i < m\).

  1. (1)

    If \(q_{i;m}(w) \le 0\), then \(q_{k;m}(w) < 0\) for \(i < k < m\).

  2. (2)

    If \(q_{i;m}(w) \ge 0\), then \(q_{l;m}(w) > 0\) for \(0 < l < i\).

Proof

  1. 1.

    As \(i < k\), we have \(i \le k-1\) and therefore \(-(3i -2k) - (- k) = -3(i-k) \ge 3\). This implies \( \lfloor \frac{m - (3i-2k) + 1}{2} \rfloor > \lfloor \frac{m - k +1}{2}\rfloor \). Note that \(w \ne 1\) and \(w^i \le \frac{1}{2} w^{ \lfloor \frac{m-i+1}{2} \rfloor }\). Now \(w^k = w^i w^{k-i} \le \frac{1}{2} w^{ \lfloor \frac{m-i+1}{2} \rfloor + k - i } = \frac{1}{2} w^{ \lfloor \frac{m - (3i-2k) + 1}{2} \rfloor } < \frac{1}{2} w^{ \lfloor \frac{m - k +1}{2} \rfloor }\). Thus \(q_{k;m}(w) > 0\).

  2. 2.

    This follows from part 1.

\(\square \)

Proposition 5

Suppose \(x_1, x_2 \in H\) with \( 0< x_1 < x_2\).

  1. (1)

    If \(\Delta f_1^{(x_2)}(x_1) \ge 0\), then \(\Delta f_1^{(x_2)}(j) > 0 \; (1 \le j \le x_1-1)\).

  2. (2)

    If \(\Delta f_1^{(x_2)}(x_1) \le 0\), then \(\Delta f_1^{(x_2)}(j) < 0 \; (x_1+1 \le j \le x_2-1)\).

Proof

Apply Proposition 2 and Lemma 1. \(\square \)

Now we are ready to prove the next theorem which gives necessary and sufficient conditions for various \((x_1,x_2) \in \mathbf {H}^{\star }\) to be an equilibrium. For its proof, we first study demi-modality properties of the conditional payoff functions; this will be done by using Propositions 3 and 5.

We call a function \(g: H \rightarrow \mathbb {R}\) demi-modal if there exists \(r \in H\) such that \(g \upharpoonright \{0, \ldots , r \}\) is increasing and \(g(x) < g(r) \; (r < x \le n)\).

Lemma 2

  1. 1.

    Fix \(x_2 \in H\) with \(x_2 > \frac{n}{2}\). If there exists \(x_1 \in H\) with \(0< x_1 < x_2\) such that \(\Delta f_1^{(x_2)}(x_1+1) \le 0 \le \Delta f_1^{(x_2)}(x_1)\), then \(f_1^{(x_2)}\) is demi-modal and \(x_1\) is a maximizer of \(f_1^{(x_2)}\).

  2. 2.

    Fix \(x_1 \in H\) with \(x_1 < \frac{n}{2}\). If there exists \(x_2 \in H\) with \(x_1 < x_2 < n\) such that \(\Delta f_1^{(x_1)}(x_2+1) \le 0 \le \Delta f_1^{(x_1)}(x_2)\), then \(f_1^{(x_1)}\) is demi-modal and \(x_2\) is a maximizer of \(f_1^{(x_1)}\).

Proof

  1. 1.

    By Proposition 5(1), \(\Delta f_1^{(x_2)}(j) > 0 \; (1 \le j \le x_1-1)\). Together with \(\Delta f_1^{(x_2)}(x_1) \ge 0\) this implies that \(f_1^{(x_2)} \upharpoonright \{ 0, \ldots , x_1 \}\) is increasing. So \(x_1\) is a maximiser of \(f_1^{(x_2)} \upharpoonright \{ 0, \ldots , x_1 \}\). We distinguish between two cases.

    • Case where \(x_1 = x_2 -1\): Subcase \(w=1\) and n is odd: as \(x_2 \ge p+1\), Proposition 1(2) implies that each maximizer of \(f_1^{(x_2)}\) is in \(\{x_1, x_1+1 \}\). If \(f_1^{(x_2)}(x_1+1) < f_1^{(x_2)}(x_1)\), then \(f_1^{(x_2)}(x) < f_1^{(x_2)}(x_1) \; (x_1 < x \le n)\) and thus \(x_1\) is a maximiser of \(f_1^{(x_2)}\) and \(f_1^{(x_2)}\) is demi-modal. If \(f_1^{(x_2)}(x_1+1) = f_1^{(x_2)}(x_1)\), then \(f_1^{(x_2)} \upharpoonright \{ 0, \ldots , x_1+1 \}\) is increasing and\(f_1^{(x_2)}(x) < f_1^{(x_2)}(x_1+1) \; (x_2 < x \le n)\); also now \(x_1\) is a maximiser of \(f_1^{(x_2)}\) and \(f_1^{(x_2)}\) is demi-modal. Subcase \(w \ne 1\) or n is even: as \(x_2 > \frac{n}{2}\), we know by Proposition 3(1) that each maximizer of \(f_1^{(x_2)}\) is in \(\{0, \ldots , x_1 \}\). This implies that \(x_1\) is a maximiser of \(f_1^{(x_2)}\) and that \(f_1^{(x_2)}\) is demi-modal.

    • Case where \(x_1 \le x_2 -2\): by Proposition 5(2), \( \Delta f_1^{(x_2)}(j) < 0 \; (x_1+2 \le j \le x_2-1)\). Together with \(\Delta f_1^{(x_2)}(x_1+1) \le 0\) this implies that \(f_1^{(x_2)} \upharpoonright \{ x_1, \ldots , x_2 -1\}\) is decreasing and that \(f_1^{(x_2)} \upharpoonright \{ x_1+1, \ldots , x_2 -1\}\) is strictly decreasing. Thus \(x_1\) is even a maximizer of \(f_1^{(x_2)} \upharpoonright \{0,1, \ldots , x_2-1 \}\). Subcase \(w=1\) and n is odd: as \(x_2 \ge p + 1\), Proposition 1(2) implies that each maximizer of \(f_1^{(x_2)}\) is in \(\{x_2- 1, x_2 \}\). As \(f_1^{(x_2)}\) has a maximizer and \(f_1^{(x_2)}(x_2-1) = x_2 \ge p+1 = f_1^{(x_2)}(x_2) \), it follows that \(x_2-1\) is a maximizer of \(f_1^{(x_2)}\). As \(f_1^{(x_2)}(x_1) \ge f_1^{(x_2)}(x_2-1)\), also \(x_1\) is a maximizer of \(f_1^{(x_2)}\). It follows that \(x_1 = x_2-1\) or \(x_1 =x_2-2\). As \(x_1 \in \{ x_2-1,x_2 \}\), \(x_1=x_2-1\) holds. As this is a contradiction, this subcase cannot occur. Subcase \(w \ne 1\) or n is even: as \(x_2 > \frac{n}{2}\), we know by Proposition 3(1) that each maximizer of \(f_1^{(x_2)}\) is in \(\{0, \ldots , x_2- 1 \}\). As \(f_1^{(x_2)}\) has a maximizer and we already know that \(x_1\) is a maximiser of \(f_1^{(x_2)} \upharpoonright \{0,\ldots ,x_2-1\}\), it follows that \(x_1\) is a maximizer of \(f_1^{(x_2)}\). If \(f_1^{(x_2)}(x_1+1) < f_1^{(x_2)}(x_1)\), then \(f_1^{(x_2)}(x) < f_1^{(x_2)}(x_1) \; (x_1 < x \le n)\) and thus \(f_1^{(x_2)}\) is demi-modal. If \(f_1^{(x_2)}(x_1+1) = f_1^{(x_2)}(x_1)\), then \(x_1+1\) also is a maximizer of \(f_1^{(x_2)}\), \(f_1^{(x_2)} \upharpoonright \{ 0, \ldots , x_1 +1 \}\) is increasing and \(f_1^{(x_2)}(x) < f_1^{(x_2)}(x_1+1) \; (x_1+1 < x \le n)\); also now \(f_1^{(x_2)}\) is demi-modal.

  2. 2.

    Note that \(0 < n- x_2 < n-x_1\) and \(n- x_1 > \frac{n}{2}\). By Lemma 7(1), \( \Delta f_1^{(n-x_1)}(n-x_2+1) = - \Delta f_1^{(x_1)}(x_2) \le 0 \le - \Delta f_1^{(x_1)}(x_2+1) = \Delta f_1^{(n-x_1)}(n-x_2)\). By part 1, \(n-x_2 \in R(n-x_1)\). Thus, by (3), \(x_2 \in R(x_1)\). \(\square \)

Theorem 4

For each positive integer n, \(w \in ] {0},{1} ] \) and \((x_1,x_2) \in H \times H\) with \( 0 < x_1 < \frac{n}{2} < x_2 < n\) the following two statements are equivalent:

  1. (a)

    \((x_1,x_2) \in E_w\);

  2. (b)

    \(\Delta f_1^{(x_2)}(x_1) \ge 0 \ge \Delta f_1^{(x_2)}(x_1+1) \text{ and } \Delta f_1^{(x_1)}(x_2) \ge 0 \ge \Delta f_1^{(x_1)}(x_2+1)\).

Proof

Note \((x_1,x_2) \in E_w \; \Leftrightarrow \; x_1 \in R(x_2) \wedge x_2 \in R(x_1)\). By (8), a implies b. And b implies a by Lemma 2. \(\square \)

5.3 Analysing the inequalities in Theorem 4(b)

Lemma 3

Suppose \(x_1, x_2 \in H\) with \(0< x_1 < \frac{n}{2} < x_2 < n\) and \(x_2-x_1 \ge 2\).

  1. 1.

    Suppose n is even.

    1. (a)

      If \(x_1+x_2 = n-1\), then \((x_1,x_2) \in E_w \; \Leftrightarrow \; w^{ 2+ 2 x_1 - p } \le \frac{1}{2} \le w^{ 1+ 2 x_1- p}\).

    2. (b)

      If \(x_1+x_2 = n\), then \((x_1,x_2) \in E_w \; \Leftrightarrow \; w^{ 1+ 2 x_1- p } \le \frac{1}{2} \le w^{ 2x_1-p }\).

  2. 2.

    Suppose n is odd.

    1. (a)

      If \(x_1+x_2 = n-2\), then \((x_1,x_2) \in E_w \; \Leftrightarrow \; w^{ 2x_1 + 2 -p } = \frac{1}{2}\).

    2. (b)

      If \(x_1+x_2 = n-1\), then \((x_1,x_2) \in E_w \; \Leftrightarrow \; w^{ 2x_1 + 1 -p } = \frac{1}{2}\).

    3. (c)

      If \(x_1+x_2 = n\), then \((x_1,x_2) \in E_w \; \Leftrightarrow \; w^{ 2x_1 + 1 -p } \le \frac{1}{2} \le w^{ 2x_1 -1 -p } \).

Proof

1a. Now \(x_2-x_1\) is odd. By Theorem 4 and Lemma 8(2), \((x_1,x_2) \in E_w\) if and only if

$$\begin{aligned} w^{\frac{3x_1-x_2+3}{2}} \le \frac{1}{2} \wedge w^{\frac{3x_1-x_2-1}{2}} \ge \frac{1}{2} \wedge w^{\frac{2n-3x_2+x_1-1}{2}} \ge \frac{1}{2} \wedge w^{\frac{2n-3x_2+x_1+3}{2}} \le \frac{1}{2}. \end{aligned}$$

As \(x_1+x_2=n-1\), this is equivalent to

$$\begin{aligned} w^{\frac{4+4x_1-n}{2}} \le \frac{1}{2} \wedge w^{\frac{4x_1-n}{2}} \ge \frac{1}{2} \wedge w^{\frac{2+4x_1-n}{2}} \ge \frac{1}{2} \wedge w^{\frac{6+4x_1-n}{2}} \le \frac{1}{2}, \end{aligned}$$

so to, as desired, \(w^{\frac{4 + 4x_1-n}{2}} \le \frac{1}{2} \le w^{\frac{2+4x_1-n}{2}}\).

1b, 2a–2c. Analogous to 1a. \(\square \)

Lemma 4

Suppose n is even.

  1. 1.

    \(w \in ] {w_{p-2} },{ w_p} \, [ \; \Rightarrow \; R(p) = \{ p-1, p+1 \}\).

  2. 2.

    \(w = w_p \; \Rightarrow \; R(p) = \{ p-1, p, p+1 \}\).

Proof

Example 1 shows that the statements hold if \(p=1\). Now further suppose \(p \ge 2\) and \(w \in ] {w_{p-2}},{w_p} ] \). By Lemma 9(1a), \( \Delta f_1^{(p)}(p) = - \Delta f_1^{(p)}(p+1) \le 0\), and \(\Delta f_1^{(p)}(p) = 0 \; \Leftrightarrow \; w = w_p\). By Lemma 9(1b), \(\Delta f_1^{(p)}(p-1) = w ( w^{p-2} - \frac{1}{2} ) > 0\). Proposition 5(1) implies \(\Delta f_1^{(p)}(j) > 0 \; (1 \le j \le p-1)\). As, by Lemma 7(1), \(\Delta f_1^{(p)} (p+k) = -\Delta f_1^{(p)} (p-k+1) \; ( 1-p \le k \le p) \), we have \(\Delta f_1^{(p)} (p+1) \ge 0\) and \(\Delta f_1^{(p)} (j) < 0 \; (p+2 \le j \le n)\). So the desired results follow. \(\square \)

Remark   Theorem 3 directly implies that in part 1 of the next lemma for \((x_1,x_2) \in E_w^{\star }\) precisely one of the 4 cases ai, bi, ci, di holds. It is easy to see that the same also holds for part 2; here for example \(x_1+x_2=n \wedge x_2-x_1=n-2\) is impossible as this would imply that \((x_1,x_2) \not \in E_w^{\star }\).

Lemma 5

In each of the 8 cases below, the statements i and ii are equivalent.

  1. 1.

    Suppose n is even and \((x_1,x_2) \in H \times H\).

    1. (a)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \; \wedge \; x_2-x_1 \ge 2 \; \wedge \; x_1+ x_2 = n-1\).

      2. ii.

        There exists an integer \( k \ge 1\) with \( p-2k- 1 \ge 0\) such that \((x_1,x_2) = (p-k-1,p+k)\) and \(w \in [w_{p-2k-1}, w_{p-2k} ]\).

    2. (b)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \; \wedge \; x_2-x_1 \ge 2 \; \wedge \; x_1+ x_2 = n\).

      2. ii.

        There exists an integer \( k \ge 1\) with \( p-2k \ge 0\) such that \((x_1,x_2) = (p-k,p+k)\) and \(w \in [w_{p-2k}, w_{p-2k+1} ]\).

    3. (c)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \; \wedge \; x_2-x_1 =1\).

      2. ii.

        \((x_1,x_2) = (p-1,p)\) and \(w \in [w_{p-1}, w_p]\).

    4. (d)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \; \wedge \; x_2-x_1 =0\).

      2. ii.

        \((x_1,x_2) = (p,p)\) and \(w \in [w_p, 1]\).

  2. 2.

    Suppose n is odd and \((x_1,x_2) \in H \times H\).

    1. (a)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \wedge x_2 - x_1 \ge 2 \wedge x_1+x_2 = n-2\).

      2. ii.

        There exists an integer \(k \ge 1\) with \(p-2k > 0\) such that \((x_1,x_2) = (p-k-1,p+k)\) and \(w = w_{p-2k}\).

    2. (b)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \wedge x_2 - x_1 \ge 2 \wedge x_1+x_2 = n-1\).

      2. ii.

        There exists an integer \(k \ge 1\) with \(p-2k+1 > 0\) such that \((x_1,x_2) = (p-k,p+k)\) and \(w = w_{p-2k+1}\).

    3. (c)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \wedge x_2 - x_1 \ge 2 \wedge x_1+x_2 = n\).

      2. ii.

        There exists an integer \(k \ge 1\) with \(p-2k+1 > 0\) such that \((x_1,x_2) = (p-k,p+k+1)\) and \(w \in [w_{p-2k-1}, w_{p-2k+1} ]\).

    4. (d)
      1. i.

        \((x_1,x_2) \in E_w^{\star } \wedge x_2 - x_1 =1 \wedge x_1+x_2 = n\).

      2. ii.

        \((x_1,x_2) = (p,p+1)\) and \(w \in [w_{p-1},1]\).

Proof

  1. 1a.

    ‘\(i \Rightarrow ii\)’: as also \(x_1 \le p \le x_2\), it follows that \(x_1 < p-1\) and \(p< x_2\) and \(n \ge 4\). Proposition 4 implies \(0 < x_1\) and \(x_2 < n\). Let \(k \ge 1\) be the unique integer such that \((x_1,x_2) = (p-k-1,p+k)\). By Lemma 3(1a), \(w^{p-2k} \le \frac{1}{2} \le w^{p-2k-1}\). This implies \(p-2k > 0\); so \(p-2k -1 \ge 0\). This in turn implies \(w \in [w_{p-2k-1}, w_{p-2k}]\). ‘\(ii \Rightarrow i\)’: the proof is complete if we can show that \((x_1,x_2) \in E_w\). Well, as \(w^{p-2k} \le \frac{1}{2} \le w^{p-2k-1}\), this follows from Lemma 3(1a).

  2. 1b.

    Analogous to 1a.

  3. 1c.

    ‘\( i \Rightarrow ii\)’: Theorem 3(2) implies \(x_1 + x_2 = n-1\). With this it is clear that \((x_1,x_2) = (p-1,p)\). If \(p=1\), then Example 1 shows that \(w \in [w_0, w_1]\). Now further suppose \(p \ge 2\). As \(p-1 \in R(p)\) and \(p \in R(p-1)\), (8) implies

    $$\begin{aligned} \Delta f_1^{(p)}(p-1) \ge 0 \ge \Delta f_1^{(p)}(p) \; \; \wedge \; \; \Delta f_1^{(p-1)}(p) \ge 0 \ge \Delta f_1^{(p-1)}(p+1). \end{aligned}$$

    which by Lemma 9(1a–1d) is equivalent to

    $$\begin{aligned} w^{p-1} - \frac{w}{2} \ge 0 \ge w^p - \frac{1}{2} \; \wedge \; -w^{p+1} + \frac{1}{2} \ge 0 \ge -w^p + \frac{1}{2} w. \end{aligned}$$

    Finally, this is equivalent to \(w \in [w_{p-1}, w_p]\). ‘\(ii \Rightarrow i\)’: the proof is complete if we can show that \(p-1 \in R(p)\) and \(p \in R(p-1)\). Well, Lemma 4(1,2) implies \(p-1 \in R(p)\). As (see the above) \(\Delta f_1^{(p-1)}(p+1) \le 0 \le \Delta f_1^{(p-1)}(p)\), Lemma 2(2) implies \(p \in R(p-1)\).

  4. 1d.

    ‘\( i \Rightarrow ii\)’: Theorem 3(1) implies \(x_1 + x_2 = n\). With this it is clear that \((x_1,x_2) = (p,p)\). If \(p=1\), then Example 1 shows that \(w \in [w_p, 1]\). Now further suppose \(p \ge 2\). As \(p \in R(p)\), (8) implies \( \Delta f_1^{(p)}(p) \ge 0 \ge \Delta f_1^{(p)}(p+1)\) which by Lemma 9(1a) is equivalent to \(w^p - \frac{1}{2} \ge 0 \ge \frac{1}{2} - w^p\), so to \(w \in [w_p,1]\). ‘\(ii \Rightarrow i\)’: the proof is complete if we can show that \((p,p) \in E_w\). As \( \Delta f_1^{(p)}(p) \ge 0 \text{ and } \Delta f_1^{(p)}(p+1) = \frac{1}{2} - w^p \le 0\), Lemma 2(2) implies \(p \in R(p)\).

  5. 2a.

    ‘\(i \Rightarrow ii\)’: so \(p \ge 1\) and therefore \(n \ge 3\). As \(x_1 \le p+1 \le x_2\), it follows that \(x_1 \le p-2\). Proposition 4 implies \(0 < x_1\) and \(x_2 < n\). Let \(k \ge 1\) be the unique integer such that \((x_1,x_2) = (p-k-1,p+k)\). By Lemma 3(2a), \( w^{ p-2k } = \frac{1}{2}\). This implies \(p-2k > 0\); so \(p-2k \ge 1\) and \(w = w_{p-2k}\). ‘\(ii \Rightarrow i\)’: the proof is complete if we can show that \((x_1,x_2) \in E_w\). Well, as \(w =w_{p-2k}\), this follows from Lemma 3(2a).

  6. 2b,

    2c. Analogous to 2a.

  7. 2d.

    ‘\( i \Rightarrow ii\)’: \((x_1,x_2) = (p,p+1)\). So if \(n=1\), then the proof is complete. Now suppose \(n \ge 3\), so \(p \ge 1\). As \(p \in R(p+1)\) and \(p+1 \in R(p)\), (8) implies

    $$\begin{aligned} \Delta f_1^{(p+1)}(p) \ge 0 \ge \Delta f_1^{(p+1)}(p+1) \; \wedge \; \Delta f_1^{(p)}(p+1) \ge 0 \ge \Delta f_1^{(p)}(p+2). \end{aligned}$$
    (9)

    With Lemma 9(2a,2b) these inequalities are equivalent to

    $$\begin{aligned} w (w^{p-1} - \frac{1}{2} ) \ge 0 \ge \frac{1}{2} (w^{p+1} - 1) \; {\wedge } -\frac{1}{2} (w^{p+1} - 1 ) \ge 0 \ge - w \!\left( w^{p-1} - \frac{1}{2}\!\right) . \end{aligned}$$

    So to \(w^{p-1} \ge \frac{1}{2}\) and thus to \(w \in [w_{p-1},1]\). ‘\( ii \Rightarrow i\)’: this statement holds if \(w=1\) or \(n=1\). Now further suppose \(w < 1\) and \(n \ge 3\). The proof is complete if we can show that \(p \in R(p+1)\) and \(p+1 \in R(p)\). Well, this follows by Lemma 2(1, 2) as by the above, (9) holds. \(\square \)

Finally, we are ready for the proof of Theorem 2:

I. ‘\(\supseteq \):’ this is as follows implied by Lemma 5(1).

Ia by part b.

Ib for \(k \ge 1\) by part a; Ib for \(k = 0\) by part c.

Ic for \(k \ge 1\) by parts a and b; Ic for \(k=0\) by parts b and c.

Id for \(k \ge 1\) by parts a and b; Id for \(k=0\) by parts c and d.

Ie by part d.

‘\(\subseteq \)’: suppose \((e_1,e_2) \in E_w^{\star }\). The remark before Lemma 5(1) states that exactly one of the four cases a,b,c,d in Lemma 5(1) holds. The desired results follow. Indeed:

Ia by part b.

Ib for \(k \ge 1\) by part a; Ib for \(k=0\) by part c.

Ic for \(k \ge 1\) by parts a and b; Ic for \(k=0\) by parts b and c.

Id for \(k \ge 1\) by parts a and b; Id for \(k =0\) by parts c and d.

Ie by part d.

II. ‘\(\supseteq \):’ this is as follows implied by Lemma 5(2).

IIa by part c.

IIb by part a.

IIc with \(k \ge 2\): by part b for \(\mathbf {a}_k\), by part c for \(\mathbf {b}^+_k\) and \(\mathbf {b}^+_{k-1}\). IIc with \(k =1\): by part b for \(\mathbf {a}_k\), by part c for \(\mathbf {b}^+_k\) and by part d for \(\mathbf {b}^+_{k-1}\).

IId by part d.

IIe. By Proposition 1

II. ‘\(\subseteq \):’ suppose \((e_1,e_2) \in E_w^{\star }\). The remark before Lemma 5(1) states that exactly one of the four cases a,b,c,d in Lemma 5(2) holds. The desired results follow. Indeed:

IIa by part c.

IIb by parts a and c.

IIc with \(k \ge 2\): by part b for \(\mathbf {a}_k\), by part c for \(\mathbf {b}^+_k\) and \(\mathbf {b}^+_{k-1}\). IIc with \(k =1\): by part b for \(\mathbf {a}_k\), by part c for \(\mathbf {b}^+_k\) and by part d for \(\mathbf {b}^+_{k-1}\).

IId by part d.

IIe by Proposition 1. \(\square \)

6 Concluding remarks

We determined in a somewhat lengthy analysis (since we had to distinguish between many cases) for all values of the parameters n and w the pure Nash equilibrium set of the Hotelling bi-matrix game. This set is non-empty.

In the case \(n=2p+1\) is odd, there exists a symmetric equilibrium only in the case \(w=1\); in this case the symmetric equilibria are (p, p) and \((p+1,p+1)\). In the case \(n=2p\) is even, a symmetric equilibrium exists if and only if \(w \ge 2^{-1/p}\); in this case (p, p) is the unique symmetric equilibrium.

It remains to be seen whether a much simpler proof exists of the non-emptiness of the equilibrium set. We know there are three classes of finite games in strategic form that have a pure Nash equilibrium: potential games, supermodular games, and the recently discovered symmetric games with integrally concave payoffs ([6]). Our results show that the equilibrium set in general has neither a greatest element nor a smallest element. This property suggests that the theory of supermodular games does not apply to our game. Also our results show that there exist equilibria \((e_1,e_2)\) with \(|e_2-e_2| \ge 2\). (For example for \(n=7\) and \(w=1/2\), Theorems 1(IIb) and 2 give \(E_w = \{ (1,4), (2,5), (3,6), (4,1), (5,2), (6,3) \}\).) This means that we cannot rely on the results in [6] for games with integrally concave payoff functions. We do not know whether the Hotelling bi-matrix game is a potential game.

As there are two players and the game is symmetric, equilibrium existence is equivalent to the statement that the correspondence \(R^2\), i.e. the composition \(R \circ R\), has a fixed point. After analyzing many cases (with MAPLE) we conjecture that the deeper reason for \(R^2\) to have a fixed point is: \(R^2\) has an increasing singleton-valued selection. Indeed, if this conjecture is true, then Tarski’s fixed point theorem implies that \(R^2\) has a fixed point.

The corresponding continuous version of the game is not so difficult to handle. Yet, as [5] shows (where the mixed Nash equilibria of the Hotelling tri-matrix game with \(w=1\) are studied), results for the continuous and discrete Hotelling games may be quite incompatible.

The Hotelling bi-matrix game is also well-defined for \(w > 1\). We assumed \(w \le 1\) merely because this was also done in [1]. We think that our analysis can be adapted such that it holds for any value of \(w > 0\).