# condorcet_relaxation_in_spatial_voting__2edad372.pdf

Condorcet Relaxation In Spatial Voting

Arnold Filtser, 1 Omrit Filtser 2

1 Columbia University 2 Stony Brook University arnold@filtser.com, omrit@filtser.com

Consider a set of voters V , represented by a multiset in a metric space (X, d). The voters have to reach a decision - a point in X. A choice p X is called a β-plurality point for V , if for any other choice q X it holds that |{v V | β d(p, v) d(q, v)}| |V |

2 . In other words, at least half of the voters prefer p over q, when an extra factor of β is taken in favor of p. For β = 1, this is equivalent to Condorcet winner, which rarely exists. The concept of β-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [So CG 2020] as a relaxation of the Condorcet criterion. Denote by β (X,d) the value sup{β | every finite multiset V in X admits a β-plurality point}. The parameter β determines the amount of relaxation required in order to reach a stable decision. Aronov et al. showed that for the Euclidean plane β (R2, 2) =

3 2 , and more generally, for d-

dimensional Euclidean space, 1

d β (Rd, 2)

3 2 . In this paper, we show that 0.557 β (Rd, 2) for any dimension d (notice that 1

d < 0.557 for any d 4). In addition, we prove that for every metric space (X, d) it holds that

2 1 β (X,d), and show that there exists a metric space for which β (X,d) 1

Introduction

When a group of agents wants to reach a joint decision, it is often natural to embed their preferences in some metric space. The preferences of each agent are represented by a metric point (also referred to as a voter). Each point in the metric space is a potential choice, where an agent/voter prefers choices closer to its point over farther choices. The goal is to reach a stable decision, in the sense that no alternative choice is preferred by a majority of the voters. Such a decision is often referred to as a Condorcet winner. More formally, consider a metric space (X, d), and a finite multiset of points V from X, called voters. A voter v prefers a choice p X over a choice q X if d(p, v) < d(q, v). Specifically, a choice point p X is a plurality point if for any other choice point q X, the number of voters preferring p over q is at least the number of voters

Copyright 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

preferring q over p, i.e., |{v V | d(p, v) < d(q, v)}| |{v V | d(p, v) > d(q, v)}|. 1

The special case where (X, d) is the Euclidean space, i.e., (Rd, 2), is called spatial voting games, and was studied in the political economy context (Black 1948; Downs 1957; Plott 1967; Enelow and Hinich 1983). When X = R is the real line, a plurality point always exists, in fact, it is simply the median of V . When (X, d) is induced by the shortest path metric of a tree graph, then again a plurality point always exists, as any separator vertex 2 is a plurality point. However, already in R2 a plurality point does not always exist, and moreover, it exists only for a negligible portion of the point sets. Indeed, for any d 2, a plurality point for a multiset V in Rd exists if and only if all median hyperplanes 3 for V have a common intersection point (see (Enelow and Hinich 1983; Plott 1967)). Wu et al. (2014) and de Berg et al. (2018) presented algorithms that determine whether such a point exist. Recently, Aronov, de Berg, Gudmundsson, and Horton (2020), introduced a relaxation for the concept of plurality points, by defining a point p X to be a β-plurality point, for β (0, 1], if for every other point q X, |{v V | β d(p, v) < d(q, v)}| |{v V | β d(p, v) > d(q, v)}|. In other words, if we scale distances towards p by a factor of β, then for every choice point q, the number of voters preferring p over q is at least the number of voters preferring q over p. Set

β(X,d)(p, V ) = sup{β | p is a β-plurality point in X w.r.t. V },

β(X,d)(V ) = sup p X {β(X,d)(p, V )},

β (X,d) = inf{β(X,d)(V ) | V is a multiset in X} .

1A more accurate name for such a point, which is also used in the literature, is Condorcet winner. However, as this work is mainly concerned with the term β-plurality point defined in (Aronov et al. 2020), we choose to keep their terminology. 2If T is the tree inducing (X, d), a separator vertex is a vertex z X, the removal of which will break the graph T \ {z} into connected components, each containing at most |V |

2 voters. Every tree contains a separator vertex (Jordan 1869). 3A median hyperplane for V is a hyperplane such that both open half-spaces defined by it contain less than |V |

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Space Lower Bound Upper Bound Ref

R and tree metric 1 1 (R2, 2)

3/2 (Aronov et al. 2020) (R3, 2) 1/

