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

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

Piotr Faliszewski, Laurent Gourvès, Jérôme Lang, Julien Lesca, Jérôme Monnot

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 257-262.

Abstract

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.

Piotr Faliszewski, Laurent Gourvès, Jérôme Lang, Julien Lesca, and Jérôme Monnot. 2016. How Hard Is It for a Party to Nominate an Election Winner?. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 257–262. https://ijcai.org/proceedings/2016/44

@inproceedings{ijcai2016p44,
  title     = {How Hard Is It for a Party to Nominate an Election Winner?},
  author    = {Faliszewski, Piotr and Gourvès, Laurent and Lang, Jérôme and Lesca, Julien and Monnot, Jérôme},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {257--262},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/44},
}

TY  - CPAPER
TI  - How Hard Is It for a Party to Nominate an Election Winner?
AU  - Faliszewski, Piotr
AU  - Gourvès, Laurent
AU  - Lang, Jérôme
AU  - Lesca, Julien
AU  - Monnot, Jérôme
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 257
EP  - 262
UR  - https://ijcai.org/proceedings/2016/44
ER  -