Thumbnail

How Hard Is It for a Party to Nominate an Election Winner?

Faliszewski, Piotr; Gourvès, Laurent; Lang, Jérôme; Lesca, Julien; Monnot, Jérôme (2016), How Hard Is It for a Party to Nominate an Election Winner?, in Kambhampati, Subbarao, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, AAAI Press / IJCAI, p. 257-263

View/Open
Type
Communication / Conférence
Date
2016
Conference title
Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016
Conference date
2016-07
Conference city
New York
Conference country
United States
Book title
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016
Book author
Kambhampati, Subbarao
Publisher
AAAI Press / IJCAI
ISBN
978-1-57735-770-4
Pages
257-263
Metadata
Show full item record
Author(s)
Faliszewski, Piotr
Department of Automatics [AGH-UST]
Gourvès, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lesca, Julien
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We consider a Plurality-voting scenario, where the candidates are split between parties, and each party nominates exactly one candidate for the final election. We study the computational complexity of deciding if there is a set of nominees such that a candidate from a given party wins in the final election. In our second problem, the goal is to decide if a candidate from a given party always wins, irrespective who is nominated. We show that these problems are computationally hard, but are polynomial-time solvable for restricted settings.
Subjects / Keywords
Computational Social Choice; Voting; Computational Complexity