A Characterization of the Single-Peaked Single-Crossing Domain

Edith Elkind, Piotr Faliszewski, Piotr Skowron

Introduction

In social choice theory, Arrow’s Impossibility Theorem highlights the inherent difficulty in designing perfect voting systems for general preferences. To circumvent these theoretical barriers, researchers often focus on restricted domains—specific structures in voter preferences that allow for fair outcomes and efficient computation. Two of the most prominent restrictions are Single-Peaked (SP) and Single-Crossing (SC) preferences. While both domains have been extensively studied individually, their intersection, the SPSC domain, remained poorly understood until recently. This paper provides a complete mathematical characterization of SPSC elections, revealing their underlying structure and enabling significant algorithmic improvements.

The SPSC Domain vs. 1-Euclidean

A common assumption in the field was that SPSC elections are equivalent to 1-Euclidean elections, where both voters and candidates are represented as points on a one-dimensional line, and preferences are determined by Euclidean distance. However, the authors demonstrate that this assumption is incorrect. By constructing a specific election profile that satisfies both SP and SC conditions but lacks a 1D Euclidean representation, they prove that the SPSC domain is strictly broader than the 1-Euclidean model.

An election profile demonstrating that SPSC is not equivalent to 1-Euclidean.

Characterization via Narcissism

The central contribution of this work is the characterization of SPSC elections through the lens of "narcissistic" elections. An election is considered narcissistic if every candidate is ranked first by at least one voter. The authors prove a critical structural link: every narcissistic single-crossing election is inherently single-peaked.

Building on this, they establish that an election is SPSC if and only if it is "pre-narcissistic single-crossing"—meaning it can be formed by taking a narcissistic single-crossing election and deleting a subset of voters. This characterization reveals that in SPSC elections, a candidate's popularity follows a single-peaked trajectory across the ordered set of voters: a candidate starts low, rises to a peak (potentially reaching the top rank), and then declines.

Algorithmic Implications

The structural rigidity of the SPSC domain has profound implications for computational social choice. The authors provide an $O(nm^2)$ algorithm to recognize SPSC elections and "complete" them into their narcissistic counterparts.

Furthermore, this characterization allows for the efficient resolution of problems that are typically NP-hard. For instance, the egalitarian version of Monroe’s voting rule, which previously required complex $O(n^3m^3k^3)$ algorithms or was restricted to narcissistic domains, can now be solved in $O(m^2n)$ time for any SPSC election. The paper also shows that for Plurality and Condorcet rules, the "Possible Winner" problem is solvable if the observed election is SPSC.

Conclusion

By formalizing the relationship between single-peaked and single-crossing preferences, this research clarifies a significant niche in social choice theory. The discovery that SPSC elections are sub-elections of narcissistic SC elections not only provides theoretical clarity but also paves the way for faster algorithms in complex voting scenarios. Future work may explore whether other computationally difficult social choice problems can be simplified within the SPSC domain.

Summary updated

Abstract

We investigate elections that are simultaneously single-peaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and single-crossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic single-crossing election by deleting voters. We show two applications of our characterization.
BibTeX
@inproceedings{elkind2014characterization,
  author = {Edith Elkind and Piotr Faliszewski and Piotr Skowron},
  title = {{A Characterization of the Single-Peaked Single-Crossing Domain}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8821},
}
Figure