Robust Winners and Winner Determination Policies under Candidate Uncertainty


  • Craig Boutilier University of Toronto
  • Jérôme Lang Université Paris-Dauphine
  • Joel Oren University of Toronto
  • Héctor Palacios Universitat Pompeu Fabra



social choice, voting, possible winners, robust winners, query policies, multi agent systems


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.




How to Cite

Boutilier, C., Lang, J., Oren, J., & Palacios, H. (2014). Robust Winners and Winner Determination Policies under Candidate Uncertainty. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Multiagent Systems