Abstract
We consider a Hotelling location game where retailers can choose one of a finite number of locations. Consumers have strict preferences over the possible available store locations and retailers aim to attract the maximum number of consumers. We prove that a pure strategy equilibrium exists if the number of retailers is large enough. Moreover, as the number of retailers grows large, in equilibrium the distribution of retailers over the locations converges to the distribution of consumers’ preferences.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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.,
For \(J \subset K\) call \(\pi ^{J}\) the projection of the permutation \(\pi \) on \(J\) and for \(i \in J\)
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
This implies that, no matter where stores locate, none of them will go unpatronized. Given (1), we have
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:
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
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
Since
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
Corollary 6
Let
Let \(m_{1}, \dots , m_{k} \in \mathbb {N}_{+}\) be such that
Then, \(\bar{n}\) in Theorem 5 can be chosen as:
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
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
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
Therefore, there exists \(i\in N_{n}\) such that
If this player deviated to \(a_{i}=x_{j}\), she would achieve the payoff
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
Then, player \(i\) could profitably deviate from \(x_{\ell }\) to \(x_{j}\). Therefore, for every \(j,\ell \in K\) we have
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})\),
Define for \(\pmb {n}:=(n_{1}, \dots , n_{k})\)
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
The proof of Theorem 9 requires the following lemmata.
Lemma 10
Assume that (6) holds. If
then
Proof
Combining the inequalities in (7), we get
The right inequality in (6) and the left inequality in (8) imply
\(\square \)
Lemma 11
Assume that (6) holds. Then, at least one of the double inequalities (9) and (10) below is true:
Proof
From (6), we get
Since, either
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
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\}\)
Therefore, by combining (12) for \(i=j\) and \(i=\ell \), we get
If we take \(\bar{n}_{j}=m_{j}\) for all \(j \in \{1, \dots , k\}\) and
then for all \(j,\ell \in \{1, \dots , k\}\)
\(\square \)
Lemma 13
If \(\pmb {n} \in \Sigma _{k}(n)\) satisfies (6), then there exists \(\pmb {n}^{*} \in \Sigma _{k}(n+1)\) such that
and
Proof
Start with index \(1\), and, for every \(j=2, \dots , k\), check whether
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
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\}\)
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
We know that for all \(\ell \in \{1, \dots , j^{*}-1\} \cup \{j^{*}+1, \dots , j^{**}-1\}\)
Therefore, by Lemma 10, (18) implies that for all \(\ell \in \{1, \dots , j^{**}-1\}\)
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
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 \)
Notes
We refer to Fournier and Scarsini (2014) for a recent extensive bibliography on the topic.
References
Balder, E.J.: An equilibrium closure result for discontinuous games. Econ. Theory 48(1), 47–65 (2011). doi:10.1007/s00199-010-0574-6
Barelli, P., Meneghel, I.: A note on the equilibrium existence problem in discontinuous games. Econometrica 81(2), 813–824 (2013). doi:10.3982/ECTA9125
Carmona, G.: Understanding some recent existence results for discontinuous games. Econ. Theory 48(1), 31–45 (2011). doi:10.1007/s00199-010-0532-3
de Castro, L.I.: Equilibrium existence and approximation of regular discontinuous games. Econ. Theory 48(1), 67–85 (2011). doi:10.1007/s00199-010-0580-8
Debreu, G.: A social equilibrium existence theorem. Proc. Natl. Acad. Sci. USA 38, 886–893 (1952)
Downs, A.: An Economic Theory of Democracy. Harper and Row, New York (1957)
Eaton, B.C., Lipsey, R.G.: The principle of minimum differentiation reconsidered: some new developments in the theory of spatial competition. Rev. Econ. Stud. 42(1), 27–49 (1975)
Feldmann, R., Mavronicolas, M., Monien, B.: Nash equilibria for Voronoi games on transitive graphs. In: Leonardi, S. (ed.) Internet and Network Economics, Lecture Notes in Computer Science, vol. 5929, pp. 280–291. Springer, Berlin, Heidelberg (2009). doi:10.1007/978-3-642-10841-9_26
Fournier, G., Scarsini, M.: Hotelling games on networks: efficiency of equilibria (2014). doi:10.2139/ssrn.2423345
Glicksberg, I.L.: A further generalization of the Kakutani fixed theorem, with application to Nash equilibrium points. Proc. Am. Math. Soc. 3, 170–174 (1952)
He, W., Yannelis, N.C.: Discontinuous games with asymmetric information: an extension of Reny’s existence theorem. Mimeo (2014a)
He, W., Yannelis, N.C.: Equilibria with discontinuous preferences. Mimeo (2014b)
He, W., Yannelis, N.C.: Existence of walrasian equilibria with discontinuous, non-ordered, interdependent and price-dependent preferences. Mimeo (2014c)
Heijnen, P., Soetevent, A.R.: Price competition on graphs. Technical Report TI 2014–131/VII, Tinbergen Institute (2014)
Hotelling, H.: Stability in competition. Econ. J. 39(153), 41–57 (1929)
Jackson, M.O., Swinkels, J.M.: Existence of equilibrium in single and double private value auctions. Econometrica 73(1), 93–139 (2005). doi:10.1111/j.1468-0262.2005.00566.x
Kalai, E.: Large robust games. Econometrica 72(6), 1631–1665 (2004). doi:10.1111/j.1468-0262.2004.00549.x
Laster, D., Bennet, P., Geoum, I.: Rational bias in macroeconomic forecasts. Q. J. Econ. 45(2), 145–186 (1999). doi:10.1007/s00355-010-0495-0
Mavronicolas, M., Monien, B., Papadopoulou, V.G., Schoppmann, F.: Voronoi games on cycle graphs. In: Mathematical Foundations of Computer Science 2008, Lecture Notes in Computer Science, vol. 5162, pp. 503–514. Springer, Berlin (2008). doi:10.1007/978-3-540-85238-4_41
McLennan, A., Monteiro, P.K., Tourky, R.: Games with discontinuous payoffs: a strengthening of Reny’s existence theorem. Econometrica 79(5), 1643–1664 (2011). doi:10.3982/ECTA8949
Milgrom, P., Roberts, J.: Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica 58(6), 1255–1277 (1990). doi:10.2307/2938316
Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996). doi:10.1006/game.1996.0044
Osborne, M.J., Pitchik, C.: The nature of equilibrium in a location model. Int. Econ. Rev. 27(1), 223–237 (1986). doi:10.2307/2526617
Ottaviani, M., Sorensen, P.N.: The strategy of professional forecasting. J. Fin. Econ. 81(2), 441–466 (2006). doi:10.1007/s00355-010-0495-0
Pálvölgyi, D.: Hotelling on graphs. Mimeo (2011)
Reny, P.J.: On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 67(5), 1029–1056 (1999). doi:10.1111/1468-0262.00069
Reny, P.J.: Strategic approximations of discontinuous games. Econ. Theory 48(1), 17–29 (2011). doi:10.1007/s00199-010-0518-1
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973)
Salop, S.C.: Monopolistic competition with outside goods. Bell J. Econ. 10(1), 141–156 (1979)
Schmeidler, D.: Equilibrium points of nonatomic games. J. Stat. Phys. 7(4), 295–300 (1973). doi:10.1007/BF01014905
Topkis, D.: Equilibrium points in nonzero-sum \(n\)-person submodular games. SIAM J. Control Optim. 17(6), 773–787 (1979). doi:10.1137/0317054
Acknowledgments
The authors thank Clémence Christin, Fabian Gouret, and Giacomo Nannicini for their useful remarks and suggestions. The work of Matías Núñez is supported by the center of excellence MME-DII (ANR-11-LBX-0023-01). The work of Marco Scarsini is partially supported by PRIN 20103S5RN3 and MOE2013-T2-1-158. This author is a member of GNAMPA-INdAM.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Núñez, M., Scarsini, M. Competing over a finite number of locations. Econ Theory Bull 4, 125–136 (2016). https://doi.org/10.1007/s40505-015-0068-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40505-015-0068-6