ML Anthology

Approximately Strategy-Proof Voting

Eleanor Birrell, Rafael Pass
IJCAI 2011 pp. 67-72
doi:10.5591/978-1-57735-516-8/IJCAI11-023 /ijcai/2011/birrell2011ijcai-approximately/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Birrell and Pass. "Approximately Strategy-Proof Voting." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-023

Markdown

[Birrell and Pass. "Approximately Strategy-Proof Voting." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/birrell2011ijcai-approximately/) doi:10.5591/978-1-57735-516-8/IJCAI11-023

BibTeX

@inproceedings{birrell2011ijcai-approximately,
  title     = {{Approximately Strategy-Proof Voting}},
  author    = {Birrell, Eleanor and Pass, Rafael},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {67-72},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-023},
  url       = {https://mlanthology.org/ijcai/2011/birrell2011ijcai-approximately/}
}