A Maximum Likelihood Approach towards Aggregating Partial Orders

Lirong Xia, Vincent ConitzerIJCAI 2011 · OpenReview

Abstract

In many real-world multi-agent systems and decision-making scenarios, voters provide partial rankings rather than complete linear orders due to information constraints or incomparability. This paper extends the Maximum Likelihood Estimation (MLE) framework—traditionally used for complete rankings—to aggregate these partial orders. We introduce "pairwise scoring rules" and establish that classic voting methods, such as Borda and Kemeny, are natural extensions within this probabilistic framework. We provide characterization theorems for these rules and analyze the computational complexity of winner selection, demonstrating that multi-winner identification under certain noise models is NP-complete.

Introduction

Traditional computational social choice assumes that agents report preferences as strict, complete linear orders. However, in domains such as committee reviews or multi-issue voting, this is often unrealistic. Voters may find candidates incomparable or may only have reviewed a subset of the available options, resulting in partial orders. While ad-hoc aggregation methods exist, this paper develops a principled approach based on Maximum Likelihood Estimation (MLE). This framework, originating with Condorcet, assumes a "correct" objective outcome exists and that observed votes are noisy, independent observations of this truth.

Methodology

The authors bridge probabilistic modeling with axiomatic voting theory by introducing Pairwise-Independent Models and Pairwise Scoring Rules. In these models, the probability of a voter’s preference between any two candidates is conditionally independent given the correct outcome.

The Maximum Likelihood Estimation (MLE) framework assumes a 'correct outcome' exists, with individual votes acting as noisy, independent observations.

The study utilizes mathematical proofs to establish equivalences between MLEs and specific voting rules. Furthermore, computational complexity analysis, including reductions from the MAX-CUT problem, is used to evaluate the hardness of winner determination.

Key Insights

A primary finding is that a voting rule is the MLE of a weakly neutral pairwise-independent noise model if and only if it is a pairwise scoring rule. This provides a strong probabilistic foundation for scoring-based rules. Notably, the Borda rule is identified as the unique neutral voting rule for single-winner selection that extends to partial orders via this MLE approach. Similarly, the Kemeny rule is shown to extend naturally for full ranking outputs. The paper also introduces Generalized Weighted Majority Graphs (GWMG) to adapt graph-based rules to partial orders by accounting for the proportion of comparisons made.

Results and Complexity

The paper successfully characterizes the traditional voting rules that can be ported to the partial-order domain (Theorems 1-3). However, selecting $k$ winners is shown to be computationally difficult. Specifically, the L-EVALUATION problem—determining if a candidate set meets a likelihood threshold—is NP-complete. Maximizing log-likelihood for the $k$-winner problem is also shown to be APX-hard and MAXSNP-hard.

Conclusion

This research provides a theoretical bridge for aggregating partial preferences. Future work includes closing the gap between necessary and sufficient conditions for extending outcome scoring rules and determining the exact complexity of computing winning outcomes in multi-winner models, conjectured to be $\Theta_2^P$-complete. Practical applications, such as software for PhD admissions or multi-agent coordination, represent promising directions for this framework.

Summary updated

BibTeX
@inproceedings{xia2011maximum,
  author = {Lirong Xia and Vincent Conitzer},
  title = {{A Maximum Likelihood Approach towards Aggregating Partial Orders}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=aIBvX9EqtD},
}
Figure