OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Gibbard-Satterthwaite Games

Elkind, Edith and Grandi, Umberto and Rossi, Francesca and Slinko, Arkadii Gibbard-Satterthwaite Games. (2015) In: 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), 25 July 2015 - 31 July 2015 (Buenos Aires, Argentina).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to AAAI press. This papers appears in IJCAI'15 Proceedings of the 24th International Conference on Artificial Intelligence ISBN: 978-1-57735-738-4 The definitive version is available https://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/view/10909/10738 ; https://www.ijcai.org/Proceedings/15/Papers/081.pdf
HAL Id:hal-01523671
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Harvard university (USA)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > University of Oxford (UNITED KINGDOM)
Other partners > Università degli Studi di Padova (ITALY)
Other partners > University of Auckland - UOA (NEW ZEALAND)
Laboratory name:
Deposited On:21 Apr 2017 14:53

Repository Staff Only: item control page