ML Anthology

A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes

Nadja Betzler, Susanne Hemmann, Rolf Niedermeier
IJCAI 2009 pp. 53-58
/ijcai/2009/betzler2009ijcai-multivariate/

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

PDF Semantic Scholar

Cite

Text

Betzler et al. "A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes." International Joint Conference on Artificial Intelligence, 2009.

Markdown

[Betzler et al. "A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes." International Joint Conference on Artificial Intelligence, 2009.](https://mlanthology.org/ijcai/2009/betzler2009ijcai-multivariate/)

BibTeX

@inproceedings{betzler2009ijcai-multivariate,
  title     = {{A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes}},
  author    = {Betzler, Nadja and Hemmann, Susanne and Niedermeier, Rolf},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2009},
  pages     = {53-58},
  url       = {https://mlanthology.org/ijcai/2009/betzler2009ijcai-multivariate/}
}