2020/05/10 by Filtser, Arnold, Filtser, Omrit
#Computational Geometry (cs.CG) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2005.04799
Consider a set V of voters, 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 [TALG 2021] as a relaxation of the Condorcet criterion. Let β^*(X,d)=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 β^*(ℝ2,‖⋅‖2)=(√(3))/(2), and more generally, for d-dimensional Euclidean space, (1)/(√(d))≤ β^*(ℝd,‖⋅‖2)≤(√(3))/(2). In this paper, we show that 0.557≤ β^*(ℝ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)≤ \frac12.