Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains
Edith Elkind, Nisarg Shah
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.
Keywords:
Pages: 182-191
PS Link:
PDF Link: /papers/14/p182-elkind.pdf
BibTex:
@INPROCEEDINGS{Elkind14,
AUTHOR = "Edith Elkind and Nisarg Shah",
TITLE = "Electing the Most Probable Without Eliminating the Irrational: Voting Over Intransitive Domains",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "182--191"
}


hosted by DSL   •   site info   •   help