Approximately Strategy-Proof Voting

Birrell, Eleanor; Pass, Rafael

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

Approximately Strategy-Proof Voting

Eleanor Birrell, Rafael Pass

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 67-71.

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

Abstract

The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We consider a new approach for circumventing this result: we consider randomized voting rules that only approximate a deterministic voting rule and only are approximately strategy-proof. We show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule, and we provide asymptotically tight lower bounds on the parameters required by such voting rules.

Eleanor Birrell, and Rafael Pass. 2011. Approximately Strategy-Proof Voting. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 67–71. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-023

@inproceedings{ijcai2011p23,
  title     = {Approximately Strategy-Proof Voting},
  author    = {Birrell, Eleanor and Pass, Rafael},
  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     = {67--71},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-023},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-023},
}

TY  - CPAPER
TI  - Approximately Strategy-Proof Voting
AU  - Birrell, Eleanor
AU  - Pass, Rafael
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  - 67
EP  - 71
DO  - 10.5591/978-1-57735-516-8/IJCAI11-023
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-023
ER  -