1 Introduction

Starting with Hotelling (1929), many papers have considered location games where retailers decide where to set up their shop to attract the largest amount of consumers.Footnote 1 Several of these papers focus on the existence of pure equilibria of the game for different number of retailers. For instance, Eaton and Lipsey (1975) provided a detailed analysis of the case where retailers are distributed on an interval or on a circle. The case of the circle was studied also by Salop (1979). Different topologies of the space where consumers are distributed and different distributions have been considered. For instance, Mavronicolas et al. (2008), Feldmann et al. (2009), Pálvölgyi (2011), Heijnen and Soetevent (2014) and Fournier and Scarsini (2014) have considered the case of consumers distributed on a graph.

In this paper, we completely abstract from any topological structure and simply assume that consumers have strict preferences over a finite number of possible store locations. Moreover, the distribution of these preferences is completely arbitrary. In this way, we do not even need to make any explicit hypothesis about the number (finite or infinite) of consumers. Each retailer chooses a possible location for her store to maximize the amount of consumers that she can attract. The aim of the paper is to provide sufficient conditions for the game to have a pure Nash equilibrium. In particular, we will prove that, given a fixed distribution of consumers’ preferences, there exists an integer \(\bar{n}\) such that any game where the number of retailers is larger than \(\bar{n}\) has a pure equilibrium. Moreover, as the number of retailers increases, their distribution over locations tends to match the distribution of consumers’ preferences. This phenomenon was first observed by Osborne and Pitchik (1986) for mixed equilibria in a model where consumers are distributed in the interval \([0,1]\) under some differentiability conditions on the consumers’ distribution. A similar result is present in Laster et al. (1999) and Ottaviani and Sorensen (2006) in the context of professional forecasting.

Our model would apply also to political competition, as studied by Downs (1957) and many others after him. For the sake of clarity, we decided to stick to the retailer/consumer language.

Existence of pure equilibria in non-cooperative games is a topic that has been studied in different contexts. In congestion games, players, in order to achieve their goal, can choose a subset of an available set of facilities. The cost of a facility is increasing in the number of players who use it. Congestion games are potential games; therefore, they have pure Nash equilibria, see, for instance, the seminal papers of Rosenthal (1973) and Monderer and Shapley (1996). Although they bear strong similarities to congestion games, our location games are different: it is true that the utility of using a certain location decreases in the number of players who use it, but the utility depends also on whether the other locations are used rather than not. There are, therefore, externalities. For this reason, location games with few players may fail to have pure equilibria. As we prove in this paper, as the number of players becomes large, a necessary condition for an equilibrium is that all locations be occupied; therefore, location games behave like congestion games and hence have pure equilibria. Nevertheless, even with a large number of players the payoff function of a location game is not the one of a congestion game. The similarity is only in the equilibrium behavior. That is why a proof of the existence of pure equilibria in large location games is needed and it is not possible to resort to the property of a potential function: there is no potential function in these games.

Another family of games with good properties is the class of supermodular games. Conditions for pure equilibria in supermodular games were established in Topkis (1979), see also Milgrom and Roberts (1990), among others. In general, in infinite games existence of equilibria is guaranteed under some topological assumptions on the action space and some continuity assumptions on the payoff function, see, for instance, Glicksberg (1952) and Debreu (1952). The classical Hotelling-type models where retailers can choose any location where consumers live are infinite games with discontinuous payoff functions. Starting with Reny (1999), conditions for equilibria in discontinuous games have been studied, see, for instance, Jackson and Swinkels (2005), McLennan et al. (2011), Balder (2011), Carmona (2011), de Castro (2011), Reny (2011), Barelli and Meneghel (2013) and He and Yannelis (2014a, b, c).

Our results bear also some connections with the literature on large games in the tradition of Schmeidler (1973) and Kalai (2004), among others. In particular, Schmeidler (1973) showed that, in games with a continuum of players, pure equilibria exist under some anonymity conditions on the payoff functions. Kalai (2004) proved a self-purification result for games with a large number of players: for any positive \(\varepsilon \), there exists an integer \(\bar{n}\) such that for every mixed-strategy equilibrium of a game with more than \(\bar{n}\) players, with probability larger than \((1-\varepsilon )\) the realized vector of pure strategies is a Nash equilibrium of the game.

