WPS7701 Policy Research Working Paper 7701 Nash on a Rotary Two Theorems with Implications for Electoral Politics Kaushik Basu Tapan Mitra Development Economics Vice Presidency Office of the Chief Economist June 2016 Policy Research Working Paper 7701 Abstract The paper provides a complete characterization of Nash shown that if the sum of all players’ payoffs is 1, the Nash equilibria for games in which n candidates choose a strat- equilibrium payoff of each player in an arbitrary Nash egy in the form of a platform, each from a circle of feasible equilibrium must be restricted to the interval [1/2(n − 1), platforms, with the aim of maximizing the stretch of the 2/(n + 1)]. This implies that in an election with four can- circle from where the candidate’s platform will receive didates, a candidate who is attracting less than one-sixth support from the voters. Using this characterization, it is of the voters can do better by changing his or her strategy. This paper is a product of the Office of the Chief Economist, Development Economics Vice Presidency. It is part of a larger effort by the World Bank to provide open access to its research and make a contribution to development policy discussions around the world. Policy Research Working Papers are also posted on the Web at http://econ.worldbank.org. The authors may be contacted at kb40@cornell.edu and tm19@cornell.edu. The Policy Research Working Paper Series disseminates the findings of work in progress to encourage the exchange of ideas about development issues. An objective of the series is to get the findings out quickly, even if the presentations are less than fully polished. The papers carry the names of the authors and should be cited accordingly. The findings, interpretations, and conclusions expressed in this paper are entirely those of the authors. They do not necessarily represent the views of the International Bank for Reconstruction and Development/World Bank and its affiliated organizations, or those of the Executive Directors of the World Bank or the governments they represent. Produced by the Research Support Team Nash on a Rotary: Two Theorems with Implications for Electoral Politics∗ Kaushik Basu†and Tapan Mitra‡ Journal of Economic Literature Classification numbers: C72, D21, L10. Key words : Electoral Politics, Circle, Nash Equilibrium, Equilibrium Payoffs ∗ We would like to express our indebtedness to Tito Cordella, Avinash Dixit, Anderson Ospino, and Arunava Sen for comments on an earlier version of this paper. † The World Bank, 1818 H Street, NW, Washington, DC 20433 and Department of Economics, Cornell University, Ithaca, NY 14853; E Mail: kb40@cornell.edu ‡ Department of Economics, Cornell University, Ithaca, NY 14853; E-Mail: tm19@cornell.edu 1 Introduction Starting with Harold Hotelling’s (1929) classic paper, the economics of location, for instance, where and how firms position themselves on a line or on a surface, or the ideological space which political parties try to capture, has become an important tool for analyzing product quality differentiation and antitrust law, retail marketing and the theory of vendor positioning and, most prominently, political economy and electoral politics. In the area of political economy, it has led to the celebrated median voter theorem of Duncan Black (1948) for majority decisions, and of Anthony Downs (1957) for a representative democracy, which enabled us to take on some of the big questions of electoral democracy and development [see, for instance, Stokes (1963); Osborne (1995); Congleton (2002); Acemoglu and Robinson (2005)]. The present paper is an exercise in the pure theory of location choice over a circle or rotary. Given the wide use of location analysis in economics and political science, it is hoped the paper will provide foundations for different kinds of practical studies on electoral democracy or retail trading. Each of these entail further complications. In the case of retail stores choosing their location, the analysis is complicated by the fact that they can, typically, choose the price as well. In electoral politics, personal attributes (for example, the appearance) of the candidate may matter as well and not just the ideological platform the candidate offers. However, the theorems reported in this paper should be of value for all such models. For the most part, for the purpose of motivation, we refer to the problem of electoral democracy. The importance of the pivotal voter was recognized as early as 1785 by Condorcet. However, following the influential work of Hotelling, the bulk of the analysis got focused on voters spread over a line. At one level, our paper is a reminder that there can be other formations among voters and these can lead to related but distinct results. In our set up, for instance, it is not the case that candidates invariably converge on the same electoral platform but, instead, we get the result that no matter how many candidates contest an election, there will never be more than two candidates announcing the same platform.1 As Stokes (1963, p. 368) noted over a half a century ago, “The use of spatial ideas to interpret party competition is a universal phenomenon of modern politics. Such ideas are the common coin of political journalists. . . ” Congleton (2002) points out in his survey of the median voter theorem, “Most analytical work in public choice is based upon relatively simple models of majority decision making. These models are widely used even though the researchers know that real political settings are more complex than the models seem to imply. The . . . simple models provide us with engines of analysis that allow a variety of hypotheses about more complex phenomena to be developed, many of which would be impossible (or uninteresting) without the frame of reference provided by simple models.” It is in this spirit that we venture into investigating electoral democracy in this paper. To understand the idea of using location analysis to investigate electoral democracy, suppose voters are interested in two aspects of candidates running for office: how anti-establishment they are, and their economic ideology, for instance, their position on economic conservatism. Clearly, each voter’s ideal can be represented as a point in a two-dimensional space. Suppose all voters ideals lie on a circle, of the kind shown in Figure 1, and suppose each candidate has to announce his or her agenda which is basically a point on the circle. Thus we can think of candidates S and T announcing their respective agenda, as points S and T on the circle as shown. From the vertical perspective, S and T look identical but they are far apart in terms of economic ideology, measured on the horizontal axis. (Any resemblance of S and T to Sanders and Trump is entirely spurious.) If we assume that voters opt for the candidate 1 Similar issues of cluster and spread arise in the literature on spatial location and agglomeration (Fujita and Thisse, 1996; Pal, 1998; Matsushima, 2001). 2 closest to his or her ideal, the closeness being measured in terms of distance along the circle, then we have a classic location-choice game. 2 Figure 1: Two Dimensional Attributes The specific problem that we want to address in this paper is the following. If there are n candidates in an election, how will they position themselves on the circle in equilibrium? And, once politicians have taken up positions, is there an easy way to check if this is an equilibrium? The entire exercise in this paper is done by defining equilibrium in the sense of Nash. What the paper shows is that there is a surprisingly easy answer to the question just posed (see Theorem 1). Hotelling’s classic location game (for two vendors with exogenously fixed prices) has a unique Nash equilibrium. However, for many non-cooperative games, there is a multiplicity of Nash equilibria, and this is seen as a principal drawback of the equilibrium concept, as its predictive power can be limited as a result. In our setting too, there can be many (in fact, a continuum of) Nash equilibria. However, instead of focusing on equilibrium outcomes, if we shift our focus to equilibrium payoffs, a rather general result on the distribution of payoffs in Nash equilibria emerges in this model. We find that the entire set of Nash equilibria is subject to rather stringent bounds on the equilibrium payoffs. Specifically, if the sum of all players’ payoffs is equal to 1, the Nash equilibrium payoff of each player must lie in the interval: ∙ ¸ 1 2 Π= , 2(n − 1) n + 1 for an arbitrary number n of players, and for an arbitrary Nash equilibrium (see Theorem 2). As an implication, in a four-way race, no candidate can get less than one-sixth of the vote in a Nash 2 Alternatively, we could think of the circle as a rotary along which people in a town live. The only way to travel in this town is along the rotary (in any direction). Two retail vendors, selling goods which have exogenously fixed prices, have to set up shops at points on the rotary. If we make the reasonable assumption that customers will go to the nearest store, and each vendor is interested in maximizing the number of customers she has, then again we have a classic game theory problem. Similar arguments apply to brand proliferation. [See d’Aspremont, Gabszewicz and Thisse(1979), Schmalensee(1978), Salop(1979), Basu(1993), Gabszewicz, Thisse, Fujita and Schweitzer(1986), and Brander and Spencer (2015)]. 3 equilibrium. This makes one-sixth a useful benchmark to decide whether to change one’s strategy in a four-way race. 2 The Model 2.1 Preliminaries We consider a democratic election scenario in the following way. There are a number (say n) of political candidates. Each candidate has a political platform. When each candidate has a distinct platform, candidates can be identified by their political platforms, so that these words can be used interchangeably. Clearly, this is an abstraction, since there can be more to a candidate than her political platform, even from the point of view of an election. Further, the official platform can often be different from the actual platform, or the platform as perceived by the voters. Platforms are typically multi-dimensional (as we have illustrated in Section 1), although in prevalent political discussions, one often discusses platforms in one (major) dimension (or in one dimension at a time), since this simplifies the argument one is trying to make. Actually, the distortion produced in such analysis is substantial, and this has long been recognized in the political science literature that has followed since the uni-dimensional median voter theorem. 3 We might describe a platform by a list of issues ; when speaking of candidates, one might use the term attributes instead. Thus, for example, one might specify a platform by a list of seven major issues, by indicating a candidate’s stand on those seven issues. Unlike in the economics of location, where there would be fairly clear-cut numerical measures to identify locations of vendors, and prices charged at those locations, the problem of quantitative representation of political issues can be a substantial one. On some issues (such as, what should be the magnitude of the capital gains tax), there might be clear-cut numerical measures to summarize a candidate’s stand on the issue. But, on others (such as, the extent of gun control), there might not be such summary measures. However, even in such cases, it is common to use not only ordinal measures (preference for more gun-control to less), but also measures which would be interpreted as cardinal (strongly opposed to gun control). While being aware of the abstraction involved, we choose to represent a platform by a point in m dimensional real space, if there are m clearly defined issues. 4 Not all points in m dimensional space may be considered to be platforms. It is more reasonable to suppose that there is a feasible set of platforms, F (a subset of Rm ), which is well understood by the candidates as well as the electorate. 5 Because we need to understand simpler structures first, in order to investigate more complex and realistic structures later, we simplify by choosing m = 2; whereas m can in reality take many values, there is a special significance to moving from 1 to any larger value, including 2. It immediately allows for political situations where candidates differ on some issues and agree on others. Further, again in the interest of simplification, we consider the feasible set of platforms F to be a circle (with, say, origin at (0, 0) and circumference equal to 1), just as represented in Figures 2 to 8 in Sections 3 and 4 below. The circle is capable of including fine distinctions between similar platforms, as well as diametrically opposing platforms. 6 3 For an extensive discussion of, and empirical evidence on, this issue, see Stokes (1963), p.370-371. 4 The list of important issues can of course change over time. So, the same “fixed structure” (to use the terminology of Stokes (1963)) might not be applicable at different points in time (political eras). 5 This is not an innocent supposition. Stokes (1963, p.370) notes: “What is more, when our respondents are asked directly to describe the parties in terms of the liberal-conservative distinction, nearly half confess that the terms are unfamiliar. And the bizarre meanings given the terms by many of those who do attempt to use them suggest that we are eliciting artificial answers that have little to do with the public’s everyday perceptions of the parties.” 6 The circle has been an object of intellectual interest from pre-Socratic and pre-Pythagorean times. It was analyzed in some depth by Thales of Miletus. Born in Miletus in Asia Minor (currently Turkey), in 624 BC, he was 54 years senior 4 We turn now to the electorate. We suppose a voter has preferences over the set of feasible platforms, in the form of an “ideal platform”, which is best from the voter’s point of view, other platforms being inferior. A voter votes for the candidate whose platform is “closest” to the voter’s ideal platform. We define “closest” in terms of the length of the arc between the voter’s ideal and the candidate’s platform. [We elaborate on this measure in Section 3.1.3.] Finally, we need to consider the distribution of voters, or more precisely, the distribution of the ideal platforms of voters. As an extreme case, consider (in the context of Figure 1) that even though there is a lot of variety of feasible platforms on a circle, voters do not really care about whether a candidate is pro-establishment or anti-establishment. They would then be bunched up (in terms of their ideal platforms) at two points on the circle on the horizontal axis. Because we want to emphasize the importance of multi-dimensional platforms, we do not wish to investigate such extreme cases. A more reasonable assumption is that the voters’ ideal platforms are distributed with full support on the circle. Assuming a uniform distribution on the circle (which we do in our model below) is a useful place to start to keep the model tractable. 2.2 Description of the Game There are n players (political candidates). Each player has to set up a platform at some point on the circle (with origin at (0, 0) and circumference equal to 1). Each voter has an ideal platform on the circle and votes for the candidate whose platform is closest to his own. If a voter is equi-distant to several players’ locations, he chooses randomly from them by assigning equal probability to each of those players. There is a continuum of voters, and their ideal platforms are distributed uniformly on the circle. Each player’s (political candidate’s) payoff is equal to the expected number of voters who vote for her and her aim is to maximize her payoff. Players choose their platforms simultaneously. A choice of platform by each player will be called an n-tuple of strategies or simply a placement. The aim is to analyze the Nash equilibria of this game, that is a placement, such that no player can do better (increase her payoff ) through a unilateral deviation to another platform. It is useful to coin a few more terms before we begin the analysis. A placement in which there is no platform that is chosen by more than one player will be referred to as a scattered placement. All other kinds of placements are called clustered placements. Given a placement, a stretch of the circle where no platform has been chosen by any of the players will be called an empty stretch. A Nash equilibrium in which the placement is scattered will be called a scattered Nash equilibrium. All other Nash equilibria are called clustered Nash equilibria. 3 Scattered Nash Equilibria This section provides a complete characterization of scattered Nash equilibria. If n = 2 it is easy to see that all placements are Nash equilibria. Henceforth, and without further mention, we will focus on cases where n ≥ 3. to Pythagoras, and is often regarded as the first “Greek philosopher” that proved some theorems concerning right-angled triangles and the circle, using pure deductive reasoning. In that tradition, quite apart from its implications for electoral politics and location economics, this paper may be viewed as an exercise in pure abstract reasoning. 5 3.1 Notation and Definitions of Concepts Recall that we want to present a criterion, such that given a placement, the criterion can be used easily to check whether the placement is (or is not) a Nash equilibrium. For this purpose, some notation is needed to formalize the concepts introduced above. 3.1.1 Circle and Arcs We consider a circle with circumference equal to C. 7 An arc of a circle is any connected set of points of the circle. Associated with any arc are its boundary points. The boundary points need not belong to the arc itself; for example, the arc can be open relative to the circle. If the closure of the arc is not the entire circle, it will have two boundary points. Given any two distinct points A and B on the circle, two arcs can be associated with them. One arc is the set of points traversed as one moves from A to B clockwise; we denote this by arc[A, B ]. [This set will be understood to include the points A and B.] The other arc is the set of points traversed as one moves from A to B counterclockwise. This is, of course, the same as the set of points traversed as one moves from B to A clockwise. We denote this by arc[B, A]. The set arc[A, B ]\{A, B } is denoted by arc(A, B ). Similar obvious notation applies to arcs containing B, but not A, and to arcs containing A, but not B. Note that arc(A, B ) is disjoint from arc[B, A], and therefore from arc(B, A), arc(B, A] and arc[B, A). The arc length of arc[A, B ] is defined to be equal to (C θ/360), if θ is the angle (in degrees) which arc[A, B ] subtends at the center of the circle. This is also defined to be the arc length of arc(A, B ). The arc length of arc[A, B ] is denoted by a[A, B ].8 When the two arc lengths a[A, B ] and a[B, A] are not equal, the arc with the larger arc length is called the major arc, and the arc with the smaller arc length is called the minor arc. Thus, the arc length of the minor arc is min{a[A, B ], a[B, A]}, and we denote it by ma[A, B ]; it is also equal to ma[B, A]. In what follows, without loss of generality, we take the circumference C of the circle to be equal to 1, and therefore the radius of the circle to be r = (1/2π ). 3.1.2 Candidates, Platforms and Neighborhoods In a scattered placement, each candidate i ∈ I ≡ {1, ..., n} can be identified with a distinct point (plat- form) on the circle. Thus, the placement itself can be described by an n-tuple of platforms {s1 , ..., sn }, where each si for i ∈ I is a distinct point on this circle. 9 Given a scattered placement s = {s1 , ..., sn }, there is a neighborhood Yi (s) for each candidate i ∈ I ≡ {1, ..., n}, which is defined to be the maximal arc, containing si , but not containing any sj 6= si ; that is, it is an arc S, containing si , but not containing any sj 6= si , such that if S 0 is any arc, containing si , but not containing any sj 6= si , then S 0 ⊂ S. 10 As we have defined it, a neighborhood Yi (s) is a set which is open relative to the circle. The closure of Yi (s) (relative to the circle) is denoted by Y ¯i (s). ¯ Thus, Yi (s) contains Yi (s) and the boundary points of Yi (s). Given a scattered placement s = {s1 , ..., sn }, for each candidate i ∈ I ≡ {1, ..., n}, we can define his neighbors to be: sR(i) = arg min a(si , sj ) and sL(i) = arg min a(sj , si ) (NBS) sj ∈s\{si } sj ∈s\{si } 7 This circumference is specified precisely, as soon as we pick a radius of the circle, a positive real number. 8 When the two arc lengths are not equal, the arc with the larger arc length is called the major arc, and the arc with the smaller arc length is called the minor arc. 9 Each si can be specified precisely in terms of its Cartesian co-ordinates. 10 Note that a neighborhood for player i can be a minor arc, and it can also be a major arc, depending on the positions of the other players on the circle. 6 These are the candidates with platforms closest to the platform of candidate i, on the right and on the left respectively. Clearly, we have: sR(i) 6= si and sL(i) 6= si and the neighbors are distinct : sR(i) 6= sL(i) (DNBS) The statement in (DNBS) holds because if sR(i) = sL(i) , then Y ¯i (s) is the circle itself, implying that there are just two distinct platforms on the circle, and this is impossible in a scattered placement with n ≥ 3. Using (NBS), it can be shown that: ¯i (s) = arc[sL(i) , sR(i) ] Yi (s) = arc(sL(i) , sR(i) ) and Y (NBD) ¯i (s) contains the platforms of i0 s “nearest” neighbors, while Yi (s) does not. (NBD) Informally, the set Y is a useful characterization of a neighborhood; we make use of this characterization in our analysis below. We define yi (s) to be the arc length of the arc Yi (s). 3.1.3 Behavior of Voters Each voter has an ideal platform, v, a point on the circle. The general principle that we wish to use with respect to voting behavior is that each voter votes for the candidate whose platform is “closest” to her ideal platform v. To implement this principle, we need to be explicit about what “closest” means. However, without specifying a particular distance function, we can say that a necessary condition for the voter to vote for platform si (of candidate i) is that there be an arc joining v with si (either arc(v, si ) or arc(si , v )) which contains no other platform sj (for j 6= i). For if there is always some platform sj in between v and si (that is, there is some sj in arc(v, si ) and there is some sk in arc(si , v )), then si cannot be closest to v by any reasonable notion of closeness. A consequence of this is that a voter whose ideal platform v falls outside Y ¯i (s) will definitely not vote for candidate i, since sL(i) is in arc(v, si ) and sR(i) is in arc(si , v ). So, the only voters who can possibly vote for candidate i are those whose ideal platform v falls in ¯i (s). If v ∈ (si , sR(i) ], we postulate that the voter votes for si when a(si , v ) < a(v, sR(i) ], votes for Y sR(i) when a(si , v ) > a(v, sR(i) ], and votes for either platform with equal probability when a(si , v ) = a(v, sR(i) ]. A similar rule is postuated if v ∈ [sL(i) , si ); that is, the voter votes for si when a(v, si ) < a[sL(i) , v ), votes for sL(i) when a(v, si ) > a[sL(i) , v ), and votes for either platform with equal probability when a(v, si ) = a[sL(i) , v ). Finally, if v = si , then the voter votes for si . Unlike the economics of location of vendors, and customers purchasing from the nearest vendor, where the above postulate would be entirely natural, it is a debatable postulate in electoral politics. The use of the arc length is not itself central to a possible objection to the postulate. It is the fact that a clockwise arc length is compared to an anti-clockwise arc length in deciding on voting behavior. If, for example, a voter always seeks the closest platform, moving in a clockwise direction from his ideal platform, then this postulate of voting behavior would not hold. Because closeness of a platform to another platform is primarily a mental concept, without a convenient physical counterpart, the analogy with spatial location theory need not carry over. 3.1.4 Payoffs of Candidates Given the postulate of voting behavior, and the assumption that the ideal platforms of voters are uniformly distributed on the circle, the payoff pi (s) of candidate i is one-half the arc length of Yi (s); that is, pi (s) = yi (s)/2. It measures the percentage of the votes that candidate i expects to get. 7 In studying scattered Nash equilibria, it is important to be able to deal with some clustered place- ments. This is because, for each player, one has to consider all unilateral deviations in platforms from her given platform (in the scattered placement). Consider a scattered placement {s1 , ..., sn }, and focus on player i. Player i can consider a unilateral deviation to a platform s0 0 i . Now si can coincide with sk for some k 6= i. Thus, after such a deviation, we have a clustered placement, and one must be able to compute the payoff to player i from such a deviation and compare that payoff to her payoff from the scattered placement {s1 , ..., sn }. 11 To see how this is done, notice that after such a unilateral deviation by player i, we have a clustered placement s0 = {s1 , ., s0 i , .., sn } and we can define a neighborhood Yi (s ) 0 0 0 0 as above to be the maximal arc, containing si , but not containing any sj 6= si . Note that Yk (s ) coincides with Yi (s0 ). The arc length of Yi (s0 ) is denoted by yi (s0 ). The payoff to player i in the new placement s0 is defined to be pi (s0 ) = yi (s0 )/4, since both i and k have to share the same neighborhood Yi (s0 ) in the placement s0 . 3.2 Characterizing Scattered Nash Equilibria Given a scattered placement s = {s1 , ..., sn }, an empty stretch is any arc that does not contain any si for i ∈ {1, ..., n}. The arc length of the empty stretch of maximum arc length is denoted by x(s). We define: y (s) = min{y1 (s), ..., yn (s)} A characterization of scattered Nash equilibria can be obtained by just comparing y (s) with x(s). Theorem 1 (A) Given a scattered placement s = {s1 , ..., sn }, if: y (s) ≥ x(s) (1) then the placement is a Nash equilibrium. (B) Given a scattered placement s = {s1 , ..., sn }, if: y (s) < x(s) (2) then the placement is not a Nash equilibrium. Proof. (A) Pick any j ∈ I, and fix it in what follows. By (1), and the definition of y (s), we have: pj (s) = (yj (s)/2) ≥ (x(s)/2) (3) Suppose j unilaterally changes his platform from sj to some other point s0 j on the circle. Denote the new placement created by s0 = {s1 , .., s0j , .., sn }. We have either (a) s0 is a scattered placement, or (b) s0 is a clustered placement. Case (a): If s0 0 j ∈ Yj (s), then the payoff of j does not change. If sj is not in Yj (s), then since s 0 0 is a scattered placement, sj ∈ Yk (s), the neighborhood of some other seller k ∈ I (with k 6= j ). The neighborhood Yk (s) consists of two empty stretches, and the new neighborhood of s0 j will have to be one of these two empty stretches (no longer empty after it is occupied by s0 j ). Thus, we must have yj (s0 ) ≤ x(s), and so: pj (s0 ) ≤ (x(s)/2) (4) Clearly, (3) and (4) imply that there is no incentive for j to change his platform to s0 j . This establishes that the placement s is a Nash equilibrium in Case (a). 11 Note that the deviation can result in two players (but not more) being at the same location, since the original placement is scattered. 8 Case (b): In this case, there is some k ∈ I, with k 6= j, such that sk = s0 j . There are two subcases ¯k (s) is non-empty. In subcase (I), ¯k (s); (II) Yj (s) ∩ Y to consider: (I) Yj (s) is disjoint from Y Yk (s0 ) = Yk (s) (5) and so Yj (s0 ) = Yk (s). 12 The neighborhood Yk (s) contains two empty stretches, and the point sk . Thus, yk (s) ≤ 2x(s), and we get: pj (s0 ) = yj (s0 )/4 = yk (s)/4 ≤ 2x(s)/4 = (x(s)/2) (6) Clearly, (3) and (6) imply that there is no incentive for j to change his platform to s0 j . This establishes that the placement s is a Nash equilibrium in Case (b)(I). ¯k (s) is non-empty. Let us write: In subcase (II), Yj (s) ∩ Y Yk (s) = arc(sL(k) , sR(k) ) and Yj (s) = arc(sL(j ) , sR(j ) ) (7) We now claim 13 that: Either (i) sj = sL(k) and sR(j ) = sk ; or (ii) sk = sL(j ) and sR(k) = sj (8) Taking the claim for granted, we can proceed to complete the proof of Case (b)(II) as follows. In case (i) of (8), after candidate j changes his platform from sj to s0 j = sk , the entire arc(sL(j ) , sj ] becomes part of the neighborhood of seller j , in addition to Yk (s). That is, Yj (s0 ) = arc(sL(j ) , sj ] ∪ Yk (s) = arc(sL(j ) , sL(k) ] ∪ arc(sL(k) , sR(k) ) = arc(sL(j ) , sL(k) ] ∪ arc(sL(k) , sk ) ∪ arc[sk , sR(k) ) = arc(sL(j ) , sL(k) ] ∪ arc(sL(k) , sR(j ) ) ∪ arc[sk , sR(k) ) = arc(sL(j ) , sj ] ∪ arc(sj , sR(j ) ) ∪ arc[sk , sR(k) ) = Yj (s) ∪ arc[sk , sR(k) ) (9) where we have used (8)(i) in lines 2,4 and 5 of (9). [This is also the new neighborhood Yk (s0 ) of seller k]. Since arc(sk , sR(k) ) is one of the two empty stretches of Yk (s), its arc length is at most x(s), and so the arc length of arc[sk , sR(k) ) is also at most x(s). The arc length of Yj (s) is yj (s). Thus, the arc length of Yj (s0 ) is ≤ x(s) + yj (s). Consequently, pj (s0 ) ≤ [x(s) + yj (s)]/4 ≤ 2yj (s)/4 = yj (s)/2 (10) where the second inequality in (10) follows from (1). Clearly, (3) and (10) imply that there is no incentive for j to change his platform to s0 j . This establishes that the placement s is a Nash equilibrium, when case (i) of claim (8) holds. If case (ii) of claim (8) holds, the proof is similar to the one just given for case (i) of claim (8). This establishes that the placement s is a Nash equilibrium in Case (b)(II), and completes the proof of part (A) of the theorem. (B) By (2), and the definition of y (s), there is h ∈ I, such that yh (s) = y (s) < x(s). Then: ph (s) < (x(s)/2) (11) 12 While the claim (5) is intuitively clear, it takes a bit of work to establish this analytically. It is included in an Appendix. 13 Claim (8) is intuitively clear, but it takes a bit of work to establish this analytically. It is included in an Appendix. 9 Now h can relocate from platform sh to a platform s0 h (say) in an empty stretch with arc length x(s). Then the new neighborhood of h is the empty stretch with arc length x(s) (no longer empty after it is occupied by s0 h ). Consequently, ph (s0 ) = (x(s)/2) (12) Clearly, (11) and (12) imply that h can increase her payoff by a unilateral deviation from platform sh to platform s0 h . So, the (original) placement s cannot be a Nash equilibrium. This completes the proof of part (B) of the theorem. A consequence of Theorem 1 is the following result, which provides a sufficient condition for a scattered placement s to be a Nash equilibrium. Note that, to use this criterion, one does not need to calculate y (s). Corollary 1 Given a scattered placement s = {s1 , ..., sn }, if: 1 x(s) ≤ (13) n−1 then the placement s is a Nash equilibrium. Proof. We claim that: y (s) ≥ x(s) (14) Suppose, on the contrary that y (s) < x(s). Then, there is j ∈ I such that: yj (s) = y (s) < x(s) (15) Since x(s) is the arc length of the largest empty stretch, we can find a set of points X (s) which is an empty stretch, with arc length x(s). [There could be several such sets; we are picking one and calling it X (s)]. Using (13) and (15), we get: 2 x(s) + yj (s) < 2x(s) ≤ n−1 and so: 2 n−3 1 − x(s) − yj (s) > 1 − = ≥0 (16) n−1 n−1 If the neighborhood Yj (s) overlaps with X (s) (that is Yj (s) ∩ X (s) 6= φ), then X must be a subset of Yj (s), and consequently yj (s) ≥ x(s), contradicting (9). Thus, Yj (s) does not overlap with the empty stretch X (s), with arc length x(s). Note that Yj (s) consists of two empty stretches (and the point sj ) and neither one overlaps with X (s). If n = 3, then there are no other empty stretches and we must have yj (s) + x(s) = 1, but this contradicts (16). Thus, we must have n > 3 and there are a total of (n − 3) empty stretches remaining (other than X (s) and the two empty stretches in Yj (s)). Let z (s) be the maximum of the (arc) lengths of these remaining empty stretches. Consequently, (n − 3)z (s) ≥ 1 − x(s) − yj (s) (17) Using (16) in (17), we obtain: 1 z (s) > (18) n−1 Clearly, (18) contradicts (13) and establishes our claim (14). Now, the result follows directly from Theorem 1. 10 3.2.1 Geometric Illustration for n = 3 To hone our intuition for the analysis used in Theorem 1, it is useful to consider the special case of n = 3. Consider the scattered placement described in Figure 2. Figure 2: Illustration of Theorem 1(A) It is easy to see no player can do better by shifting platform on the same stretch (strictly) between the other two players. Note, for instance that player 1 will get exactly half the votes on the clockwise stretch traversed from her platform s1 to the platform s3 of player 3 and, likewise, half the votes on the anti-clockwise stretch traversed from her platform s1 to the platform s2 of player 2. In other words, player 1 gets half the votes on the stretch of rotary between s2 and s3 on the side where s1 is located. Since this makes no mention of where s1 is located on this stretch, any movement by player 1, where she remains on the same side of the rotary leaves her payoff unchanged. [Analytically, we expressed this above by saying that if s1 is located anywhere on the arc(s2 , s3 ), then her payoff remains the same; this is the arc traversed as one moves from s2 to s3 in a clockwise direction.] Hence to check if a scattered placement is a Nash equilibrium, all we have to check is if any player is better off by relocating her platform to another empty stretch. For instance, can player 1 do better by changing her platform to the southern stretch of the rotary between s2 and s3 ? [Analytically, we expressed this above by analyzing whether player 1 can do better by relocating from platform s1 to some platform s0 1 on the arc(s3 , s2 ); this is the arc traversed as one moves from s3 to s2 in a clockwise direction.] Clearly, in Figure 2, the southern stretch of the rotary between s2 and s3 is less than (1/2), 11 and so player 1 cannot do better by such a relocation of her platform. Given the symmetry of the locations of the three players, the same argument applies to players 2 and 3 as well. So, the placement in Figure 2 is a Nash equilibrium. Now consider the case where the empty stretch arc(s3 , s2 ) is more than (1/2). This is illustrated in Figure 3. Figure 3: Illustration of Theorem 1(B) It is obvious that such a placement cannot be Nash, since player 1 can shift her platform from s1 in the north connector between s2 and s3 to s01 in the south connector between s2 and s3 . 3.3 Symmetric and Asymmetric Scattered Nash Equilibria Corollary 1 has the following implication, which might be of interest. In the equally spaced case, the longest empty stretch is (1/n), and therefore such a scattered placement is a Nash equilibrium. So, for all placements sufficiently close to the equally spaced case, x is close to (1/n), and therefore less than [1/(n − 1)]. Thus, all such scattered placements are also Nash equilibria by Corollary 1. That is, there is a continuum of scattered Nash equilibria, clustered around the equally spaced placement. The fact that the players have no distinctive features ex ante (they can choose platforms anywhere on the cicle, and once located the same payoff rule applies to all of them) does not, of course, mean that they receive the same or even similar payoffs in a Nash equilibrium. In fact, distinctly asymmetric Nash equilibria can arise in this model. We begin by describing an example with three players, which can be instructive. 12 3.3.1 The Advantage of Appearing Different Example 1: With Cartesian coordinates, consider the center of the circle to be at (0, 0). There are three players, and the scattered placement s is described as follows. The platform of player 1 is located at (r, 0), where r = (1/2π ). The platforms of players 2 and 3 are located near (−r, 0), with the platform for 2 slightly above the axis on the circle, and the platform for 3 symmetrically slightly below the axis on the circle. (See Figure 4.) To be precise, the platform of 2 is located at (−(a2 − ε2 )1/2 , ε) and the platform of 3 is located at (−(a2 − ε2 )1/2 , −ε), where 0 < ε < a, and we are to suppose that ε is close to zero. That is, candidates 2 and 3 are very alike in their platforms, while candidate 1 is very different from either one of them. Figure 4: Asymmetric Scattered Nash Equilibrium (Example 1) Note that yi (s) exceeds (1/2) for all i ∈ I = {1, 2, 3}, and x(s) is smaller than (1/2). Thus, s is a Nash equilibrium by Theorem 1. [In fact, Corollary 1 can also be applied directly in this case to reach this conclusion.] Now, notice that as ε → 0, we have the payoff of player 1 approaching (1/2), as her neighborhood approaches the entire circle, while the payoffs of players 2 and 3 approach (1/4). There is a big advantage from appearing different. 3.3.2 The Distribution of Payoffs in Scattered Nash Equilibria It is a rather remarkable fact that the simple example just discussed illustrates a general result on the distribution of payoffs in Nash equilibria in this model. Non-uniqueness of Nash equilibria is the major 13 drawback in its predictive power regarding the outcome of the game. In our next result, instead of focusing on equilibrium locations of platforms, we shift our focus to equilibrium payoffs, and we find that these are subject to rather stringent bounds. Specifically, the Nash equilibrium payoffs of all players must lie in the interval: ∙ ¸ 1 2 Π= , (DOP) 2(n − 1) n + 1 for an arbitrary number n of players, and for an arbitrary Nash equilibrium. As an implication, in a four-way race, no candidate can get less than one-sixth of the vote in a scattered Nash equilibrium. This makes (1/6) a useful benchmark to decide whether to change one’s strategy (platform). That is, it is all right to get less than a quarter of the vote (perform worse than average), but it is not all right to get less than a sixth of the vote.14 We now proceed to establish the formula (DOP) using Theorem 1. Proposition 1 If a scattered placement s = {s1 , ..., sn } is a Nash equilibrium, then: 1 2 ≤ pi (s) ≤ for all i ∈ I = {1, ..., n} (19) 2(n − 1) n+1 Proof. Given the scattered placement s = {s1 , ..., sn }, recall that the arc length of the empty stretch of maximum arc length is denoted by x(s), and we define: y (s) = min{y1 (s), ..., yn (s)}; z (s) = max{y1 (s), ..., yn (s)} Note that, given the scattered placement s = {s1 , ..., sn }, there are n empty stretches. Each empty stretch is contained in the neighborhoods of two distinct players. Since the arc lengths of the n empty stretches must add up to 1 (the circumference of the circle), the arc lengths of the neighborhoods of the n players must add up to 2; that is: Xn yi (s) = 2 (20) i=1 There is k ∈ I = {1, ..., n} such that yk (s) = z (s). Since Yk (s) consists of two empty stretches (and the point sk ), we have: z (s) = yk (s) ≤ 2x(s) (21) Using (20) and (21), and Theorem 1, we get: X 2 = z (s) + yi (s) i6=k ≥ z (s) + (n − 1)x(s) ≥ z (s) + (n − 1) [z (s)/2] ∙ ¸ n−1 = z (s) 1 + 2 ∙ ¸ n+1 = z (s) (22) 2 14 It might be difficult for a candidate to change his platform significantly, given his ideological beliefs. On a more pragmatic note, significant changes in platform by a candidate to suit an election might not be taken seriously by voters, who might rightly view it as an opportunistic move. In such cases, (1/6) would also be a useful benchmark to decide whether to quit a race. 14 where we used (20) in line 1, Theorem 1 in line 2 and (21) in line 3. This yields: ∙ ¸ 4 z (s) ≤ n+1 so that: ∙ ¸ 2 pi (s) ≤ pk (s) = [z (s)/2] ≤ for all i ∈ I (23) n+1 This establishes the right-hand inequality in (19). We proceed now to establish the left-hand inequality in (19). Note that by using (21) and Theorem 1, we have: z (s) = yk (s) ≤ 2x(s) ≤ 2y (s) (24) There is j ∈ I = {1, ..., n} such that yj (s) = y (s). The neighborhood Yj (s) consists of two empty stretches (and the point sj ). Call these empty stretches Yj 1 (s) and Yj 2 (s). The corresponding arc lengths can be written as [yj (s)/2] + ε and [yj (s)/2] − ε, where − [yj (s)/2] < ε < [yj (s)/2] . The empty stretch Yj 1 (s) must be shared with another player r 6= j ; that is, Yj 1 (s) must be one of the two empty stretches of Yr (s), the neighborhood of player r. Similarly, empty stretch Yj 2 (s) must be shared with another player t 6= j, r; that is, Yj 2 (s) must be one of the two empty stretches of Yt (s), the neighborhood of player t. Using (20), we can now write: X 2 = yj (s) + yr (s) + yt (s) + yi (s) i6=j,r,t ≤ yj (s) + yr (s) + yt (s) + (n − 3)z (s) ≤ yj (s) + {[yj (s)/2] + ε + x(s)} + {[yj (s)/2] − ε + x(s)} + (n − 3)z (s) = 2yj (s) + 2x(s) + (n − 3)z (s) ≤ 2y (s) + 2y (s) + (n − 3)z (s) ≤ 2y (s) + 2y (s) + 2(n − 3)y (s) (25) where we have used Theorem 1 in line 5 and (24) in line (6) of (25). Thus, we obtain: 2 1 y (s) ≥ = (26) 2n − 2 n−1 Using (6), we have: ∙ ¸ 1 pi (s) ≥ pj (s) = [y (s)/2] ≥ for all i ∈ I 2(n − 1) which establishes the left-hand inequality in (19). Remark: In the context of Example 1 with n = 3, we see that the lower bound of 25% in (19), and the upper bound of 50% in (19) are approached as we let ε → 0. 4 Clustered Nash Equilibria To analyze clustered Nash equilibria, it is useful to have a more general setup of the framework of Section 3, which will include all placements, including both scattered and clustered placements. Consider as before that there are n ≥ 3 players. A placement will be described by (m, s, t) where m ≤ n is a positive integer, s = {s1 , ..., sm } an m−tuple of distinct points 15 on the circle (with 15 Each si can be specified precisely in terms of its Cartesian coordinates. 15 circumference equal to 1), and t = {t1 , ..., tm } an m−tuple of positive integers, with t1 + · · · + tm = n. In the placement c = (m, s, t), there are m locations on the circle which represent distinct platforms. For i ∈ J = {1, ..., m}, there are ti candidates who share the platform si . A scattered placement is a special case, where m = n, and ti = 1 for each i ∈ J. Concepts related to this framework can be defined as in Section 3.1, but with a few differences which justify our going over these concepts again. Given a placement c = (m, s, t), with m ≥ 2, there is a neighborhood Yi (c) for each platform si , where i ∈ J ≡ {1, ..., m}, which is defined to be the maximal arc, containing si , but not containing any sj 6= si . Note that the subscript i in Yi (c) keeps track of the platform si , and not a particular candidate who has announced platform si . All candidates sharing the same platform si have the same neighborhood Yi (c). Note also the qualification m ≥ 2 in the above definition. If m = 1, then all platforms are identical, and the neighborhood for each candidate announcing the only platform is the entire circle. As in Section 3.1, a neighborhood is an arc, and we define yi (c) to be the arc length of this arc. As we have defined it, when m ≥ 2, a neighborhood Yi (c) is a set which is open relative to the circle. The ¯i (c) contains Yi (c) and the boundary ¯i (c). Thus, Y closure of Yi (c) (relative to the circle) is denoted by Y points of Yi (c). Given a placement c = (m, s, t), with m ≥ 2, for each platform si (with i ∈ J ), we can define the neighboring platforms by: sR(i) = arg min a(si , sj ) and sL(i) = arg min a(sj , si ) (NBS) sj ∈s\{si } sj ∈s\{si } Clearly, we have: sR(i) 6= si and sL(i) 6= si Unlike in Section 3.1, it is possible to have sR(i) = sL(i) . [In this case, there are exactly two distinct platforms.] Using (NBS), it can be shown that when m ≥ 2, ¯i (c) = arc[sL(i) , sR(i) ] Yi (c) = arc(sL(i) , sR(i) ) and Y (NBD) When m ≥ 2, the payoff pi (c) of each candidate who has announced the platform si (with i ∈ J ) is: yi (c) pi (c) = (PO) 2ti When m = 1, there is exactly one platform and the payoff p(c) of each candidate is: 1 p(c) = (PO1) n 4.1 An Example of a Clustered Nash Equilibrium We start by providing an example of a clustered Nash equilibrium. This can be viewed as a limiting version of Example 1. Example 2: With Cartesian coordinates, consider the center of the circle to be at (0, 0). There are three players, and the placement c = (m, s, t) is described as follows. The platform of player 1 is s1 = (r, 0). Players 2 and 3 have the same platform, specified by s2 = (−r, 0). Thus, we have m = 2, s = {s1 , s2 } and t = {t1 , t2 } = {1, 2}. This placement is illustrated in Figure 5. 16 Figure 5: Clustered Nash Equilibrium (Example 2) Here we have y1 (c) = 1, y2 (c) = 1, and so p1 (c) = (1/2), while the payoff of each player who has announced the same platform s2 is p2 (c) = (1/4). We can check that c is a Nash equilibrium by using the following elementary analysis. A unilateral deviation by any player will create a new placement c0 = (m0 , s0 , t0 ), where the platforms of the other two players remain the same as in the placement c. If player 1 changes his platform to s0 0 1 6= s2 , his neighborhood remains the same as in c, and his payoff remains (1/2). If s1 = s2 , then his neighborhood remains the same as in c, but his payoff becomes (1/3). So, clearly, player 1 has no incentive to deviate from s1 . Consider next a unilateral deviation by player 2 from her original platform of s2 to a new platform s0 0 2 6= s2 . If s2 6= s1 , her new neighborhood is the semi-circle, and so her new payoff is (1/4). If, on the other hand, s0 2 = s1 , then her neighborhood is the full circle, and her payoff is again (1/4).So, clearly, player 2 has no incentive to deviate from s2 . Similarly, player 3 has no incentive to deviate from s2 . 4.2 General Properties of Nash Equilibria We now proceed to establish four general properties of Nash equilibria. Given that we already have a complete characterization of scattered Nash equilibria in Section 3, the focus of three of these properties is on clustered Nash equilibria. First, in any clustered Nash equilibrium, there cannot be more than two candidates announcing the same platform. That is, for any Nash equilibrium placement c = (m, s, t), we must have ti ∈ {1, 2} for 17 all i ∈ J. This implies that m ≥ 2 (since we have n ≥ 3). Second, if c = (m, s, t) is a clustered Nash equilibrium, and there are two candidates who have announced the same platform sj , then sj must be precisely at the mid-point of its neighborhood Yj (c). Third, the analogue of part (B) of Theorem 1 is valid for all Nash equilibria. To describe it, let us define two key concepts. Given a placement c = (m, s, t), an empty stretch is any arc that does not contain any si for i ∈ J. The arc length of an empty stretch of maximum arc length (among all empty stretches) is denoted by x(c). We define for m ≥ 2, ½ ¾ y1 (c) ym (c) y (c) = min , ..., t1 tm If c = (m, s, t) is any Nash equilibrium, then it must be the case that y (c) ≥ x(c). Fourth, if c = (m, s, t) is any clustered Nash equilibrium, then it must be the case that y (c) = x(c). Proposition 2 If a placement c = (m, s, t) is a Nash equilibrium, then the following properties must hold: (i) ti ∈ {1, 2} for all i ∈ J, and m ≥ 2. (ii) For each location si with ti = 2, si must be at the midpoint of its neighborhood Yi (c). (iii) y (c) ≥ x(c). (iv) If the placement c is clustered, then y (c) = x(c); further, for each location si with ti = 2, each of the two empty stretches of Yi (c) has arc length x(c). Proof. (i) Let c = (m, s, t) be a Nash equilibrium placement. Suppose there is some platform sj which has been announced by k ≥ 3 candidates. First consider the case where k = n; that is, all players have announced the same platform. Then the neighborhood of each player is the entire circle, and the payoff to each player is (1/n). If one player deviates to another platform she will still have the entire circle as her neighborhood, but her payoff will be (1/2). Since n ≥ 3, a deviation is worthwhile. Hence c is not a Nash equilibrium. Now suppose 3 ≤ k < n, so that m ≥ 2. The neighborhood of each player who has announced platform sj is Yj (c), and the payoff of each player who has announced platform sj is pj (c) = yj (c)/2tj = yj (c)/2k. The neighborhood Yj (c) consists of two empty stretches (and the point sj ). Call these empty stretches Yj 1 (c) and Yj 2 (c). Comparing the arc lengths of these empty stretches, pick an empty stretch whose arc length is not smaller than the arc length of the other empty stretch, and call it Yj 1 (c) (without loss of generality). If one of the k players who has announced platform sj deviates to a platform s0 j ∈ Yj 1 (c), then this player’s neighborhood becomes Yj 1 (c) and so this player’s payoff becomes half the arc length of Yj 1 (c), which will therefore be greater than or equal to [yj (c)/4]. Since k ≥ 3, yj (c) yj (c) > 4 2k Hence, the player benefits by deviating from sj to s0 j . So c cannot be a Nash equilibrium. This establishes that ti ∈ {1, 2} for all i ∈ J. If m = 1, then there would be at least three players who announce the same platform, since n ≥ 3. But this is ruled out by the property just established. Thus, we must have m ≥ 2. (ii) Let c = (m, s, t) be a Nash equilibrium placement. Suppose there is some platform sj which has been announced by tj = 2 players. The neighborhood of each player who has announced platform sj is Yj (c), and the payoff of each player who has announced platform sj is pj (c) = yj (c)/2tj = yj (c)/4. The neighborhood Yj (c) consists of two empty stretches (and the point sj ). Call these empty stretches 18 Yj 1 (c) and Yj 2 (c). Suppose the arc lengths of these two empty stretches are not the same. Pick the empty stretch whose arc length is the larger of the two, and call it Yj 1 (c) (without loss of generality). If one of the two players who has announced platform sj deviates to a location s0j ∈ Yj 1 (c), then this player’s neighborhood becomes Yj 1 (c) and so this player’s payoff becomes half the arc length of Yj 1 (c), which will therefore be greater than [yj (c)/4]. Hence, the player benefits by deviating from sj to s0 j . So c cannot be a Nash equilibrium. This establishes that the arc lengths of Yj 1 (c) and Yj 2 (c) must be the same. That is, sj must be at the midpoint of its neighborhood Yj (c). (iii) Let c = (m, s, t) be a Nash equilibrium placement. Suppose y (c) < x(c). By the definition of y (c), there is some platform sh (with h ∈ J ) such that yh (c)/th = y (c) < x(c). Then the payoff of each player who has announced platform sh is: ph (c) = yh (c)/2th < (x(c)/2) Now a player (who has announced platform sh ) can relocate from sh to a platform s0 h in an empty stretch with arc length x(c). Then the new neighborhood of this player is the empty stretch with arc length x(c) (no longer empty after it is occupied by this player). Consequently, the new payoff to this player is (x(c)/2). Hence, this player benefits by deviating from sj to s0 j . So, the placement c cannot be a Nash equilibrium. This contradiction establishes that y (c) ≥ x(c). (iv) Let c = (m, s, t) be a Nash equilibrium placement, where the placement is clustered. Then, there is some platform sh (with h ∈ J ) which has been announced by more than one player. By (i), there are two players who have announced platform sj . Thus, by definition of y (c), we have: yj (c) ≥ y (c) ≥ x(c) (27) 2 where the second inequality in (27) follows from result (iii). The neighborhood of each player who has announced platform sj is Yj (c), and Yj (c) consists of two empty stretches (and the point sj ). Thus, yj (c) ≤ 2x(c) (28) Combining (27) and (28), we obtain: yj (c) yj (c) ≥ y (c) ≥ x(c) ≥ (29) 2 2 so that equality must hold in place of each inequality in (29). Thus, y (c) = x(c) must hold. Further, yj (c) = 2x(c), so by result (ii), each of the two (equal) empty stretches of Yj (c) constitutes a largest empty stretch in the placement c. Remark: Result (i) in Proposition 2 sheds interesting light on the median voter theorem which says that, when the available platforms are points on a straight line, two candidates will invariably choose the same platform (the median). What Example 2 and Proposition 2 (i) show is that in an electoral democracy with voter preference on a circle of available platforms, two candidates may choose the same political agenda, but there will never be three candidates doing so. 4.3 A Property of Clustered Nash Equilibria Results (i), (ii) and (iv) of Proposition 2 place rather strong restrictions on clustered Nash equilibria. If n = 3 and c = (m, s, t) is a clustered Nash equilibrium, then there must be precisely two platforms. One 19 candidate would announce one platform; call this s1 . The other two candidates would both announce a distinct platform, s2 . Given the platform s2 , property (ii) of Proposition 2 demands that it be at the midpoint of its neighborhood. This implies that s1 must be diametrically opposite to s2 on the circle. In other words, Example 2 is essentially the only example of a clustered Nash equilibrium when m = 3. In particular, the distribution of payoffs in any clustered Nash equilibrium must be: ½ ¾ 1 1 1 Ω= , , 4 4 2 More generally, for arbitrary n ≥ 3, we note the following property for clustered Nash equilibria, which should be compared to Corollary 1 for scattered Nash equilibria. It is a useful property which is helpful in studying the distribution of payoffs in arbitrary Nash equilibria, which we take up in the next subsection. Corollary 2 If a placement c = (m, s, t) is a clustered Nash equilibrium, then: 1 x(c) ≥ (30) n−1 Proof. Given the placement c = (m, s, t), there are m empty stretches. Since the arc lengths of the m empty stretches must add up to 1 (the circumference of the circle), we must have: mx(c) ≥ 1 (31) Since the placement c = (m, s, t) is a clustered Nash equilibrium, there is at least one platform sk , which is announced by multiple candidates; by Proposition 2 (i), we know in fact that there are precisely two candidates who announce platform sk . The remaining (n − 2) candidates announce the remaining (m − 1) platforms. In order that each of the remaining (m − 1) platforms is announced by at least one candidate each, we must have: n−2≥m−1 and consequently n − 1 ≥ m. Using this in (31), we obtain (30). 4.4 Distribution of Payoffs in Nash Equilibria We now present a generalization of Proposition 1, extending that result to all Nash equilibria. It will be noted that in our result, the bounds on the payoffs are determined in terms of n, the number of players (candidates), and independent of m, the number of platforms announced in a Nash equilibrium. Thus, one needs no information about the equilibrium placements to make use of the bounds. Theorem 2 If a placement c = (m, s, t) is a Nash equilibrium, then: 1 2 ≤ pi (c) ≤ for all i ∈ J = {1, ..., m} (DOP’) 2(n − 1) n+1 Proof. Given the placement c = (m, s, t), recall that the arc length of the empty stretch of maximum arc length is denoted by x(c), and we define: ½ ¾ ½ ¾ y1 (c) ym (c) y1 (c) ym (c) y (c) = min , ..., ; z (c) = max , ..., t1 tm t1 tm Note that, given the placement c = (m, s, t), there are m empty stretches. Each empty stretch is contained in the neighborhoods of two distinct platforms. Since the arc lengths of the m empty 20 stretches must add up to 1 (the circumference of the circle), the arc lengths of the neighborhoods of the m platforms must add up to 2; that is: Xm yi (c) = 2 (32) i=1 There is k ∈ J = {1, ..., m} such that (yk (c)/tk ) = z (c). By Proposition 2 (i), there are two possibilities (a) tk = 2; (b) tk = 1. In case (a), we know by Proposition 2 (iv) that yk (c) = 2x(c). Thus, we have: z (c) = yk (c)/tk = 2x(c)/tk = x(c) (33) and so by definition of z (c), yi (c)/ti ≤ z (c) = x(c) for all i ∈ J (34) But, we also know from the definition of y (c) and Proposition 2 (iii) that: yi (c)/ti ≥ y (c) = x(c) for all i ∈ J (35) Thus, we have: yi (c)/ti = y (c) = z (c) = x(c) for all i ∈ J (36) Using (36) in (32), we obtain: m X m X ∙ ¸ Xm yi (c) 2= yi (c) = ti = ti x(c) = nx(c) (37) ti i=1 i=1 i=1 Thus, (34) and (37) yield: ∙ ¸ ∙ ¸ 2 1 pi (c) = yi (c)/2ti ≤ x(c)/2 = (1/2) = for all i ∈ J n n Since n ≥ 3, we have (1/n) < [2/(n + 1)], and so the right-hand inequality in (DOP’) holds in case (a). In case (b), we have tk = 1, and so: z (c) = yk (c)/tk = yk (c) ≤ 2x(c) (38) Using (32) and (38), and Proposition 2 (iii), we get: X 2 = yk (c) + yi (c) i6=k X ≥ z (c) + ti y (c) i6=k X ≥ z (c) + ti x(c) i6=k X ≥ z (c) + ti {z (c)/2} i6=k ⎡ ⎤ X = z (c) ⎣1 + (ti /2)⎦ i6=k " m # X = z (c) {1 − (tk /2)} + (ti /2) i=1 = z (c) [(1/2) + (n/2)] (39) 21 where we used (32) in line 1, Proposition 2 (iii) in line 3 and (38) in line 4. This yields: ∙ ¸ 4 z (c) ≤ n+1 so that: ∙ ¸ 2 pi (c) = yi (c)/2ti ≤ z (c)/2 ≤ for all i ∈ J n+1 This establishes the right-hand inequality in (DOP’) in case (b). We proceed now to establish the left-hand inequality in (DOP’). We divide our analysis into two cases (a) c = (m, s, t) is a scattered Nash equilibrium; and (b) c = (m, s, t) is a clustered Nash equilibrium. In case (a), the result follows directly from Proposition 1. We now analyze case (b). In case (b), we note that by Corollary 2, 1 x(c) ≥ (40) n−1 Thus, for all platforms si (with i ∈ J ) we must have: ∙ ¸ 1 pi (c) = yi (c)/2ti ≥ y (c)/2 ≥ x(c)/2 ≥ 2(n − 1) where the second inequality follows from Proposition 2 (iii), and the last inequality from (40). This establishes the left-hand inequality in (DOP’) in case (b). 4.5 Best Bounds in the Distribution of Payoffs In the context of Example 2 with n = 3, we see that the lower bound of [1/2(n − 1)] = 25% in (DOP’), and the upper bound of [2/(n + 1)] = 50% in (DOP’) are attained. This shows that the bounds in (DOP’) are the best possible for n = 3. This raises the question of whether, in general, the bounds given in Theorem 2 (for the distribution of payoffs in an arbitrary Nash equilibrium) are the best possible. In this subsection, we provide answers to this question separately for the lower bound in (DOP’) and the upper bound in (DOP’). 4.5.1 Lower Bound in the Distribution of Payoffs We present an example to show that the lower bound of the interval, given in both Proposition 1 and Theorem 2, is the “best possible” in the sense that given any n ≥ 3, it is possible to construct a scattered Nash equilibrium with n players, such that the payoff of some player in that equilibrium is exactly equal to [1/2(n − 1)]. Example 3: Let n ≥ 3 be given. Divide the circumference of the circle into (n − 1) equal parts. This will generate (n − 1) points on the circle, equally spaced. Place the platforms {s1 , ..., sn−1 } at these (n − 1) points. To make the instruction more precise, place s1 at any one of the (n − 1) points. Place s2 at the next available point (of the remaining n − 2 points) as you go clockwise around the circle, starting from s1 . Continue similarly with s3 , ..., sn−1 . Finally, place the platform sn at the midpoint of the arc arc(sn−1 , s1 ). For an illustration of this procedure for n = 5, see Figure 6. The largest empty stretch is: 1 x(s) = (41) n−1 22 Figure 6: Lower Bound of DOP (Example 3) The neighborhood with the smallest arc length is: 1 y (s) = yn (s) = (42) n−1 Thus, by Theorem 1, the placement s = {s1 , ..., sn } described above is a Nash equilibrium. Using (42), the payoff of player n in this Nash equilibrium is: yn (s) 1 pn (s) = = (43) 2 2(n − 1) which is precisely the lower bound of Π in (DOP’). Remark: The lower bound in (DOP’) is also attained when n = 2, since in that case, the payoff of each player in any Nash equilibrium is equal to (1/2). 4.5.2 Upper Bound in the Distribution of Payoffs We now focus on the question whether the upper bound of the interval, given in both Proposition 1 and Theorem 2, is the “best possible”. When n ≥ 3, and n is odd, we show that the upper bound in (DOP’) is the best possible in the following sense. Given n ≥ 3 and n odd, and any positive number β 23 smaller than this upper bound: 2 β< (44) n+1 we can construct an example of a scattered Nash equilibrium, such that the payoff of some player exceeds β in that equilibrium. Thus, [2/(n + 1)] is not just an upper bound, it is the least upper bound of the payoff of the players in a Nash equilibrium, for n ≥ 3 and n odd. Unlike the result for the lower bound, we do not claim that the bound [2/(n + 1)] is actually attained in a Nash equilibrium for n ≥ 3 with n odd. This is principally because we work with scattered Nash equilibrium, for which there is a complete characterization provided by Theorem 1. The partial characterization result (in Proposition 2) of all Nash equilibria (scattered and clustered) does not provide us with a sufficient condition to check whether a proposed placement is a Nash equilibrium. It is certainly possible that the least upper bound [2/(n + 1)] is actually attained in a clustered Nash equilibrium, but we have not pursued this issue. [For n = 3, this least upper bound is attained in a clustered Nash equilibrium, as we checked in Example 2.] Example 4: The Result for n Odd Let n ≥ 3 be given, with n odd. Then (n + 1) is even, and N = (n + 1)/2 is an integer, greater than or equal to 2. Let β be any positive number satisfying (44). Denote: µ ¶ 2 2 ε≡ − β ∈ 0, (45) n+1 n+1 Divide the circumference of the circle into N equal parts. This will generate N points on the circle, equally spaced. Place the platform s1 at any one of the N points. Place s3 at the next available point (of the remaining N − 1 points) as you go clockwise around the circle, starting from s1 . Continue similarly with s5 , ..., sn . Notice that only the odd numbered platforms have been located at these N points. For example, with n = 5, we will have N = 3, and this procedure will place platforms s1 , s3 , and s5 at the N = 3 available points, moving clockwise from s1 to s3 and then clockwise from s3 to s5 . Observe that: 1 2 arc(s1 , s3 ) = · · · = arc(sn−2 , sn ) = arc(sn , s1 ) = = (46) N n+1 For an illustration of this procedure for n = 5, see Figure 7. We now proceed to place the even numbered platforms as follows. Place s2 in arc(s1 , s3 ) so that arc(s2 , s3 ) = ε. Since: 2 1 ε< = = arc(s1 , s3 ) n+1 N this is certainly possible. Similarly, place sk in arc(sk−1 , sk+1 ) with arc(sk , sk+1 ) = ε for all k ∈ {2, 4, ..., n − 1}. See the figure again for an illustration of this procedure for n = 5. It is now easy to check that: yj (s) = (1/N ) for all j ∈ {2, 3, ...., n − 1} (47) Further, we have: yn (s) = (1/N ) + ε; y1 (s) = (2/N ) − ε (48) Using (45),(47) and (48), the neighborhood with the smallest arc length is: 1 y (s) = (49) N 24 Figure 7: Upper Bound of DOP (Example 4) The largest empty stretch is: 1 x(s) = a(sn , s1 ) = (50) N Thus, by Theorem 1, the placement s = {s1 , ..., sn } described above is a Nash equilibrium. Using (48), the payoff of player 1 in this Nash equilibrium is: y1 (s) 1 ε 2 ε 2 p1 (s) = = − = − > −ε=β (51) 2 N 2 n+1 2 n+1 This shows that [2/(n + 1)] is the least upper bound of the payoff of the players in a Nash equilibrium, for n ≥ 3 and n odd. Example 5: The Result for n Even For n ≥ 3 and n even, the upper bound in (DOP’) is not necessarily a least upper bound of the payoff of the players in a Nash equilibrium. For instance, with n = 4, it can be shown that an upper bound of the payoff of the players in any scattered Nash equilibrium is equal to: 1 2 2 2 = < = (52) 3 n+2 n+1 5 To see this, we proceed as follows. With n = 4, let s = {s1 , s2 , s3 , s4 } be an arbitrary scattered Nash equilibrium. Recall that the arc length of the empty stretch of maximum arc length is denoted by x(s), 25 and we define: y (s) = min{y1 (s), ..., y4 (s)}; z (s) = max{y1 (s), ..., y4 (s)} There is k ∈ I = {1, ..., 4} such that yk (s) = z (s). Note that by Theorem 1, we have: z (s) = yk (s) ≤ 2x(s) ≤ 2y (s) (53) Without loss of generality, we can take k = 1. The neighborhood Y1 (s) defines sj and sq with sj = 6 sq such that: Y1 (s) = arc(sj , sq ) (54) Again without loss of generality, we can take j = 2 and q = 3. It then follows that s4 belongs to the arc arc(sq , sj ) = arc(s3 , s2 ). Thus, Y4 (s) = arc(s3 , s2 ) (55) See Figure 8 for an illustration of the locations s1 , s2 , s3 , and s4 . Figure 8: Upper Bound of DOP for n = 4 (Example 5) The neighborhood Y1 (s) consists of two empty stretches (and the point s1 ), arc(s2 , s1 ) and arc(s1 , s3 ).The corresponding arc lengths can be written as [y1 (s)/2]+ε and [y1 (s)/2]−ε respectively, where − [y1 (s)/2] < ε < [y1 (s)/2] . Similarly, the neighborhood Y4 (s) consists of two empty stretches (and the point s4 ), arc(s3 , s4 ) and arc(s4 , s2 ). The corresponding arc lengths can be written as [y4 (s)/2]+ η and [y4 (s)/2] − η respectively, where − [y4 (s)/2] < η < [y4 (s)/2] . Note that ε and η are being allowed to be either negative or positive or zero. [In Figure 8, ε = 0 while η < 0.] 26 With this notation we have: y2 (s) = a(s4 , s2 ) + a(s2 , s1 ) = [y4 (s)/2] − η + [y1 (s)/2] + ε (56) and: y3 (s) = a(s1 , s3 ) + a(s3 , s4 ) = [y1 (s)/2] − ε + [y4 (s)/2] + η (57) Using (56) and (57), we can now write: 2 = y1 (s) + y2 (s) + y3 (s) + y4 (s) = y1 (s) + {[y4 (s)/2] − η + [y1 (s)/2] + ε} + {[y1 (s)/2] − ε + [y4 (s)/2] + η } + y4 (s) = 2y1 (s) + 2y4 (s) ≥ 2z (s) + 2y (s) ≥ 2z (s) + z (s) = 3z (s) (58) where we have used (43) in the last but one line of (58). Thus, we obtain: 2 z (s) ≤ (59) 3 and so: yi (s) z (s) 1 pi (s) = ≤ ≤ for all i ∈ I = {1, 2, 3, 4} (60) 2 2 3 5 Concluding Remarks This paper was an exercise in abstract geometric reasoning. When drawing on it for more applied models, it will be important to add relevant complications. In applying it to retail trading and location choice or brand proliferation, it will be important to introduce the option to vary prices (Basu, 1993, Chapter 8). When applying it to electoral politics, we need to account for the fact that candidates typically come with a prior record of ideology and a sharp shift in this can cause voter dissonance. In all these models there may also be a case for considering sequential moves, which would convert this into an extensive-form game. It is hoped that the simple model presented here can be of value for such extensions. 6 Appendix 6.1 Proof of Claim (5) in Section 3 Since k 6= j, the definition of s0 implies that s0 0 0 0 k = sk ∈ Yk (s). If there is some sr in Yk (s) with sr 6= sk , 0 0 then r 6= k, j, and so by definition of s , sr = sr must hold. In this case, we have sr in Yk (s) with sr 6= sk , a contradiction to the definition of Yk (s). This establishes that there is no s0 r in Yk (s) with s0 r 6 = s0 . Since Y (s) is a connected set containing s0 , and there is no s0 in Y (s) with s0 6= s0 , we must k k k r k r k have Yk (s) ⊂ Yk (s0 ), and consequently Y ¯k (s) ⊂ Y¯k (s0 ) as well. Using (NBD), let us write Yk (s) = arc(sL(k) , sR(k) ) ≡ arc(sp , sq ). Note that sL(k) 6= sk , and sR(k) 6= sk , and sL(k) 6= sR(k) . Now, if sL(k) = sj , then since sL(k) ∈ Y ¯k (s) and sj ∈ Yj (s), we would have ¯k (s) ∩ Yj (s) 6= φ, a contradiction to the definition of Case (b)(I). Thus, we must have sL(k) 6= sj , and Y similarly sR(k) 6= sj . By definition of s0 it follows that s0 0 p = sp and sq = sq . 27 Both sp and sq belong to Y ¯k (s), and since Y ¯k (s0 ), they belong to Y ¯k (s) ⊂ Y ¯k (s0 ). However, they ¯ 0 0 cannot be interior points of Yk (s ); that is, they cannot belong to Yk (s ). To see this, note that sp 6= sk , sp = s0 0 0 0 0 0 p and sk = sk , and so sp 6= sk . Then, by definition of Yk (s ), we infer that sp cannot be in Yk (s ); 0 0 that is, sp cannot be in Yk (s ). A similar reasoning establishes that sq cannot be an interior point of ¯k (s0 ). Thus, both are boundary points of Y Y ¯k (s0 ). This means that Y ¯k (s0 ) is either the set arc[sp , sq ] ¯ 0 or the set arc[sq , sp ]. Since Yk (s) = arc(sp , sq ), and Yk (s ) has to contain the set Y ¯k (s) = arc[sp , sq ], ¯ 0 0 we conclude that Yk (s ) must be the set arc[sp , sq ]. Thus, Yk (s ) must be the set arc(sp , sq ), and so Yk (s) = Yk (s0 ). 6.2 Proof of Claim (8) in Section 3 We break up our analysis into two cases: (A1) sL(j ) = sR(k) and (A2) sL(j ) 6= sR(k) . Case (A1): In this case, sj belongs to arc(sR(k) , sL(k) ]. If sj actually belongs to arc(sR(k) , sL(k) ), then Yj (s) = arc(sR(k) , sL(k) ), which is disjoint from Y ¯k (s), contradicting the fact that Yj (s) ∩ Y ¯k (s) 6= φ in subcase (b)(II). Thus, sj = sL(k) , and so sk = sR(j ) , so that (8)(i) in claim (8) holds. Case (A2): We subdivide our analysis into the following two possibilities (A2a) sL(j ) ∈ Y ¯k (s), (A2b) sL(j ) ∈ /Y ¯k (s). In subcase (A2a), sL(j ) must be equal to sL(k) or sk or sR(k) . The last possibility is ruled out since in (A2) we have sL(j ) 6= sR(k) . If sL(j ) = sL(k) , then sj must be equal to sk , which is ruled out since s is a scattered placement (recall that k 6= j in Case (b)). Thus, we must have sL(j ) = sk and consequently sj = sR(k) . That is, (8)(ii) in claim (8) holds. In subcase (A2b), sL(j ) ∈ arc(sR(k) , sL(k) ), and consequently sR(j ) ∈ / arc(sR(k) , sL(k) ). This is because if sR(j ) ∈ arc(sR(k) , sL(k) ), then Yj (s) is entirely contained in arc(sR(k) , sL(k) ), which is disjoint from Y¯k (s), contradicting the fact that Yj (s) ∩ Y ¯k (s) 6= φ in subcase (b)(II). Since sR(j ) ∈/ arc(sR(k) , sL(k) ), we must have sR(j ) ∈ Y ¯k (s) ≡ arc[sL(k) , sR(k) ]. Thus, sR(j ) must be equal to sL(k) or sk or sR(k) . The first possibility is ruled out since sR(j ) = sL(k) would imply that Yj (s) ∩ Y¯k (s) = φ, a contradiction. The third possibility is ruled out because sR(j ) = sR(k) would imply that sj must be equal to sk , which is ruled out since s is a scattered placement (recall that k 6= j in Case (b)). Thus, we must have sR(j ) = sk and consequently sj = sL(k) , so that (8)(i) in claim (8) holds. 28 References [1] Acemoglu, D. and Robinson, J. A. (2005). Economic Origins of Dictatorship and Democracy. Cambridge University Press. [2] Basu, K. (1993). Lectures in Industrial Organization Theory. Blackwell. [3] Black, D. (1948). On the Rationale of Group Decision-making, Journal of Political Economy, 56(1), 23-34. [4] Brander, J. A. and Spencer, B. J. (2015). Endogenous Horizontal Product Differentiation under Bertrand and Cournot Competition: Revisiting the Bertrand Paradox, NBER Working Paper No. 20966. [5] Congleton, R. (2002). The median voter model. in C.K. Rowley and F. Schneider (eds.), The Encyclopedia of Public Choice, Kluwer Academic Press. [6] d’Aspremont, C., Gabszewicz, J. J. and Thisse, J. F. (1979). On Hotelling’s “Stability in Compe- tition”. Econometrica, 1145-1150. [7] Downs, A. (1957). An Economic Theory of Political Action in a Democracy. Journal of Political Economy, 65(2), 135—150. [8] Fujita, M. and Thisse, J.-F (1996). Economics of Agglomeration, Journal of the Japanese and International Economies, 10(4), 339-378. [9] Gabszewicz, J.J., Thisse, J.F., Fujita, M. and Schweizer, U. (1986). Location Theory, Chich- ester:Harwood. [10] Hotelling, H. (1929). Stability in Competition. The Economic Journal, 39(153), 41—57. [11] Matsushima, N. (2001). Cournot Competition and Spatial Agglomeration Revisited, Economics Letters, 73(2), 175—177. [12] Pal, D. (1998), Does Cournot Competition Yield Spatial Agglomeration? Economics Letters, 60(1), 49—53. [13] Salop, S. C. (1979). Monopolistic Competition with Outside Goods. The Bell Journal of Economics, 141-156. [14] Schmalensee, R. (1978). Entry Deterrence in the Ready-To-Eat Breakfast Cereal Industry. The Bell Journal of Economics, 305-327. [15] Stokes, D.E. (1963). Spatial Models of Party Competition, The American Political Science Review, 57(2), 368-377. [16] Osborne, M. J. (1995). Spatial Models of Political Competition under Plurality Rule: A Survey of Some Explanations of the Number of Candidates and the Positions They Take. Canadian Journal of Economics, 261-301. 29