Thumbnail - No thumbnail

Robust Winners and Winner Determination Policies under Candidate Uncertainty

Boutilier, Craig; Lang, Jérôme; Oren, Joel; Palacios, Héctor (2014), Robust Winners and Winner Determination Policies under Candidate Uncertainty, in Brodley, Carla E.; Stone, Peter, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI Press : Palo Alto (USA), p. 1391-1397

Type
Communication / Conférence
External document link
http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8648
Date
2014
Conference title
28th AAAI Conference on Artificial Intelligence
Conference date
2014-07
Conference city
Québec
Conference country
Canada
Book title
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence
Book author
Brodley, Carla E.; Stone, Peter
Publisher
AAAI Press
Published in
Palo Alto (USA)
ISBN
978-1-57735-661-5
Number of pages
3155
Pages
1391-1397
Metadata
Show full item record
Author(s)
Boutilier, Craig

Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oren, Joel

Palacios, Héctor
Abstract (EN)
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.
Subjects / Keywords
social choice; voting; possible winners; robust winners; query policies; multi agent systems