Abstract
An electorate with fully-ranked innate preferences casts approval votes over a finite set of alternatives, revealing only partial information to voting authorities. A fundamental question in computational social choice is whether these unknown innate preferences could be single-crossing. We present the first polynomial-time algorithm to determine if a single-crossing collection of fully-ranked preferences could have induced a given set of approval ballots. Furthermore, we demonstrate that PSC (Possibly Single-Crossing) elections cannot be characterized by a finite set of forbidden sub-ballots, as any such characterization requires infinitely many forbidden configurations.
Introduction
In social choice theory, the "single-crossing" property is a powerful structural assumption. It posits that voters can be ordered along a one-dimensional spectrum such that for any two candidates, the preference switch between them occurs at most once across the voter sequence. This structure often reflects real-world political or ideological axes.
While previous research has explored single-crossing preferences in the context of full rankings, real-world voting often employs approval voting, where voters provide binary "yes/no" feedback. The Possibly Single-Crossing (PSC) problem asks: given a set of approval ballots, does there exist an underlying single-crossing preference profile consistent with them? This problem remained a significant open challenge in the field until now.
Methodology: From Ballots to Graphs
The proposed algorithm transforms the PSC problem into a combinatorial search for an acyclic orientation of a specialized graph. The process involves several key steps:
- Non-Betweenness Constraints: The approval ballots are first converted into constraints that restrict the relative positioning of voters. Specifically, for certain triples $(i, j, k)$, voter $j$ is forbidden from being placed between $i$ and $k$ on the societal axis.
- The Formula and Colorful Graphs: The algorithm constructs a "formula graph" where vertices represent the relative order of pairs of voters. This is further refined into a colorful graph. In this graph, edges are grouped by color; the algorithm must decide for each color whether to keep the current orientation of all its edges or flip them all.
- Acyclic Orientation: The core task is to find a "color-consistent" orientation that results in an acyclic graph. The authors discovered a "Three-Colored Triangle" rule: if a cycle exists, the smallest such cycle must be a triangle of three distinct colors. This insight allows the problem to be solved efficiently.
- Verification: To ensure the algorithm's correctness across all combinatorial possibilities, the researchers employed a computer-aided proof to verify local graph structures (Lemmas 32 and 33).
Key Results and Insights
The primary contribution is a polynomial-time algorithm for the PSC problem, resolving a long-standing question by Elkind and Lackner.
Beyond the main algorithm, the paper provides several theoretical insights:
- Fixed-Parameter Tractability: The approach yields an FPT algorithm for the non-betweenness problem, where complexity scales with the number of colors rather than the total number of voters.
- Infinite Forbidden Substructures: Unlike many other voting properties (like single-peakedness), PSC cannot be defined by a finite set of "bad" patterns. The authors proved that there is an infinite family of minimal non-PSC configurations, meaning no finite checklist can ever fully characterize invalid instances.
Discussion and Future Directions
While this work solves the binary approval case, extending it to multi-valued scores (e.g., 3-level approval) remains difficult, as the underlying combinatorial lemmas no longer hold. Future research may focus on "nearly" single-crossing profiles—finding the best fit for noisy real-world data—and applying these algorithms to the study of core-stable committees in multi-winner elections.
Summary updated