A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

Betzler, Nadja; Hemmann, Susanne; Niedermeier, Rolf

A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

Nadja Betzler, Susanne Hemmann, Rolf Niedermeier

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 53-57.

Abstract

The Possible Winner problem asks whether some distinguished candidate may become the winner of an election when the given incomplete votes are extended into complete ones in a favorable way. Possible Winner is NP-complete for common voting rules such as Borda, many other positional scoring rules, Bucklin, Copeland etc. We investigate how three different parameterizations influence the computational complexity of Possible Winner for a number of voting rules. We show fixed-parameter tractability results with respect to the parameter number of candidates but intractability results with respect to the parameter number of votes. Finally, we derive fixed-parameter tractability results with respect to the parameter total number of undetermined candidate pairs and identify an interesting polynomial-time solvable special case for Borda.Nadja Betzler, Susanne Hemmann, Rolf Niedermeier

Nadja Betzler, Susanne Hemmann, and Rolf Niedermeier. 2009. A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09. IJCAI, 53–57. https://ijcai.org/proceedings/2009/20

@inproceedings{ijcai2009p20,
  title     = {A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes},
  author    = {Betzler, Nadja and Hemmann, Susanne and Niedermeier, Rolf},
  booktitle = {Proceedings of the Twenty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-09}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Hiroaki Kitano},
  pages     = {53--57},
  year      = {2009},
  url       = {https://ijcai.org/proceedings/2009/20},
}

TY  - CPAPER
TI  - A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes
AU  - Betzler, Nadja
AU  - Hemmann, Susanne
AU  - Niedermeier, Rolf
T2  - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2009
SP  - 53
EP  - 57
UR  - https://ijcai.org/proceedings/2009/20
ER  -