On Recognising Nearly Single-Crossing Preferences

Florian Jaeckle, Dominik Peters, Edith Elkind

Abstract

In computational social choice, the single-crossing property is a powerful structural constraint that renders many NP-hard voting problems tractable. However, real-world preference profiles rarely satisfy this property perfectly. This paper investigates the "recognition problem" for profiles that are nearly single-crossing. We analyze three distance metrics: partitioning voters into $k$ single-crossing groups, allowing a limited number of local swaps per voter, and partitioning candidates. Our results provide a complexity map for these problems, including a polynomial-time algorithm for 2-voter partitions and an XP algorithm for local swaps, while demonstrating that candidate-based partitioning is NP-complete.

Introduction

Aggregating individual preferences into a collective decision is the core task of social choice theory. In multiwinner elections, where the goal is to select a committee of representatives, many common voting rules are computationally intractable (NP-hard). To circumvent this, researchers look for structural properties in voter preferences that simplify these calculations.

One such structure is the single-crossing property. A preference profile is single-crossing if there exists an ordering of voters such that for any pair of candidates, the voters' relative preference between them changes at most once as we move through the sequence. This often corresponds to voters being aligned along a one-dimensional ideological spectrum (e.g., left-to-right).

A standard single-crossing preference profile where candidate rankings change at most once across the voter sequence.

Despite its theoretical utility, the single-crossing property is seldom found in its pure form in real-world datasets, such as those in the PrefLib library. This paper addresses the gap by developing algorithms to recognize profiles that are "nearly" single-crossing, allowing for small deviations or sub-structures.

Metrics for "Nearness"

The authors explore three primary ways to define how close a profile is to being single-crossing.

1. Voter Partition

This metric asks whether the set of voters can be split into $k$ disjoint groups, where each group independently satisfies the single-crossing property. This models a society composed of a few distinct ideological "camps."

The authors show that for $k=2$, the problem can be reduced to 2-SAT, making it solvable in $O(n^4 m^2)$ time. This is a significant result, as it allows researchers to efficiently identify if a messy profile is actually the union of two structured groups.

A preference profile partitioned into two single-crossing groups, highlighted in red and gray.

2. Local Swaps

Instead of ignoring or grouping voters, the local swaps metric assumes every voter's ranking is mostly correct but might contain minor errors—perhaps due to indifference between similar candidates. A profile is "nearly" single-crossing if it can be made perfectly so by performing at most $k$ adjacent swaps in each voter's ranking.

The authors developed an algorithm using a Directed Acyclic Graph (DAG) approach. By fixing a "first" voter and building the profile block by block, they proved that this recognition problem is in XP, meaning it is solvable in polynomial time for any fixed value of $k$. This approach is considered more "egalitarian" than voter deletion, as it preserves the input of every participant.

3. Alternative Partition

Finally, the paper considers partitioning the candidates into $k$ sets such that the voters' preferences over each set are single-crossing. Unlike voter-based metrics, this approach proves to be much harder. By reducing the problem from k-coloring, the authors demonstrate that recognizing such profiles is NP-complete for $k \ge 3$.

Key Results and Complexity Map

The paper's findings are summarized in the following complexity table:

Distance Metric Complexity Result
Voter Partition ($k=2$) In P ($O(n^4 m^2)$)
Voter Partition ($k \ge 3$) Open
Local Swaps In XP (Polynomial for fixed $k$)
Alternative Partition NP-complete ($k \ge 3$)

Note: $n$ represents the number of voters, and $m$ represents the number of candidates.

Conclusion and Future Directions

This research provides a theoretical foundation for using "nearly" structured preferences to solve complex voting problems. By identifying which nearness metrics are computationally manageable, the authors pave the way for more robust multiwinner voting systems.

Future work remains in several areas, including finding a Fixed-Parameter Tractable (FPT) algorithm for local swaps to improve practical performance and determining the complexity of partitioning voters into three or more groups. Ultimately, these algorithms serve as a "front-end" for social choice mechanisms, allowing them to handle the inherent messiness of real-world democratic processes.

Summary updated

Abstract

If voters' preferences are one-dimensional, many hard problems in computational social choice become tractable. A preference profile can be classified as one-dimensional if it has the single-crossing property, which requires that the voters can be ordered from left to right so that their preferences are consistent with this order. In practice, preferences may exhibit some one-dimensional structure, despite not being single-crossing in the formal sense. Hence, we ask whether one can identify preference profiles that are close to being single-crossing. We consider three distance measures, which are based on partitioning voters or candidates or performing a small number of swaps in each vote. We prove that it can be efficiently decided if voters can be split into two single-crossing groups. Also, for every fixed k >
BibTeX
@inproceedings{jaeckle2018recognising,
  author = {Florian Jaeckle and Dominik Peters and Edith Elkind},
  title = {{On Recognising Nearly Single-Crossing Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11461},
}
Figure