AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
A Multivariate Complexity Analysis of Determining Possible Winners Given Incomplete Votes
Nadja Betzler, Susanne Hemmann, Rolf Niedermeier

Last modified: 2009-06-24

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.

Full Text: PDF