Recognizing Top-Monotonic Preference Profiles in Polynomial Time

Krzysztof Magiera, Piotr Faliszewski

Abstract

This paper introduces the first polynomial-time algorithm to determine if a set of voter preferences is top-monotonic. By reducing the recognition problem to a 2-SAT (Boolean satisfiability) instance, the authors provide a mechanism to efficiently identify a broad class of well-behaved preferences that avoid the Condorcet paradox. The approach involves a local-to-global analysis where constraints on candidate orderings are derived from triples of alternatives and pairs of agents.

Introduction

In social choice theory, the Condorcet paradox occurs when collective preferences are cyclic (e.g., a majority prefers A over B, B over C, and C over A), making it impossible to pick a clear winner. To avoid this, researchers look for "restricted domains"—specific ways of structuring preferences that guarantee a stable winner.

The two most famous restrictions are single-peakedness (candidates sit on a left-to-right spectrum) and single-crossingness (voters are ordered on a spectrum). Top-monotonicity is a more recent and powerful generalization that encompasses both. While we have known for years how to quickly recognize if a profile is single-peaked or single-crossing, the complexity of recognizing top-monotonicity remained an open question. If we can't recognize it efficiently, we can't easily apply the mathematical benefits it provides to real-world voting data.

Methodology

The authors' primary contribution is a reduction of the recognition problem to the SAT-2CNF problem (2-SAT), which is well-known to be solvable in polynomial time. The algorithm works as follows:

  1. Triple-wise Analysis: The definition of top-monotonicity relies on the existence of a specific linear ordering of candidates. The authors show that this global ordering is constrained by how every triple of candidates is ranked by every pair of voters.
  2. Constraint Mapping: They identify 21 distinct ways a pair of agents can rank a triple of candidates. For each case, they derive a set of logical constraints (clauses) that any valid top-monotonic ordering must satisfy.
  3. 2-SAT Construction: They translate these constraints into a Boolean formula where variables represent the relative order of pairs of candidates (e.g., a variable $xy$ is true if $x$ precedes $y$ in the master ordering).
  4. Consistency Check: If the resulting 2-SAT formula is satisfiable, the profile is top-monotonic, and the satisfying assignment provides the required ordering.
Table 1: The 21 cases of agent preference combinations and their corresponding 2CNF constraints.

Key Insights and Ideas

  • The Power of 2-SAT: While many similar problems in social choice are solved using "consecutive-ones" properties or graph-based algorithms, the authors found that 2-SAT is a surprisingly natural fit for the constraints of top-monotonicity.
  • Local-to-Global Structure: The paper demonstrates that top-monotonicity—a property of an entire election—can be fully captured by looking at "local" interactions between pairs of voters and triples of candidates.
  • Generalization: The algorithm confirms that top-monotonicity is a robust "super-domain." Because it generalizes single-peaked and single-crossing preferences, this one algorithm can technically be used to recognize those simpler structures as well.

Key Results

  • Polynomial-Time Solvability: The authors prove that recognizing top-monotonicity is in P. Specifically, the 2-SAT formula generated has $O(|A|^2)$ variables and $O(N^2 \cdot |A|^3)$ clauses (where $N$ is the number of voters and $A$ is the number of candidates).
  • Handling Weak Preferences: Unlike some previous models that require strict rankings, this algorithm successfully handles "weak" preferences (where voters can be indifferent between candidates).
  • Constructive Algorithm: The method doesn't just give a "yes/no" answer; if a profile is top-monotonic, the algorithm actually computes the underlying linear order that proves it.

Discussion and Future Work

  • Intuition Gap: The authors admit that top-monotonicity is difficult to define intuitively. Unlike the "left-to-right" political spectrum of single-peaked preferences, top-monotonicity lacks a simple "real-world" metaphor, which may hinder its adoption by non-specialists.
  • Algorithmic Consequences: While we can now recognize these profiles, the paper leaves open the question of whether other NP-hard voting problems (like finding the winner under the Chamberlin–Courant rule) become easy to solve when we know a profile is top-monotonic.
  • Partial Orders: The paper focuses on complete (though possibly weak) preferences. Extending this to "partial" preferences (where voters leave some candidates unranked) remains a challenge, as previous work suggests this version of the problem is NP-hard.

Summary updated

Abstract

We provide the first polynomial-time algorithm for recognizing if a profile of (possibly weak) preference orders is top-monotonic. Top-monotonicity is a generalization of the notions of single-peakedness and single-crossingness, defined by Barbera and Moreno. Top-monotonic profiles always have weak Condorcet winners and satisfy a variant of the median voter theorem. Our algorithm proceeds by reducing the recognition problem to the SAT-2CNF problem.
BibTeX
@inproceedings{magiera2017recognizing,
  author = {Krzysztof Magiera and Piotr Faliszewski},
  title = {{Recognizing Top-Monotonic Preference Profiles in Polynomial Time}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/46},
}
Figure