Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains

Edith Elkind, Nisarg Shah Carnegie Mellon University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:236-245, 2014.

Abstract

Picking the best alternative in a given set is a well-studied problem at the core of social choice theory. In some applications, one can assume that there is an objectively correct way to compare the alternatives, which, however, cannot be ob- served directly, and individuals’ preferences over the alternatives (votes) are noisy estimates of this ground truth. The goal of voting in this case is to estimate the ground truth from the votes. In this paradigm, it is usually assumed that the ground truth is a ranking of the alternatives by their true quality. However, sometimes alterna- tives are compared using not one but multiple quality parameters, which may result in cycles in the ground truth as well as in the preferences of the individuals. Motivated by this, we provide a formal model of voting with possibly intransi- tive ground truth and preferences, and investigate the maximum likelihood approach for picking the best alternative in this case. We show that the resulting framework leads to polynomial-time al- gorithms, and also approximates the correspond- ing NP-hard problems in the classic framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-elkind14a, title = {Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains}, author = {Elkind, Edith and University, Nisarg Shah Carnegie Mellon}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {236--245}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/elkind14a/elkind14a.pdf}, url = {https://proceedings.mlr.press/r12/elkind14a.html}, abstract = {Picking the best alternative in a given set is a well-studied problem at the core of social choice theory. In some applications, one can assume that there is an objectively correct way to compare the alternatives, which, however, cannot be ob- served directly, and individuals’ preferences over the alternatives (votes) are noisy estimates of this ground truth. The goal of voting in this case is to estimate the ground truth from the votes. In this paradigm, it is usually assumed that the ground truth is a ranking of the alternatives by their true quality. However, sometimes alterna- tives are compared using not one but multiple quality parameters, which may result in cycles in the ground truth as well as in the preferences of the individuals. Motivated by this, we provide a formal model of voting with possibly intransi- tive ground truth and preferences, and investigate the maximum likelihood approach for picking the best alternative in this case. We show that the resulting framework leads to polynomial-time al- gorithms, and also approximates the correspond- ing NP-hard problems in the classic framework.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains %A Edith Elkind %A Nisarg Shah Carnegie Mellon University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-elkind14a %I PMLR %P 236--245 %U https://proceedings.mlr.press/r12/elkind14a.html %V R12 %X Picking the best alternative in a given set is a well-studied problem at the core of social choice theory. In some applications, one can assume that there is an objectively correct way to compare the alternatives, which, however, cannot be ob- served directly, and individuals’ preferences over the alternatives (votes) are noisy estimates of this ground truth. The goal of voting in this case is to estimate the ground truth from the votes. In this paradigm, it is usually assumed that the ground truth is a ranking of the alternatives by their true quality. However, sometimes alterna- tives are compared using not one but multiple quality parameters, which may result in cycles in the ground truth as well as in the preferences of the individuals. Motivated by this, we provide a formal model of voting with possibly intransi- tive ground truth and preferences, and investigate the maximum likelihood approach for picking the best alternative in this case. We show that the resulting framework leads to polynomial-time al- gorithms, and also approximates the correspond- ing NP-hard problems in the classic framework. %Z Reissued by PMLR on 04 October 2026.
APA
Elkind, E. & University, N.S.C.M.. (2014). Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:236-245 Available from https://proceedings.mlr.press/r12/elkind14a.html. Reissued by PMLR on 04 October 2026.

Related Material