Condorcet Relaxation In Spatial Voting

Arnold Filtser, Omrit FiltserAAAI 2021 · DOI

Abstract

In social choice theory, a Condorcet winner—a candidate who beats all others in head-to-head matchups—rarely exists in multi-dimensional spatial voting models. This paper addresses this instability by exploring $\beta$-plurality points, which are stable under a distance relaxation factor $\beta$. The authors prove that a stable point always exists with a constant relaxation factor, independent of the number of dimensions, significantly improving upon previous dimension-dependent bounds.

Introduction: The Condorcet Paradox in Spatial Voting

Spatial voting models represent voters and candidates as points in a metric space, such as a multi-dimensional plane of political ideologies. In these models, a voter prefers the candidate closest to them. A central concept is the Condorcet winner: a candidate who would win a head-to-head majority vote against any other possible candidate.

However, in spaces with more than one dimension, a Condorcet winner almost never exists unless the voter distribution is perfectly symmetrical. For any proposed point $p$, there is typically an alternative $q$ that a majority of voters prefer. To address this inherent instability, researchers use the concept of $\beta$-plurality. A point $p$ is a $\beta$-plurality point if, after multiplying the distance from voters to $p$ by a factor $\beta$ (where $\beta \leq 1$), $p$ still defeats any other point $q$ in a majority vote. This $\beta$ factor acts as a "handicap" for the incumbent point $p$, providing a measure of the system's stability.

Methodology: The Minimal Radius Approach

The paper employs geometric proofs and metric space topology to find the largest possible $\beta$ that guarantees the existence of a stable point for any voter distribution. The authors utilize a "minimal radius" approach: they define $R_p$ as the smallest radius around a point $p$ containing at least half the voters. By identifying a point $p^*$ that minimizes this radius across the space, they construct proofs demonstrating that $p^*$ is a robust candidate for a $\beta$-plurality point.

Stability in Cycles and Trees

The topology of the metric space significantly impacts the stability factor. In "Tree" metrics (hierarchical structures), a Condorcet winner always exists, meaning $\beta=1$. However, the authors demonstrate that the introduction of even a single cycle into the metric space causes the guaranteed $\beta$ to drop to $1/2$.

Figure 1: A cycle graph example illustrating the voter distribution and the $\beta=1/2$ bound.

Breaking the Dimensionality Barrier in Euclidean Space

A major contribution of this work is the discovery of constant bounds in high-dimensional Euclidean spaces ($\mathbb{R}^d$). Previous literature suggested that as the number of dimensions $d$ increases, the required relaxation factor $\beta$ would vanish (specifically, scaling as $1/\sqrt{d}$).

This paper proves that $\beta$ actually maintains a constant lower bound of approximately $0.557$, regardless of the number of dimensions. This suggests that multi-dimensional social and political spaces are far more "stabilizable" than previously assumed.

Figure 2: Geometric construction used to derive the constant lower bound for $\beta$-plurality in Euclidean spaces.

Key Results and Comparison

The following table summarizes the new lower bounds for the relaxation parameter $\beta^*$ established in this research:

Space New Lower Bound Previous Best
General Metric Space $\sqrt{2} - 1 \approx 0.414$ None (Constant)
Euclidean Space ($\mathbb{R}^d$) $\approx 0.557$ $1/\sqrt{d}$
Cycle Graphs $1/2$ (Exact) $1$ (for Trees)

The shift from a dimension-dependent bound ($1/\sqrt{d}$) to a constant ($0.557$) is transformative for high-dimensional analysis. In a 100-dimensional space, for instance, the previous bound suggested a relaxation of $0.1$ might be necessary, while this work proves $0.557$ is sufficient.

Conclusion and Future Directions

While this paper establishes significant new constants, a gap remains between the proven lower bound ($0.557$) and the known upper bound ($\sqrt{3}/2 \approx 0.866$) for Euclidean spaces. The authors conjecture that the true value is $\sqrt{3}/2$ for all dimensions $d \geq 2$. Future work may also explore the computational complexity of finding these points in high dimensions and investigate more complex graph topologies beyond simple cycles and trees.

Summary updated

BibTeX
@inproceedings{filtser2021condorcet,
  author = {Arnold Filtser and Omrit Filtser},
  title = {{Condorcet Relaxation In Spatial Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16681},
}
Figure