Preferences Single-Peaked on a Circle

Dominik Peters, Martin LacknerAAAI 2017 · DOI

Introduction

In computational social choice, the aggregation of individual preferences into a collective decision is often hindered by two major hurdles: computational hardness and fundamental impossibility theorems. While many "good" voting rules are NP-hard to compute, mathematical proofs like the Gibbard–Satterthwaite theorem show that no non-dictatorial voting rule can satisfy all fairness properties simultaneously.

A classic solution is to restrict preferences to the single-peaked domain, typically modeled on a linear spectrum. However, the "line" model is often too restrictive for cyclic scenarios, such as choosing a time for a meeting or a location on a city's ring road. This paper introduces Single-Peaked on a Circle (SPOC) preferences, a natural generalization that captures these scenarios while offering unique computational advantages.

Defining the SPOC Domain

A preference profile is defined as SPOC if there exists a circular ordering of candidates such that for every voter, there is at least one point on the circle where it can be "cut" to make that voter's preferences single-peaked on the resulting line. This allows the model to capture "extremist" preferences—voters who like both ends of a spectrum but dislike the middle—which are common in polarized environments.

Figure 1: Synthetic examples of preference curves. The red curve illustrates how a 'single-caved' preference on a line can be single-peaked on a circle.

Methodology and Recognition

The authors provide a linear-time recognition algorithm for SPOC profiles, running in $O(mn)$ time for $m$ candidates and $n$ voters. The algorithm employs a "slicing" technique: by picking an arbitrary candidate and splitting each voter's preference relative to that point, the problem is reduced to the known task of recognizing single-peakedness on a line.

Figure 4: A circular representation of candidates, highlighting the structural properties used in the recognition algorithm.

For multi-winner rules like Chamberlin–Courant and Proportional Approval Voting (PAV), the authors utilize Integer Programming. They prove that the resulting constraint matrices are totally unimodular (TUM), which guarantees that these complex problems can be solved in polynomial time.

Key Insights: The "Rebel" Domain

A significant finding of this work is the divergence between computational and axiomatic properties. Typically, a domain structured enough to simplify algorithms also prevents voting paradoxes. SPOC, however, is a "rebel" domain:

  • Algorithmic Efficiency: It makes rules like Young’s rule and Chamberlin–Courant easy to compute. Notably, the algorithm for Young's rule in the SPOC domain ($O(mn^2)$) improves upon the best-known bounds for the standard linear domain.
  • Persistent Paradoxes: Despite its structure, SPOC does not prevent the Condorcet paradox (where A beats B, B beats C, and C beats A). The authors prove that any possible majority tournament can be generated by SPOC preferences, explaining why Kemeny’s rule remains NP-hard.

Results and Impossibilities

The research establishes that while SPOC is computationally friendly for many rules, it does not circumvent fundamental social choice limitations:

  • Efficient Voting: Young’s Rule, Chamberlin–Courant, and PAV are all polynomial-time computable.
  • Axiomatic Hurdles: The Gibbard–Satterthwaite theorem still holds, meaning rules remain manipulable. Furthermore, the No-Show Paradox (where a voter is better off not participating) cannot be avoided.
  • Computational Limits: Kemeny’s rule remains NP-hard, demonstrating that circular structure alone cannot simplify all preference aggregation tasks.

Conclusion and Future Work

The SPOC domain provides a more flexible and realistic model for structured preferences than the traditional linear model, particularly in polarized or cyclic contexts. While it offers significant computational benefits, it does not solve the "fairness" issues inherent in social choice. Future work may extend these concepts to higher-dimensional manifolds like the sphere or explore stricter circular definitions to find domains that might finally guarantee the existence of Condorcet winners.

Summary updated

BibTeX
@inproceedings{peters2017preferences,
  author = {Dominik Peters and Martin Lackner},
  title = {{Preferences Single-Peaked on a Circle}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10615},
}
Figure