Gibbard-Satterthwaite Games

Elkind, Edith; Grandi, Umberto; Rossi, Francesca; Slinko, Arkadii M.

Gibbard-Satterthwaite Games

Edith Elkind, Umberto Grandi, Francesca Rossi, Arkadii M. Slinko

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 533-538.

Abstract

The Gibbard-Satterthwaite theorem implies the ubiquity of manipulators — voters who could change the election outcome in their favor by unilaterally modifying their vote. In this paper, we ask what happens if a given profile admits several such voters. We model strategic interactions among Gibbard–Satterthwaite manipulators as a normal-form game. We classify the 2-by-2 games that can arise in this setting for two simple voting rules, namely Plurality and Borda, and study the complexity of determining whether a given manipulative vote weakly dominates truth-telling, as well as existence of Nash equilibria.

Edith Elkind, Umberto Grandi, Francesca Rossi, and Arkadii M. Slinko. 2015. Gibbard-Satterthwaite Games. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 533–538. https://ijcai.org/proceedings/2015/81

@inproceedings{ijcai2015p81,
  title     = {Gibbard-Satterthwaite Games},
  author    = {Elkind, Edith and Grandi, Umberto and Rossi, Francesca and Slinko, Arkadii M.},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {533--538},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/81},
}

TY  - CPAPER
TI  - Gibbard-Satterthwaite Games
AU  - Elkind, Edith
AU  - Grandi, Umberto
AU  - Rossi, Francesca
AU  - Slinko, Arkadii M.
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 533
EP  - 538
UR  - https://ijcai.org/proceedings/2015/81
ER  -