Robust Approximation and Incremental Elicitation in Voting Protocols

Lu, Tyler; Boutilier, Craig

doi:10.5591/978-1-57735-516-8/IJCAI11-058

Robust Approximation and Incremental Elicitation in Voting Protocols

Tyler Lu, Craig Boutilier

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 287-292.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-058

Abstract

While voting schemes provide an effective means for aggregating preferences, methods for the effective elicitation of voter preferences have received little attention. We address this problem by first considering approximate winner determination when incomplete voter preferences are provided. Exploiting natural scoring metrics, we use max regret to measure the quality or robustness of proposed winners, and develop polynomial time algorithms for computing the alternative with minimax regret for several popular voting rules. We then show how minimax regret can be used to effectively drive incremental preference/vote elicitation and devise several heuristics for this process. Despite worst-case theoretical results showing that most voting protocols require nearly complete voter preferences to determine winners, we demonstrate the practical effectiveness of regret-based elicitation for determining both approximate and exact winners on several real-world data sets.

Tyler Lu, and Craig Boutilier. 2011. Robust Approximation and Incremental Elicitation in Voting Protocols. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 287–292. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-058

@inproceedings{ijcai2011p58,
  title     = {Robust Approximation and Incremental Elicitation in Voting Protocols},
  author    = {Lu, Tyler and Boutilier, Craig},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {287--292},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-058},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-058},
}

TY  - CPAPER
TI  - Robust Approximation and Incremental Elicitation in Voting Protocols
AU  - Lu, Tyler
AU  - Boutilier, Craig
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 287
EP  - 292
DO  - 10.5591/978-1-57735-516-8/IJCAI11-058
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-058
ER  -