Gibbard-Satterthwaite Games

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

[img]
Preview
Text
Download (261kB) | Preview

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.

Item Type: Conference or Workshop Item (Paper)
Language: English
Date: 2015
Uncontrolled Keywords: Gibbard-Satterthwaite theorem
Subjects: H- INFORMATIQUE
Divisions: Institut de Recherche en Informatique de Toulouse
Site: UT1
Date Deposited: 14 Mar 2019 14:15
Last Modified: 14 Mar 2019 14:15
URI: http://publications.ut-capitole.fr/id/eprint/29519

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year