TY - JOUR
AU - Filtser, Arnold
AU - Filtser, Omrit
PY - 2021/05/18
Y2 - 2024/08/13
TI - Condorcet Relaxation In Spatial Voting
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 35
IS - 6
SE - AAAI Technical Track on Game Theory and Economic Paradigms
DO - 10.1609/aaai.v35i6.16681
UR - https://ojs.aaai.org/index.php/AAAI/article/view/16681
SP - 5407-5414
AB - 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'' 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 β*(ℝ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)≤ 1/2 .
ER -