Position-Based Social Choice Methods for Intransitive Incomplete Pairwise Vote Sets (Student Abstract)

Julian ZuckerAAAI 2020 · DOI

Introduction

Social choice mechanisms are foundational to collective decision-making, yet they often face challenges when applied to real-world data. Preferences collected from individuals are frequently "messy"—they may be incomplete, where voters do not compare every possible pair of candidates, or intransitive, where a voter prefers candidate A over B, B over C, but C over A.

While pair-based methods (like Ranked Pairs) can handle such data, position-based methods (like the Borda count) require a complete, linear ranking. This paper introduces Ordering Induction, a framework designed to bridge this gap by transforming messy pairwise sets into clean, ordered rankings.

The Ordering Induction Framework

The proposed algorithm follows a three-step pipeline to induce a total ordering from a set of pairwise preferences:

  1. Resolve Intransitivity: The preference graph is pruned to remove cycles. The author tested three heuristics:
  2. Break Random: Removing a random edge within a cycle.
  3. Break Weakest: Removing the edge with the lowest global win-ratio in the cycle.
  4. Add In Order: Constructing a graph by adding edges in descending order of global win-ratio, skipping those that create cycles.
  5. Resolve Incompleteness: Missing edges are added to create a complete tournament. Two methods were evaluated:
  6. Add Random: Filling gaps randomly while maintaining transitivity.
  7. Add By Win Ratio: Filling gaps based on the candidates' global population win-ratios.
  8. Topological Sort: A standard topological sort is performed on the resulting transitive, complete graph to produce the final ranking.

Experimental Evaluation

The framework was tested using the Northeastern Cute Dog Project dataset, a unique real-world benchmark where users compared pairs of dogs. This dataset is particularly valuable because it contains both high levels of incompleteness and significant intransitivity (roughly one-third of voters).

Performance was measured using Kendall’s $\tau$, comparing the similarity between the induced rankings and the results of the Ranked Pairs method applied to the original data.

Key Results

The experimental results highlight a critical insight: the method used to handle missing data (incompleteness) is far more consequential than the method used to break cycles (intransitivity).

Kendall’s $\tau$ similarity scores across different resolution heuristics.

As shown in the table above, when "Add By Win Ratio" was used to resolve incompleteness, the similarity score reached a remarkably stable 0.988, regardless of the intransitivity resolution method. In contrast, using "Add Random" led to lower and more volatile scores, ranging from 0.896 to 0.936. This suggests that leveraging the "wisdom of the crowd" (global win ratios) to fill individual gaps is a highly effective heuristic.

Conclusion

Ordering induction provides a robust pathway for applying position-based social choice methods to imperfect real-world datasets. The study demonstrates that simple heuristics can effectively bypass the NP-complete feedback arc set problem. Future work may explore whether these findings hold in more polarized contexts, such as political elections, where intransitivity might be more structurally significant.

Summary updated

BibTeX
@inproceedings{zucker2020position,
  author = {Julian Zucker},
  title = {{Position-Based Social Choice Methods for Intransitive Incomplete Pairwise Vote Sets (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7273},
}
Figure