Recovering Single-Crossing Preferences From Approval Ballots

Andrei Constantinescu, Roger Wattenhofer

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:

  1. 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.
  2. 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.
The colorful graph represents dependencies between pairs of voters. Edges of the same color must maintain a consistent orientation to satisfy the underlying preference constraints.
  1. 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.
  2. 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.

A final directed graph of voters. An acyclic orientation of this graph, respecting the color-coded constraints, defines a valid single-crossing axis for the electorate.

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

Abstract

An electorate with fully-ranked innate preferences casts approval votes over a finite set of alternatives. As a result, only partial information about the true preferences is revealed to the voting authorities. In an effort to understand the nature of the true preferences given only partial information, one might ask whether the unknown innate preferences could possibly be single-crossing. The existence of a polynomial time algorithm to determine this has been asked as an outstanding problem in the works of Elkind and Lackner. We hereby give a polynomial time algorithm determining a single-crossing collection of fully-ranked preferences that could have induced the elicited approval ballots, or reporting the nonexistence thereof. Moreover, we consider the problem of identifying negative instances with a set of forbidden sub-ballots, showing that any such characterization requires infinitely many forbidden configurations.
BibTeX
@inproceedings{constantinescu2023recovering,
  author = {Andrei Constantinescu and Roger Wattenhofer},
  title = {{Recovering Single-Crossing Preferences From Approval Ballots}},
  booktitle = {WINE},
  year = {2023},
  doi = {10.1007/978-3-031-48974-7\_11},
}

Loading related content...

Figure