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.
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