3/2 (Aronov et al. 2020) (Rd, 2) for d 4 0.557

3/2 Theorem 4, (Aronov et al. 2020) General metric space

2 1 0.414 1/2 Theorem 1, Theorem 2

Table 1: Summary of the state of the art results on β X for different metric spaces.

Intuitively, β(X,d)(p, V ) is the maximum value β such that p is a β-plurality point, β(X,d)(V ) is the maximum value β such that there exist a β-plurality point in (X, d) w.r.t. the voter set V , and β (X,d) is the maximum value β such that for every voter set V , a β-plurality point is guaranteed to exist. A natural question is to find or estimate these parameters for a given metric space. Notice that as β becomes larger, we are closer to having a plurality point. Therefore, it is interesting to know what values of β we can anticipate for a given metric space in order to reach a stable decision. These bounds give an indication on the amount of relaxation that might be needed, and how reasonable it is. Aronov et al. (2020) studied β-plurality for the case of Euclidean space, i.e., (Rd, 2). Given a specific instance V , they presented an EPTAS to approximate β(Rd, 2)(V ). For the case of the Euclidean plane (d = 2), they showed that β (R2, 2) =

3 2 . Specifically, they showed that for every multiset of voters V in R2, there exists a point p R2 such that β(R2, 2)(V, p)

3 2 . Furthermore, they showed that for the case where V consist of the three vertices of an equilateral triangle, it holds that β(R2, 2)(V )

3 2 . For the general d-dimensional Euclidean space (Rd, 2), Aronov et al. showed a lower bound of β (R2, 2)(V ) 1

d. They left as a main open problem the question of closing the gap between 1

3 2 , and asked what bound on β could be proven in other metric spaces.

Our contribution. We prove that for every metric space (X, d), β (X,d)

2 1. Note that Aronov et al. (2020) gave a lower bound of 1

d for the Euclidean metric, while our result shows a constant lower bound for any metric space. In addition, we provide an example of a metric space (X, d) for which β (X,d) = 1

2. In fact, we show that β (X,d) = 1

2 for any (continuous) graph metric (X, d) that contains a cycle (in contrast to tree metrics, for which β (X,d) = 1). Finally, for the case of Euclidean space of arbitrary dimension d, we show that β (Rd, 2) 0.557. Note that this lower bound is larger than 1

d for d 4. All the current and previous results are summarized in Table 1.

Related work A well known relaxation for the concept of plurality points in Euclidean space is the yolk (Mc Kelvey

1986; Miller, Grofman, and Feld 1989; Feld, Grofman, and Miller 1988; Gudmundsson and Wong 2019; Miller 2015), which is the smallest ball intersecting every median hyperplane 3 of V . The center of the yolk is a good heuristic for a plurality point (see (Miller and Godfrey 2008) for a list of properties the yolk possesses). Notice that the definition of β-plurality applies for any metric space, not necessarily Euclidean as in the concept of yolk. Another relaxation studied by Lin et al. (2015) is the minimum cost plurality problem . Here given a set of voters V with some cost function, the goal is to find a set W of minimum cost such that V \ W contains a plurality point. A main drawback of the spatial voting model in the realistic political context was underlined by Stokes (1963). The claim is that this model does not take into account the so-called valence issues : qualities of the candidates such as charisma and competence (Evrenk et al. 2018), a strong party support (Wiseman 2006), and even the campaign spending (Herrera, Levine, and Martinelli 2008). Therefore, several more realistic models have been proposed (see, e.g., (Giansiracusa and Ricciardi 2019; Gouret, Hollard, and Rossignol 2011; Sanders et al. 2011)). A common model is the multiplicative model which was introduced by Hollard and Rossignol (2008), and is defined for two-candidate spatial voting model. This model is closely related to the concept of β-plurality, and is similar to it in the case of a two-player game.

General Metric Spaces We begin by providing an alternative definition of βplurality point.

Definition 1. Consider a metric space (X, d), and a multiset V in X of voters. A point p X is a β-plurality point if for every q X, |{v V | β d(p, v) d(q, v)}| |V |

2 . In addition, similarly to (Aronov et al. 2020), set β(X,d)(V ) = supp X β(X,d)(p, V ) and

β (X,d) = inf{β(X,d)(V ) | V is a multiset in X} .

