Robust Winners and Winner Determination Policies Under Candidate Uncertainty

Craig Boutilier, Jérôme Lang, Joel Oren, Héctor Palacios

AAAI 2014 pp. 1391-1397

doi:10.1609/AAAI.V28I1.8893 /aaai/2014/boutilier2014aaai-robust/

Abstract

We consider voting situations in which some candidates may turn out to be unavailable. When determining availability is costly (e.g., in terms of money, time, or computation), voting prior to determining candidate availability and testing the winner's availability after the vote may be beneficial. However, since few voting rules are robust to candidate deletion, winner determination requires a number of such availability tests. We outline a model for analyzing such problems, defining robust winners relative to potential candidate unavailability. We assess the complexity of computing robust winners for several voting rules. Assuming a distribution over availability, and costs for availability tests/queries, we describe algorithms for computing optimal query policies, which minimize the expected cost of determining true winners.

PDF AAAI Semantic Scholar

Cite

Text

Boutilier et al. "Robust Winners and Winner Determination Policies Under Candidate Uncertainty." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.8893

Markdown

[Boutilier et al. "Robust Winners and Winner Determination Policies Under Candidate Uncertainty." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/boutilier2014aaai-robust/) doi:10.1609/AAAI.V28I1.8893

BibTeX

@inproceedings{boutilier2014aaai-robust,
  title     = {{Robust Winners and Winner Determination Policies Under Candidate Uncertainty}},
  author    = {Boutilier, Craig and Lang, Jérôme and Oren, Joel and Palacios, Héctor},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2014},
  pages     = {1391-1397},
  doi       = {10.1609/AAAI.V28I1.8893},
  url       = {https://mlanthology.org/aaai/2014/boutilier2014aaai-robust/}
}