Condorcet Relaxation In Spatial Voting

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 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 [SoCG 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 Eu- 2 , and more generally, for ddimensional Euclidean space, 1 2 . In this paper, we show that 0.557 ≤ β * (R d , • 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 2 .