The difference between the definitions is that Definition 1 is deciding ties in favor of p, that is a voter v for which β d(p, v) = d(q, v), will choose p over q, while in the original definition, such voters remain undecided . Definition 1 is equivalent to the original definition in (Aronov et al. 2020). See Lemma 8 in the Missing proofs section for an exact statement and proof.

Consider a metric space (X, d), with a multiset V of voters from X, and set |V | = n. For a point p and radius r, denote by BV (p, r) = {v V | d(p, v) r} the (multi) subset of voters at distance at most r from p (i.e., those that are contained in the closed ball of radius r centered at p), and let Rp be the minimum radius such that |BV (p, Rp)| n

2 . The following theorem shows that a (

2 1)-plurality point always exists. The fact that the lower bound is constant, and even close to 1

2, demonstrates the strength of βplurality in the sense that for any set of voters and in any metric space, the multiplication factor needed for the existence of such winner is a fixed constant, and thus the amount of relaxation is bounded.

Theorem 1. For every metric space (X, d), it hold that β (X,d)

Proof. Let p X be a point with minimum Rp over all p X, and denote Bp = BV (p , Rp ). We claim that p

2 1)-plurality point.

2 1, and notice that β = 1 2+β . Consider some choice point q X, and set d(p , q) = (1 + α) Rp , for α 1. Let Bq = {v V | d(q, v) < Rq} be the (multi) subset of voters at distance (strictly) smaller than Rq from q (i.e., those that are contained in the open ball of radius Rq centered at q). Consider the following cases:

α β: For every point v / Bq, as d(q, v) Rq Rp , by the triangle inequality it holds that

d(p , v) d(p , q) + d(q, v) (2 + α) d(q, v)

(2 + β) d(q, v) = 1

β d(q, v) .

α β: For every point v Bp , as d(p , q) = (1 + α) Rp (1 + α) d(p , v), it holds that

d(q, v) d(q, p ) d(p , v) (1 + α 1) d(p , v) β d(p , v) .

The theorem follows as | Bq| < n

Theorem 2. There exists a metric space (X, d) such that β (X,d) = 1

Proof. Consider a continuous cycle C of length 1, we will think of C as a one dimensional space. Formally, X is the

segment [0, 1), and given two points x, y [0, 1), their distance is d(x, y) = min{(x y)mod 1, (y x)mod 1}. First we show that β (X,d) 1 2. Consider a set of three voters {v1, v2, v3} = {0, 1

3}, all at distance 1

3 from each other. We will show that β (X,d)(V ) 1

2. Assume by contradiction that there is a choice p which is a β-plurality point for β > 1 2. Assume w.l.o.g. that p = α [0, 1

6] (see the figure above for illustration), the other cases are symmetric.

Consider the choice point q = 1 2 α

2 lying on the arc [v2, v3] at distance 1

2 from v2, and 1

