Plurality in Spatial Voting Games with constant β
share
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 [SoCG 2020] as a relaxation of the Condorcet criterion. Let β^*_(X,d)=sup{β|}. 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.
READ FULL TEXT