The paper is organized as follows. Section 2 introduces the model and Sect. 3 analyzes its equilibria. All proofs are in the Sect. 4.

2 The model

Retailers A finite set \(N_{n}:=\{1,\dots ,n\}\) of retailers has to decide where to set shop, knowing that consumers choose the closest retailers. Each retailer wants to maximize her market share. Given \(K=\{1,\dots ,k\}\), the action set of each retailer is a finite set \(X_{K}=\{x_{1}, \dots , x_{k}\}\). For \(J \subset K\), we define

$$\begin{aligned} X_{J}:= \{x_{i}:i \in J\}. \end{aligned}$$

Consumers Each consumer has a strict preference over the locations in \(X_{K}\). This preference can be expressed in terms of a permutation \(\pi \) of \(K:=\{1,\dots ,k\}\). If a consumer has a preference \((\pi (1), \pi (2), \dots , \pi (k))\), then she will shop at location \(x_{\pi (1)}\), if there is a retailer located there, otherwise she will shop at \(x_{\pi (2)}\), if there is a retailer located there, and so on. Call \(\fancyscript{P}(K)\) the set of all permutations of \(K\).

We make no assumption about the cardinality of the set of consumers. We call \(\lambda _{\pi } \in \mathbb {R}_{+}\) the mass of consumers whose preference is \(\pi :=(\pi (1), \pi (2), \dots , \pi (k))\). We assume that total mass of consumers is finite and, w.l.o.g.,

$$\begin{aligned} \sum _{\pi \in \fancyscript{P}(K)} \lambda _{\pi } = 1. \end{aligned}$$
(1)

For \(J \subset K\) call \(\pi ^{J}\) the projection of the permutation \(\pi \) on \(J\) and for \(i \in J\)

$$\begin{aligned} \lambda ^{J}_{i} := \sum _{\pi \in \fancyscript{P}(K):\pi ^{J}(1)=i} \lambda _{\pi }. \end{aligned}$$

Hence \(\lambda ^{J}_{i}\) represents the mass of consumers whose first choice is location \(x_{i}\), if the set of locations where they can shop is \(X_{J}\). It is clear that for \(i \in J \subset L \subset K\) we have \(\lambda ^{J}_{i} \ge \lambda ^{L}_{i}\). For the sake of simplicity, we write \(\lambda _{i}\) rather than \(\lambda ^{K}_{i}\).

We assume that

$$\begin{aligned} \lambda _{i} > 0\quad \text {for all }\ i \in K. \end{aligned}$$
(2)

This implies that, no matter where stores locate, none of them will go unpatronized. Given (1), we have

$$\begin{aligned} \sum _{i \in K} \lambda _{i}=1. \end{aligned}$$

The game. We build a game where \(N_{n}:=\{1,\dots ,n\}\) is the set of players. For \(i \in N_{n}\) call \(a_{i} \in X_{K}\) the action of player \(i\). Then, \(\pmb {a}:=(a_{i})_{i\in N_{n}}\) is the profile of actions and \(\pmb {a}_{-i}:=(a_{h})_{h\in N_{n}\setminus \{i\}}\) is the profile of actions of all the players different from \(i\). Hence \(\pmb {a}=(a_{i}, \pmb {a}_{-i})\).

We say that \(\pmb {a} \approx X_{J}\) if for all locations \(x_{j}\in X_{J}\) there exists a player \(i \in N_{n}\) such that \(a_{i} = x_{j}\) and for all players \(i \in N_{n}\) there exists a location \(x_{j}\in X_{J}\) such that \(a_{i} = x_{j}\).

For \(i \in N_{n}\), the payoff of player \(i\) is \(u_{i}: X_{K}^{n} \rightarrow \mathbb {R}\), defined as follows:

$$\begin{aligned} u_{i}(\pmb {a}) = \frac{1}{{\text {card}}\{h:a_{h}=a_{i}\}} \sum _{J\subset K} \lambda ^{J}_{i}1\!\!1(\pmb {a}\approx X_{J}). \end{aligned}$$
(3)