2 from v3. Then β d(p, v2) = β ( 1

2 = d(q, v2) and β d(p, v3) = β ( 1

2 = d(q, v3), which contradicts the assumption that p is a β-plurality point. Next we show that β (X,d) 1 2. Consider an arbitrary (multi) subset of voters V X, and let p X be a choice with minimal radius Rp such that |BV (p, Rp)| n

2 . Note that the length of the smallest arc containing n

2 voters is 2Rp. In particular, as either the arc [0, 1

2, 1) contain n 2 voters, 2Rp 1

2, and thus Rp 1

4. Assume w.l.o.g. that p = 0. We show that p is a 1

2-plurality point. Let q X be any other point. We assume that q (0, 1

2], the case q [ 1

2, 1) is symmetric. We say that a voter v prefers q over p if 1

2d(p, v) > d(q, v). It will be enough to show that at most n

2 voters prefer q over p. Let v be a voter that prefer p over q. If v < q then 1

2d(p, v) = 1

2v and d(q, v) = q v, and thus v > 2

3q. Else, if v > q, then 1

2v and d(q, v) = v q (as otherwise the shortest path from v to q goes through p, implying d(p, v) < d(q, v)), and therefore v < 2q. We conclude that only voters in the arc ( 2

3q, 2q) prefer q over p. The rest is case analysis:

2Rp, then the arc containing the set of the voters preferring q over p is of length 4

3q < 2Rp. By the minimality of Rp, it contains less than n

2 voters. If q 3

2Rp, then the arc [0, Rp] is disjoint from the arc ( 2

3q, 2q). Moreover, as q < 1 2, all the voters in the arc [1 Rp, 1) [ 1

4, 1) will prefer p over q. In particular there are at least n

2 voters preferring p over q.

Given a weighted graph G = (V, E, w), denote by G its continuous counterpart. If G contains a cycle, we can generalize Theorem 2 to G. A proof sketch (and definition of

continuous counterpart) is deferred to the Missing proofs section. This shows a separation between metric spaces obtained by acyclic graphs (trees) which always contain a plurality point (that is, β (X,d) = 1), to metric spaces obtained by all other graphs, for which β (X,d) 1

Theorem 3. For every weighted graph G = (V, E, w) containing a cycle, it holds that β ( G,d G) 1

Euclidean Space In this section we consider the case of the Euclidean metric space, and give a bound on β (Rd, 2) which is independent of d and greater than 1

d for any d 4, thus improving the lower bound of (Aronov et al. 2020) for d 4.

Theorem 4. For Euclidean space of arbitrary dimension, β (Rd, 2) β,

3 3 0.5570157181

We begin with a structural observation regarding the Euclidean space. The proof is deferred to the Missing proofs section.

Claim 2. Fix a pair of candidates a, b Rd. For any β (0, 1), the set of all voters v V that do not β-prefer a over b, i.e., n v V | β a v 2 > b v 2 o , is equal to the intersection of V with the open ball centered at o = a + 1 1 β2 ( b a) with radius β o a 2.

By the above claim we can conclude:

Corollary 3. For any β (0, 1), a is a β-plurality point if and only if, for every other point o Rd, the open ball of radius β o a 2 around o contains at most n

For the remainder of the section, β is the number defined in Theorem 4 and not a general parameter.

Proof of Theorem 4. Consider a multiset V Rd of voters. Let p be the point that minimizes R p. By scaling, we can assume w.l.o.g. that R p = 1. If p is a β-plurality point, then we are done. Otherwise, by Corollary 3 there is a point q such that the open ball BRd ( q, β p q 2) contains strictly more than n

2 voters. Denote q = p q 2. Set

w = p + 1 2(1 β2)q β + 3

2q q p q p 2 , we claim that w is a β-plurality point. First, notice that q > 1 β , as otherwise the open ball of radius βq 1 around q contains more than n

2 voters, a contradiction to the fact that R p = 1 is the minimal radius of a closed ball containing at least n

2 voters. Second, it must hold that q < 1 1 β , because otherwise βq + 1 q, implying that the ball BRd( p, R p) and the open ball BRd( q, βq) are disjoint, a contradiction to the fact that the open ball BRd( q, βq) contains more than n

2 voters. Therefore, we conclude that

1 β < q < 1 1 β (1)

Notice that p is a 1

2-plurality point, as no q satisfies eq. (1).

Figure 1: The points p = (0, 0), q = (q, 0), and w = (w, 0) for w = 1

2(1 β2)q β+ 3

2q are on the x-axis. Bp is the circle of radius 2 around p, while Bq is the circle of radius 1 + βq around q. Bp and Bq intersect at i = (w,

4 w2) and i = (w,

4 w2). The ball of radius 1 around i is tangent to both Bp and Bq. It holds that w i 2 =

4 w2 1 β (equation (2)).

To prove that w is a β-plurality point, we will show that for every other point z Rd, the open ball of radius β z w 2 around z contains at most n

2 voters. We will use the following lemma.

Lemma 4. For any point z Rd, denote z = z w 2. Then at least one of the following hold:

β . 2. z p 2 1 + βz. 3. z q 2 βq + βz.

Before proving Lemma 4, we show how it implies that w is a β-plurality point. For any z Rd:

β , then βz 1 = R p, and thus BRd( z, βz) contains at most n

2 voters. If z p 2 1 + βz, then the balls BRd( p, 1) and BRd( z, βz) are disjoint, and thus BRd( z, βz) contains at most n

2 voters. If z q 2 βq + βz, then the balls BRd( q, βq) and BRd( z, βz) are disjoint, and thus BRd( z, βz) contains at most n

We conclude that for every z Rd, BRd( z, z) contains at most n

2 voters, and thus by Corollary 3, w is a β-plurality point.

Proof of Lemma 4. The points p, q, w lie on a single line. Given an additional point z, the four points lie on a single plane. Thus, w.l.o.g. we can restrict the analysis to the Euclidean plane. Moreover, we can assume that p = (0, 0), q = (q, 0), w = (w, 0) for w = 1 2(1 β2)q β + 3 2q,

and that z = (zx, zy) where zy 0 (the case of zy 0 is symmetric). Denote Bp = BR2( p, 2) and Bq = BR2( q, 1 + βq) (see Figure 1). The boundaries of Bp and Bq intersect at the points (w,

4 w2) (this is the reason for our choice of w). Denote i = (w,

4 w2), and notice that 0 < w < q for any q 1

β (this can be verified by straightforward calculations). Lemma 4 follows by the two following claims:

Claim 5. If z Bp Bq then z w 2 1

Claim 6. If z / Bp Bq then either z p 2 1 + βz or z q 2 βq + βz.

Proof of Claim 5. The boundaries of Bp and Bq intersect at the points i = (w,

4 w2) and i = (w,

4 w2). For every q ( 1

β , 1 1 β ), it holds that

In fact, β was chosen to be the maximum number satisfying equation (2). A calculation showing that equation (2) holds is deferred to the Missing proofs section. Consider the ball Bw = BR2( w, i w 2). Bw has radius at most 1

β , and the

segment [ i, i ] is a diameter of Bw. Furthermore, [ i, i ] is a chord in both Bp and Bq. Assume that z = (zx, zy) Bp Bq. If zx w, then the chord [ i, i ] of Bp separates the point z from the center p, because 0 < w < q (see illustration below).

It follows that the angle i z i is larger than π

2 , which implies that z Bw (as [ i, i ] is a diameter, for any point z / Bw, the angle i z i is smaller than π

2 ). If the zx < w, a symmetric argument (using Bq) will imply that z Bw. We conclude that in any case z Bw. By equation (2), it follows that z w 2 1

Proof of Claim 6. Assume that z = (zx, zy) / Bp Bq. We show that if zx w then z p 2 1 + βz, and otherwise z q 2 βq + βz. First, consider the case when zx w. Notice that z / Bp, because the boundaries of Bp and Bq intersect only at i, i , and thus the intersection of Bp with the half plane x w is contained in Bq. Let z = (z x, z y) be a point on the ball

with radius z p 2 around p such that z x = w and z y 0, and notice that z y zy (see illustration below).

Notice that z w 2 z w 2, because z2 x + z2 y = z p 2 2 = z p 2 2 = w2 + z y 2 and zx w, so we get z w 2 2 = z2 y + (zx w)2 = z2 y + z2 x 2wzx + w2 = 2w2 2wzx + z y 2 z y 2 = z w 2 2. Since z p 2 = z p 2, it is enough to show that z p 2 1+β z w 2. From here on, we will abuse notation and refer to z as z. Thus we simply assume z = (w, z). As Bp and Bq intersect at i, and z / Bp Bq, it must hold that z

4 w2. Note that p i 2 = 2 (because i is on the boundary of Bp), and by equation (2), β i w 2 1. It thus follows that 1+β w i 2 2 = p i 2, implying that the claim holds for z = i. It remains to prove that the claim holds for z = (w,

4 w2 +δ) for all δ 0. It holds that

z p 2 2 = w2 + ( p

= i p 2 2 + 2δ p

4 w2 + δ2 .

(1 + β z w 2)2

= 1 + β i w 2 + β z i 2 2

= 1 + β i w 2 2 + 2β z i 2 1 + β i w 2

+ β2 z i 2 2

= 1 + β i w 2 2 + 2βδ 1 + β p

4 w2 + β2δ2 .

As 1 + β w i 2 p i 2, it holds that

z p 2 2 (1 + β z w 2)2

2βδ 1 + β p

4 w2 + β2δ2

4 w2 1 β2 + δ2(1 β2) 2βδ 0 ,

where the last inequality holds as by our choice of β,

4 w2 1 β2 β for every 1

β < q < 1 1 β . The claim follows. Next, we show that in the symmetric case, when zx w, it holds that z q 2 βq + βz. Similarly to the previous case, we can assume that z = (w, z), where z

(as this is only harder). Now, as i lies on the boundary of Bq, by equation (2), it holds that i q 2 = 1 + βq β w i 2 + βq. It remains to prove that the claim holds for z = (w,

4 w2 + δ) for some δ > 0. It holds that

z q 2 2 = (q w)2 + ( p

= i q 2 2 + 2δ p

4 w2 + δ2 .

(βq + β z w 2)2

= βq + β i w 2 + β z i 2 2

= βq + β i w 2 2

+ 2β z i 2 βq + β i w 2 + β2 z i 2 2

βq + β i w 2 2

+ 2βδ βq + β p

4 w2 + β2δ2 .

Thus, z q 2 2 (βq + β z w 2)2

4 w2 + δ2 2βδ βq + β p

4 w2 1 β2 + δ2(1 β2) 2β2qδ 0 , where the last inequality holds as by our choice of β,

4 w2 1 β2 β2q for every 1

β < q < 1 1 β . The claim follows. Remark 7. A natural extension of the algorithm in Theorem 4 will be to allow another step. Specifically, to choose β > β so that Lemma 4 will not hold w.r.t. β . Then, in case w is not a β -plurality point, there is a point z such that the ball BRd( z, β z w 2) contains more than n 2 voter points. Then, one might hope to find a new candidate point w2 that will be a β -plurality point. Here a natural choice of w2 will be the center of the minimal ball containing the intersection of the three balls Bp = BRd( p, 2), Bq = BRd( q, β q p 2 +1), and Bz = BRd( z, β z w 2 +1). See illustration below. Even though it is indeed possible that this approach will provide some improvement, it is unlikely to be significant. The reason is that even for the simplest symmetric case where

β , 0), z = ( 1

β ), one need β q

89 256 0.59. For the hardest case, it is likely that a much smaller β will be required.

Missing Proofs Equivalence Between the Definitions of β-Plurality Lemma 8. Definition 1 for β(p, V ) is equivalent to the definition from Aronov et al. (2020). Specifically, for a met-

ric space (X, d), voter multiset V and point p X, denote by β(p, V ) the value defined in (Aronov et al. 2020), and by β(p, V ) the value from Definition 1. It holds that β(p, V ) = β(p, V ) (note that the equivalence of the parameters β(X,d) and β (X,d) follows).

Proof. Fix |V | = n. There are two directions for the proof:

β(p, V ) β(p, V ). Assume by contradiction that β(p, V ) < β(p, V ). By the definition of β(p, V ), there exists α, β(p, V ) < α β(p, V ) such that for every q X, |{v V | α d(p, v) < d(q, v)}| |{v V | α d(p, v) > d(q, v)}|, implying |{v | α d(p, v) d(q, v)}| n 2 . Thus β(p, V ) α, a contradiction. β(p, V ) β(p, V ). Assume by contradiction that β(p, V ) < β(p, V ), and let ϵ > 0 such that β(p, V ) + ϵ < β(p, V ). By definition of β(p, V ), there is an α β(p, V ) + ϵ such that for every q, |{v V | α d(p, v) d(q, v)}| n 2 . Let α = α ϵ 2 (β(p, V ), α). Then for every q = p, |{v V | α d(p, v) < d(q, v)}| |{v V | α d(p, v) d(q, v)}| n 2 , implying |{v V | α d(p, v) < d(q, v)}| |{v V | α d(p, v) > d(q, v)}|. Clearly, for q = p, |{v V | α d(p, v) < d(q, v)}| |{v V | α d(p, v) > d(q, v)}|. It follows that p is an α -plurality point, a contradiction.

Proof of Theorem 3 We begin by defining the continuous counterpart G of a weighted graph G = (V, E, w). Each edge e = (v, u) in G is represented in G by a an interval of length w(e) equipped with the line metric with endpoints u, v. d G is then the natural induced metric. That is, the distance between two points u, v G denoted d G(u, v), is the shortest length of a geodesic path connecting u to v. We restate Theorem 3:

Theorem 3. For every weighted graph G = (V, E, w) containing a cycle, it holds that β ( G,d G) 1

Proof. Let C be a cycle in G of shortest length. Assume w.l.o.g. that the length of C is 3. We place 3 voters v1, v2, v3 on C at unit distance from each other. Assume by contradiction that there is a choice p which is a β-plurality point for β > 1

2. Farther, assume w.l.o.g. that v1 is the voter closest to p, and denote d G(p, v1) = α.

If p lies on the cycle C, then the same argument as in Theorem 2 will imply a contradiction to the assumption that p is a β-plurality point. Else, if v1 lies on the shortest paths from p to both v2, v3, then d G(p, v2), d G(p, v3) 1. Consider the choice q lying at distance 1 2 from both v2, v3. Then as max{d G(q, v2), d G(q, v3)} = 1 2 < β min{d G(p, v2), d G(p, v3)}, q will win two votes over p, a contradiction. Else, suppose w.l.o.g. that the shortest path from p to v2 does not pass though v1. Necessarily d G(p, v2) 2 α, as otherwise v1, p, v2 will be a cycle in G of length strictly less than 3, a contradiction to the minimality of C. Let q be the point lying on the shortest path from v1 to v2 at distance α

2 from v1 and 1 α

2 from v2. Note that q wins both the votes of v1 and v2 over p, a contradiction.

Proof of Claim 2

Proof. By translation and rotation, we can assume w.l.o.g. that a = 0, and b = a b 2 e1 (e1 here is the first standard basis vector). A straightforward calculation shows that

n x Rd | β a x 2 > b x 2 o

x Rd | x1 a b 2 2

i=2 x2 i < β2

x Rd | 1 β2 x2 1 2x1 a b 2 + a b 2 2

i=2 x2 i < 0

i=2 x2 i < β2 a b 2 2 (1 β2)2

Thus we indeed obtain a ball with center at o = a b 2

e1 = a + 1 1 β2 ( a b), and radius r =

β2 a b 2 2 (1 β2)2 =

Proof of Equation (2)

f(β, q) = i w 2 2 = 4 w2

2(1 β2)q β + 3

We show that for our choice of β, q ( 1

β , 1 1 β ), it holds

β , thus proving equation (2).

qf(β, q) = 2 1 2(1 β2)q β + 3

2q 1 2(1 β2) 3 2q2

which equals to 0 only for q q

As we restrict our attention to q ( 1

β , 1 1 β ), it follows

that once we fixed β, f(β, q) has a maximum at q

(note that q

b, 1 1 b) for every b ( 1

2, 1)). It thus will be enough to prove that

f(β, q) f β, r 3 1 β2

= 1 + 2β2 + 2

This expression could be massaged into a degree 4 polynomial. Thus we can obtain an exact solution. In partic-

ular, for every β 0, 1

(0, 0.557], it holds that p

β , as required.

Denote β = inf n β (X,d) | (X, d) is a metric space o . In

this paper we showed that

2 1 β 1 2. Further, in the Euclidean case, for arbitrary dimension d 4, by combining our results with (Aronov et al. 2020), we know that 0.557 < β (Rd, 2)

3 2 . The main question left open is closing these two gaps. Our conjecture is that the upper bounds are tight, since when |V | = 3, a plurality point must win 2

3 of the overall vote. This task can only become easier once the number of voters increases.

Conjecture 1. β = 1

2, and for every d 2,

β (Rd, 2) =

If indeed β (Rd, 2) =

3 2 0.866 for every dimension d, then it implies that the concept of β-plurality might be very useful as a relaxation for Condorcet winner. Informally, it shows that the amount of compromise that we need to make in order to find a plurality point in any Euclidean space is relatively small.

Acknowledgments

After sharing our proof of Theorem 1 with the authors of (Aronov et al. 2020), Mark de Berg proved a weaker version of Theorem 4, and generously allowed us to publish our proof which is based on his observation. Specifically, de Berg proved that β (Rd, 2) 1

The authors would also like to thank Boris Aronov and Nimrod Talmon for providing useful comments on the manuscript.

Funding. Work by Arnold Filtser was supported by the Simons Foundation. Work by Omrit Filtser was supported by the Eric and Wendy Schmidt Fund for Strategic Innovation, by the Council for Higher Education of Israel, and by Ben Gurion University of the Negev.

Aronov, B.; de Berg, M.; Gudmundsson, J.; and Horton, M. 2020. On β-Plurality Points in Spatial Voting Games. In 36th International Symposium on Computational Geometry, So CG 2020, June 23-26, 2020, Z urich, Switzerland, 7:1 7:15. doi:10.4230/LIPIcs.So CG.2020.7. URL https: //doi.org/10.4230/LIPIcs.So CG.2020.7.

Black, D. 1948. On the rationale of group decision-making. Journal of political economy 56(1): 23 34.

de Berg, M.; Gudmundsson, J.; and Mehr, M. 2018. Faster Algorithms for Computing Plurality Points. ACM Trans. Algorithms 14(3): 36:1 36:23. doi:10.1145/3186990. URL https://doi.org/10.1145/3186990. Prliminary version appeared in the proceedings of SOCG 16.

Downs, A. 1957. An economic theory of political action in a democracy. Journal of political economy 65(2): 135 150.

Enelow, J.; and Hinich, M. 1983. On Plott s pairwise symmetry condition for majority rule equilibrium. Public Choice 40(3): 317 321. URL http://www.la.utexas.edu/ hinich/files/Politics/Plott s%20Condition.pdf.

Evrenk, H.; Congleton, R.; Grofman, B.; and Voigt, S. 2018. Valence politics. The Oxford Handbook of Public Choice, Volume 1 266.

Feld, S. L.; Grofman, B.; and Miller, N. 1988. Centripetal Forces in Spatial Voting: On the Size of the Yolk. Public Choice 59(1): 37 50. ISSN 00485829, 15737101. doi:10.1007/BF00119448. URL http://www.jstor.org/stable/ 30024944.

Giansiracusa, N.; and Ricciardi, C. 2019. Computational geometry and the US Supreme Court. Mathematical Social Sciences 98: 1 9.

Gouret, F.; Hollard, G.; and Rossignol, S. 2011. An empirical analysis of valence in electoral competition. Social Choice and Welfare 37(2): 309 340.

4Following the lines of the proof of Theorem 4, for β = 1

2, p is a 1

2-plurality point, as no q satisfies equation (1).

Gudmundsson, J.; and Wong, S. 2019. Computing the Yolk in Spatial Voting Games without Computing Median Lines. In The Thirty-Third AAAI Conference on Artificial Intelligence, 2012 2019. doi:10.1609/aaai.v33i01.33012012. URL https://doi.org/10.1609/aaai.v33i01.33012012. Herrera, H.; Levine, D. K.; and Martinelli, C. 2008. Policy platforms, campaign spending and voter participation. Journal of Public Economics 92(3-4): 501 513. Hollard, G.; and Rossignol, S. 2008. An alternative approach to valence advantage in spatial competition. Journal of Public Economic Theory 10(3): 441 454. Jordan, C. 1869. Sur les assemblages de lignes. Journal f ur die reine und angewandte mathematik 70: 185 190. Lin, W.; Wu, Y.; Wang, H.; and Chao, K. 2015. Forming Plurality at Minimum Cost. In WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, 77 88. doi:10.1007/978-3-319-15612-5\ 8. URL https://doi.org/10.1007/978-3-319-15612-5\ 8. Mc Kelvey, R. D. 1986. Covering, Dominance, and Institution-Free Properties of Social Choice. American Journal of Political Science 30(2): 283 314. ISSN 00925853, 15405907. URL http://www.jstor.org/stable/2111098. Miller, N. R. 2015. The spatial model of social choice and voting. In Heckelman, J. C.; and Miller, N. R., eds., Handbook of Social Choice and Voting, Chapters, chapter 10, 163 181. Edward Elgar Publishing. URL https: //ideas.repec.org/h/elg/eechap/15584 10.html. Miller, N. R.; and Godfrey, J. 2008. On the size and location of the yolk in spatial voting games: results using cybersenate software. URL https://userpages.umbc.edu/ nmiller/RESEARCH/PAPER.PCS09.pdf. Unpublished. Miller, N. R.; Grofman, B.; and Feld, S. L. 1989. The Geometry of Majority Rule. Journal of Theoretical Politics 1(4): 379 406. doi:10.1177/0951692889001004001. Plott, C. R. 1967. A Notion of Equilibrium and its Possibility Under Majority Rule. The American Economic Review 57(4): 787 806. ISSN 00028282. URL http://www.jstor. org/stable/1815369. Sanders, D.; Clarke, H. D.; Stewart, M. C.; and Whiteley, P. 2011. Downs, stokes and the dynamics of electoral choice. British Journal of Political Science 287 314. Stokes, D. E. 1963. Spatial models of party competition. The American Political Science Review 57(2): 368 377. Wiseman, A. E. 2006. A theory of partisan support and entry deterrence in electoral competition. Journal of Theoretical Politics 18(2): 123 158. Wu, Y.; Lin, W.; Wang, H.; and Chao, K. 2014. The Generalized Popular Condensation Problem. In Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, 606 617. doi:10.1007/978-3-319-13075-0\ 48. URL https: //doi.org/10.1007/978-3-319-13075-0\ 48.