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 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₂^|. 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 Euclidean plane ß₍^*_R2_,k·k2) = ^v₂³, and more generally, for ddimensional Euclidean space, v¹_d = ß₍^*_Rd_,k·k2) = ^v₂³. In this paper, we show that 0.557 = ß₍^*_Rd_,k·k2) for any dimension d (notice that v¹_d < 0.557 for any d = 4). In addition, we prove that for every metric space (X,d) it holds that v2 - 1 = ß₍^*_X,d), and show that there exists a metric space for which ß₍^*_X,d) = ¹₂