Expression (3) represents the following idea. Retailer \(i\)’s payoff is the measure of the consumers who prefer her location to any other location chosen by any other retailer, divided by the number of retailers that choose the same action as \(i\). Some locations may not be chosen by any player, this is why, for every \(J \subset K\), we have to consider the permutation \(\pi ^{J}\) with \(\pmb {a}\approx X_{J}\) rather than the permutation \(\pi \).

Consider a game where the distribution of consumers’s preferences is \(\pmb {\Lambda }:=(\lambda _{\pi })_{\pi \in \fancyscript{P}(K)}\), the set of players is \(N_{n}\), the set of actions for each player is \(X_{K}\) and the payoff of player \(i\) is given by (3). Call this game \(\mathcal {G}_{n}=\langle \pmb {\Lambda }, N_{n}, X_{K},(u_{i})\rangle \). Since the set of actions coincides with the set of locations, we will use the two terms interchangeably.

Remark 1

A particular case of the above class of games \(\mathcal {G}_{n}\) is given by location games where consumers are distributed on a metric compact measurable space \(S \subset \mathbb {R}^{d}\) and retailers can choose one location in a finite set \(X_{K} \subset S\), knowing that consumer will shop at the closest store. If the distribution of the consumers is absolutely continuous with respect to the Lebesgue measure on \(\mathbb {R}^{d}\), then the set of consumers who are indifferent between two or more retailers has measure zero, so preferences are almost surely strict.

3 Equilibria

In the rest of this section, unless otherwise stated, we consider a sequence \(\{\mathcal {G}_{n}\}\) of games, all of which have the same parameters \(\pmb {\Lambda }, X_{K}\). More precisely, our focus is on the sequence of games when the number of retailers \(n\) grows.

We prove that when the number of retailers is large enough, (1) the game admits a pure strategy equilibrium and (2) the distribution of retailers in equilibrium approaches the distribution of consumers.

As the next example shows, when the number of players is small, equilibria may even fail to exist.

Example 2

(A game without pure equilibria) Consider a game \(\mathcal {G}_{n}\) with \(n=2\) and

$$\begin{aligned} \lambda _{123}&= \lambda _{231} = \lambda _{312} = 0, \\ \lambda _{132}&= \lambda _{321} = \lambda _{213} = \frac{1}{3}, \end{aligned}$$

that is no consumer has preferences \(123\), \(231\), or \(312\) and the remaining preferences are equally shared by the population of consumers. Then, the payoff matrix of this game is

and, therefore, no pure equilibrium exists.

The next example shows that a game \(\mathcal {G}_{n}\) can have weakly dominated actions.

Example 3

(A game with weakly dominated actions) Consider a game \(\mathcal {G}_{n}\) with \(n=2\), \(K=\{1,2,3\}\) and

$$\begin{aligned} \lambda _{123}&= \lambda _{321} = 0.475, \\ \lambda _{132}&= \lambda _{312} = 0, \\ \lambda _{213}&= \lambda _{231} = 0.025. \end{aligned}$$

Since

$$\begin{aligned} \lambda ^{12}_{1}&= 0.475,&\lambda ^{12}_{2}&= 0.525,&\\ \lambda ^{13}_{1}&= 0.5,&\lambda ^{13}_{3}&= 0.5,&\\ \lambda ^{23}_{2}&= 0.525,&\lambda ^{23}_{3}&= 0.475,&\\ \lambda ^{123}_{1}&= 0.475,&\lambda ^{123}_{2}&= 0.05,&\lambda ^{123}_{3} = 0.475. \end{aligned}$$

we see that both \(x_{1}\) and \(x_{3}\) are weakly dominated by \(x_{2}\).

The existence of weakly dominated strategies becomes impossible when the number of players is large enough.

Proposition 4

Consider a sequence of games \(\{\mathcal {G}_{n}\}_{n\in \mathbb {N}}\). There exists \(\bar{n}\) such that for all \(n \ge \bar{n}\) no location in \(X_{K}\) is weakly dominated.

When the number of players is large, pure equilibria exist and in equilibrium the share of players in location \(x_{i}\) is approximately proportional to \(\lambda _{i}\). The following theorem makes this idea precise. For \(j \in K\) call \(n_{j}(\pmb {a})\) the number of players who choose \(x_{j}\) under the strategy \(\pmb {a}\).

