Abstract
In social choice theory, the Condorcet paradox represents a fundamental challenge to fair collective decision-making, where cyclic preferences prevent the selection of a clear winner. Restricted domains, such as single-peaked or single-crossing preferences, provide a structural solution by guaranteeing the existence of a Condorcet winner. Top-monotonicity is a powerful generalization that encompasses these domains, yet its recognition has remained an algorithmic challenge. This paper presents the first polynomial-time algorithm to determine if a preference profile is top-monotonic. By reducing the problem to a 2-Satisfiability (2-SAT) instance, the authors demonstrate that top-monotonicity can be recognized in $O(m^4 n^2)$ time, bridging a significant gap in the computational study of preference structures.
Introduction
The search for "order in the chaos" of voting is a central theme in social choice. When voter preferences are unrestricted, a majority may prefer candidate A to B, B to C, and C to A, leading to instability. To mitigate this, researchers identify restricted domains—mathematical structures that preferences must follow to ensure a stable outcome. While algorithms to recognize single-peaked and single-crossing preferences have been established for years, top-monotonicity—a more recent and inclusive domain restriction—lacked an efficient recognition procedure. This research addresses that gap, providing a formal mechanism to identify these structured preferences in polynomial time.
The Top-Monotonicity Framework
Top-monotonicity is a broad category of voting patterns. It is more flexible than the traditional 1D spectrum of single-peaked preferences, making it a more realistic model for complex elections. However, this flexibility makes it harder to detect. The core challenge lies in determining whether there exists a linear ordering of candidates (a "societal axis") such that the preferences of all voters satisfy the top-monotonicity condition relative to that axis.
Methodology: The 2-SAT Reduction
The authors solve the recognition problem by cleverly mapping the constraints of top-monotonicity onto the 2-Satisfiability (2-SAT) problem. Unlike many domain-recognition problems that rely on graph-theoretic properties or the consecutive-ones property, this approach uses boolean logic to enforce structural consistency.
1. Triple-wise Analysis and Legal Orderings
The algorithm begins by analyzing all possible triples of candidates. For every triple, the algorithm evaluates how voters rank them to determine which linear orderings are "legal" under the definition of top-monotonicity. This step ensures that the local structure of the preferences is consistent with the global requirements of the domain.
2. Encoding Constraints
The problem is then translated into a SAT-2CNF formula. Boolean variables are created to represent the relative order of every pair of candidates (e.g., a variable $xy$ is true if candidate $x$ precedes $y$ on the societal axis). The algorithm constructs a formula where each clause contains at most two literals, representing the transitivity of the ordering and the specific requirements of top-monotonicity.
3. Handling Weak Orders
A significant contribution of this methodology is its ability to handle "weak preferences," where voters may be indifferent between two or more candidates. This makes the algorithm applicable to a wider range of real-world voting scenarios than models that require strict rankings.
The Algorithmic Pipeline
The paper outlines a clear five-step process for recognizing top-monotonicity:
- Top Candidate Computation: Identify the set of candidates ranked first by at least one voter.
- Candidate Refinement: Eliminate or group indistinguishable candidates to reduce the problem size.
- Formula Generation: Construct the SAT-2CNF formula based on the triple-wise analysis.
- 2-SAT Resolution: Solve the formula using standard polynomial-time 2-SAT solvers.
- Reconstruction: If the formula is satisfiable, use the truth assignments to reconstruct the final societal axis via topological sorting.
Key Results and Complexity
The primary theoretical result is the proof that recognizing top-monotonicity is in P. The algorithm achieves a time complexity of $O(m^4 n^2)$, where $m$ is the number of candidates and $n$ is the number of voters.
Beyond the complexity result, the paper demonstrates the versatility of the 2-SAT approach. The authors show that this framework can also be adapted to recognize other restricted domains, such as single-peaked preferences, suggesting that 2-SAT may serve as a "Swiss Army knife" for domain recognition problems in social choice.
Discussion and Future Work
While the $O(m^4 n^2)$ complexity is polynomial, it may still be computationally intensive for very large-scale elections. The authors suggest that future work could focus on optimizing the data structures used or employing heuristics—such as Integer Linear Programming (ILP) formulations—to improve practical performance on modern hardware.
Additionally, the recognition of top-monotonicity opens the door to more efficient computation of otherwise NP-hard voting rules. If an election is recognized as top-monotonic, rules like the Chamberlin–Courant rule may become significantly easier to solve, providing a path toward more efficient and fair collective decision-making in practice.
Summary updated