Theorem 5

Consider a sequence of games \(\{\mathcal {G}_{n}\}_{n\in \mathbb {N}}\). There exists \(\bar{n}\) such that for all \(n \ge \bar{n}\) the game \(\mathcal {G}_{n}\) admits a pure equilibrium \(\pmb {a}^{*}\). Moreover, for all \(n\ge \bar{n}\), any pure equilibrium is such that

$$\begin{aligned} \frac{n_{j}(\pmb {a}^{*})}{n_{\ell }(\pmb {a}^{*})+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}(\pmb {a}^{*})+1}{n_{\ell }(\pmb {a}^{*})}. \end{aligned}$$
(4)

Corollary 6

Let

$$\begin{aligned} \lambda ^{*}:=\min \{\lambda _{1}, \dots , \lambda _{k}\}\quad \text {and}\quad m:=\min \left\{ n \in \mathbb {N}_{+} : \frac{1}{n} \le \lambda ^{*}\right\} . \end{aligned}$$

Let \(m_{1}, \dots , m_{k} \in \mathbb {N}_{+}\) be such that

$$\begin{aligned} \frac{m_{i}}{m} \le \lambda _{i} < \frac{m_{i}+1}{m} \qquad \text {for all }\ i \in \{1, \dots , k\}. \end{aligned}$$

Then, \(\bar{n}\) in Theorem 5 can be chosen as:

$$\begin{aligned} \bar{n} = \sum _{i=1}^{k} m_{i}. \end{aligned}$$

4 Proofs

Proof

(Proof of Proposition 4) Pick any pair of locations \(x_{j}, x_{h} \in X_{K}\) and consider the strategy profile \(a_{1}=x_{j}\) and \(a_{i}=x_{h}\) for \(i\ne 1\). Then, given assumption (2), for \(i\ne 1\) and \(n\) sufficiently large, we have

$$\begin{aligned} u_{1}(\pmb {a}) = \lambda _{j} \ge \frac{1}{n-1} \lambda _{h} = u_{i}(\pmb {a}), \end{aligned}$$

which shows that \(x_{j}\) is not weakly dominated. Given that the pair \(x_{j}, x_{h}\) was arbitrarily chosen, we have the result. \(\square \)

Lemma 7

Consider a sequence of games \(\{\mathcal {G}_{n}\}_{n\in \mathbb {N}}\). There exists \(\bar{n}\) such that for all \(n \ge \bar{n}\), if \(\pmb {a}^{*}\) is an equilibrium of \(\mathcal {G}_{n}\), then

$$\begin{aligned} n_{j}(\pmb {a}^{*}) > 0\quad { for} \, { all}\, x_{j}\in X_{K}. \end{aligned}$$

Proof

Assume by contradiction that for all \(n \in \mathbb {N}\), if the game \(\mathcal {G}_{n}\) has a pure equilibrium \(\pmb {a}^{*}\), then there exists a location \(x_{j}\in X_{K}\) such that \(n_{j}(\pmb {a}^{*})=0\). We know that

$$\begin{aligned} \sum _{i\in N_{n}}u_{i}(\pmb {a}^{*})=\sum _{\pi \in \fancyscript{P}(K)} \lambda _{\pi } = 1. \end{aligned}$$

Therefore, there exists \(i\in N_{n}\) such that

$$\begin{aligned} u_{i}(\pmb {a}^{*})\le \frac{1}{n}. \end{aligned}$$

If this player deviated to \(a_{i}=x_{j}\), she would achieve the payoff

$$\begin{aligned} u_{i}(a_{i}, \pmb {a}^{*}_{-i}) \ge \lambda _{j} \ge \frac{1}{n}, \end{aligned}$$

for \(n\) large enough. This contradicts the assumption that \(\pmb {a}^{*}\) is a Nash equilibrium. \(\square \)

Lemma 8

A strategy profile \(\pmb {a}^{*}\) is an equilibrium of the game \(\mathcal {G}_{n}\) such that \(n_{j}(\pmb {a}^{*})>0\) for all \(j\in K\) if and only if, for every \(j,\ell \in K\), (4) holds.

Proof

Let \(\pmb {a}^{*}\) be an equilibrium of \(\mathcal {G}_{n}\) and let \(a_{i}^{*} = x_{\ell }\). Assume, by contradiction, that

$$\begin{aligned} \frac{\lambda _{j}}{n_{j}(\pmb {a}^{*})+1} > \frac{\lambda _{\ell }}{n_{\ell }(\pmb {a}^{*})}. \end{aligned}$$

Then, player \(i\) could profitably deviate from \(x_{\ell }\) to \(x_{j}\). Therefore, for every \(j,\ell \in K\) we have

$$\begin{aligned} \frac{\lambda _{j}}{n_{j}(\pmb {a}^{*})+1} \le \frac{\lambda _{\ell }}{n_{\ell }(\pmb {a}^{*})}\quad \text {and}\quad \frac{\lambda _{\ell }}{n_{\ell }(\pmb {a}^{*})+1} \le \frac{\lambda {j}}{n_{j}(\pmb {a}^{*})} \end{aligned}$$
(5)

and, applying Lemma 7, (4) follows.

To prove the converse implication, assume that (4) holds. Equivalently, (5) holds for every \(j,\ell \in K\). As a consequence, no player can profitably deviate from \(x_{j}\) to \(x_{\ell }\) or vice versa, for every \(j,\ell \in K\). Hence \(\pmb {a}^{*}\) is an equilibrium. \(\square \)

Fix \(k \in \mathbb {N}_{+}\). Call \(\fancyscript{I}_{k}\) the interior of the \((k-1)\)-dimensional simplex, i.e., for \(\pmb {\lambda }:=(\lambda _{1}, \dots , \lambda _{k})\),

$$\begin{aligned} \mathcal {I}_{k} = \left\{ \pmb {\lambda }\in \mathbb {R}^{k} : \lambda _{\ell } > 0 \quad \text {for all}\ \ell \in \{1, \dots , k\} \quad \text {and}\quad \sum _{j=1}^{k} \lambda _{j} = 1 \right\} . \end{aligned}$$

Define for \(\pmb {n}:=(n_{1}, \dots , n_{k})\)

$$\begin{aligned} \Sigma _{k}(n) := \left\{ \pmb {n} \in \mathbb {N}_{+}^{k} : \sum _{i=1}^{k}n_{i}=n\right\} \!. \end{aligned}$$

For \(j \in \{1, \dots , k\}\) call \(\pmb {e}_{j}\) the \(j\)-th vector of the canonical basis in \(\mathbb {R}^{k}\).

Theorem 9

Let \(\pmb {\lambda } \in \fancyscript{I}_{k}\). Then, there exists \(\bar{n} \in \mathbb {N}_{+}\) such that if \(n \ge \bar{n}\), then there exists \(\pmb {n} \in \Sigma _{k}(n)\) such that

$$\begin{aligned} \frac{n_{j}}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}+1}{n_{\ell }} \quad \text {for all }\ j,\ell \in \{1, \dots , k\}. \end{aligned}$$
(6)

The proof of Theorem 9 requires the following lemmata.

Lemma 10

Assume that (6) holds. If

$$\begin{aligned} \frac{n_{j}+1}{n_{i}+1} \le \frac{\lambda _{j}}{\lambda _{i}} \le \frac{n_{j}+2}{n_{i}} \quad \mathrm{and}\quad \frac{n_{i}+1}{n_{\ell }+1} \le \frac{\lambda _{i}}{\lambda _{\ell }} \le \frac{n_{i}+2}{n_{\ell }}, \end{aligned}$$
(7)

then

$$\begin{aligned} \frac{n_{j}+1}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}+2}{n_{\ell }}. \end{aligned}$$

Proof

Combining the inequalities in (7), we get

$$\begin{aligned} \frac{n_{j}+1}{n_{i}+1} \frac{n_{i}+1}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{i}} \frac{\lambda _{i}}{\lambda _{\ell }} \le \frac{n_{j}+2}{n_{i}} \frac{n_{i}+2}{n_{\ell }}. \end{aligned}$$
(8)

The right inequality in (6) and the left inequality in (8) imply

$$\begin{aligned} \frac{n_{j}+1}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}+1}{n_{\ell }} \le \frac{n_{j}+2}{n_{\ell }}. \end{aligned}$$

\(\square \)

Lemma 11

Assume that (6) holds. Then, at least one of the double inequalities (9) and (10) below is true:

$$\begin{aligned}&\frac{n_{j}+1}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}+2}{n_{\ell }}, \end{aligned}$$
(9)
$$\begin{aligned}&\frac{n_{\ell }+1}{n_{j}+1} \le \frac{\lambda _{\ell }}{\lambda _{j}} \le \frac{n_{\ell }+2}{n_{j}}. \end{aligned}$$
(10)

Proof

From (6), we get

$$\begin{aligned} \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n_{j}+1}{n_{\ell }} \le \frac{n_{j}+2}{n_{\ell }} \quad \text {and}\quad \frac{\lambda _{\ell }}{\lambda _{j}} \le \frac{n_{\ell }+1}{n_{j}} \le \frac{n_{\ell }+2}{n_{j}}. \end{aligned}$$

Since, either

$$\begin{aligned} \frac{n_{j}+1}{n_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \quad \text {or}\quad \frac{n_{\ell }+1}{n_{j}+1} \le \frac{\lambda _{\ell }}{\lambda _{j}}, \end{aligned}$$

or both inequalities hold, we have that at least one of (9) and (10) holds. \(\square \)

Proof

(Proof of Theorem 9) We will prove the result by induction over \(n\). First Lemma 12 shows that there exists a certain value \(\bar{n}\) and a positive integer vector \(\pmb {\bar{n}} \in \Sigma _{k}(\bar{n})\) such that (6) holds. Then, Lemma 13 shows that there exists a vector \(\pmb {n}^{*} \in \Sigma _{k}(\bar{n}+1)\) for which (6) still holds.

Lemma 12

There exists a certain value \(\bar{n}\) and a positive integer vector \(\pmb {\bar{n}} \in \Sigma _{k}(\bar{n})\) such that

$$\begin{aligned} \frac{\bar{n}_{j}}{\bar{n}_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{\bar{n}_{j}+1}{\bar{n}_{\ell }} \quad { for} \,{ all}\ j,\ell \in \{1, \dots , k\}. \end{aligned}$$
(11)

Proof

For every \(\pmb {\lambda } \in \fancyscript{I}_{k}\), since \(\lambda _{1}, \dots , \lambda _{k}\) are all positive, there exist positive integers \(m_{1}, \dots , m_{k}, m\) such that for all \(i \in \{1, \dots , k\}\)

$$\begin{aligned} \frac{m_{i}}{m} \le \lambda _{i} \le \frac{m_{i}+1}{m}. \end{aligned}$$
(12)

Therefore, by combining (12) for \(i=j\) and \(i=\ell \), we get

$$\begin{aligned} \frac{m_{j}}{m_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{m_{j}+1}{m_{\ell }}. \end{aligned}$$

If we take \(\bar{n}_{j}=m_{j}\) for all \(j \in \{1, \dots , k\}\) and

$$\begin{aligned} \bar{n} = \sum _{j=1}^{k} m_{j}, \end{aligned}$$

then for all \(j,\ell \in \{1, \dots , k\}\)

$$\begin{aligned} \frac{\bar{n}_{j}}{\bar{n}_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{\bar{n}_{j}+1}{\bar{n}_{\ell }}. \end{aligned}$$

\(\square \)

Lemma 13

If \(\pmb {n} \in \Sigma _{k}(n)\) satisfies (6), then there exists \(\pmb {n}^{*} \in \Sigma _{k}(n+1)\) such that

$$\begin{aligned} \pmb {n}^{*} = \pmb {n} + \pmb {e}_{i}\quad { for}\,{ some}\ i \in \{1, \dots , k\} \end{aligned}$$
(13)

and

$$\begin{aligned} \frac{n^{*}_{j}}{n^{*}_{\ell }+1} \le \frac{\lambda _{j}}{\lambda _{\ell }} \le \frac{n^{*}_{j}+1}{n^{*}_{\ell }}\quad { for}\, { all }\ j,\ell \in \{1, \dots , k\}. \end{aligned}$$
(14)

Proof

Start with index \(1\), and, for every \(j=2, \dots , k\), check whether

$$\begin{aligned} \frac{n_{1}+1}{n_{j}+1} \le \frac{\lambda _{1}}{\lambda _{j}} \le \frac{n_{1}+2}{n_{j}}. \end{aligned}$$
(15)

Given that \(n^{*}_{j}=n_{j}\) for \(j\ne i\), we have that, if (15) holds for every \(j=2, \dots , k\), then (14) holds when \(i=1\) in (13). If (15) does not hold for every \(j=2, \dots , k\), then consider the smallest \(j\) for which (15) is not true. Call it \(j^{*}\). By Lemma 11, we have

$$\begin{aligned} \frac{n_{j^{*}}+1}{n_{1}+1} \le \frac{\lambda _{j^{*}}}{\lambda _{1}} \le \frac{n_{j^{*}}+2}{n_{1}}. \end{aligned}$$
(16)

We know that (15) holds for all \(j=2, \dots , j^{*}-1\). Therefore, by Lemma 10, (16) in turn implies that for all \(\ell \in \{1, \dots , j^{*}-1\}\)

$$\begin{aligned} \frac{n_{j^{*}}+1}{n_{\ell }+1} \le \frac{\lambda _{j^{*}}}{\lambda _{\ell }} \le \frac{n_{j^{*}}+2}{n_{\ell }}. \end{aligned}$$
(17)

Using the same argument as before, we se that, if \(j^{*}=k\), then (14) holds when \(i=k\) in (13). If \(j^{*}\ne k\), then check whether (17) holds for all \(\ell \in \{j^{*}+1, \dots , k\}\). If it does, then (14) holds when \(i=j^{*}\) in (13). If not, then consider the smallest \(j > j^{*}\) for which (17) is not true. Call it \(j^{**}\). Repeat the steps done for \(j^{*}\), that is, first notice that, by Lemma 11, we have

$$\begin{aligned} \frac{n_{j^{**}}+1}{n_{j^{*}}+1} \le \frac{\lambda _{j^{**}}}{\lambda _{j^{*}}} \le \frac{n_{j^{**}}+2}{n_{j^{*}}}. \end{aligned}$$
(18)

We know that for all \(\ell \in \{1, \dots , j^{*}-1\} \cup \{j^{*}+1, \dots , j^{**}-1\}\)

$$\begin{aligned} \frac{n_{j^{*}}+1}{n_{\ell }+1} \le \frac{\lambda _{j^{*}}}{\lambda _{\ell }} \le \frac{n_{j^{*}}+2}{n_{\ell }}. \end{aligned}$$

Therefore, by Lemma 10, (18) implies that for all \(\ell \in \{1, \dots , j^{**}-1\}\)

$$\begin{aligned} \frac{n_{j^{**}}+1}{n_{\ell }+1} \le \frac{\lambda _{j^{**}}}{\lambda _{\ell }} \le \frac{n_{j^{**}}+2}{n_{\ell }}. \end{aligned}$$
(19)

As before, we se that, if it were true that \(j^{**}=k\), then (14) would hold when \(i=k\) in (13), but we know from the previous step that this cannot be the case. Since \(j^{**} < k\), we need to check whether (19) holds true for all \(\ell \in \{j^{**}+1, \dots , k\}\). If it does, then (14) holds when \(i=j^{**}\) in (13). If not, then consider the smallest \(j > j^{**}\) for which (19) is not true. Call it \(j^{***}\). Repeat the argument. Since

$$\begin{aligned} 1 < j^{*} < j^{**} < j^{***} \dots < k, \end{aligned}$$

the procedure ends in finite time. \(\square \)

This concludes the induction argument and, therefore, proves the theorem. \(\square \)

Proof

(Proof of Theorem 5) Lemma 7 shows that for \(n\) large enough in equilibrium all locations are occupied. Lemma 8 shows that a strategy profile \(\pmb {a}^{*}\) is an equilibrium where all locations are occupied if and only if (4) holds. Finally, Theorem 9 shows that indeed the configuration of (4) can be achieved for all \(n\) large enough. Therefore, combining these three results, the theorem is proved. \(\square \)