Elections with Few Voters: Candidate Control Can Be Easy

Authors

  • Jiehua Chen TU Berlin
  • Piotr Faliszewski AGH University of Science and Technology
  • Rolf Niedermeier TU Berlin
  • Nimrod Talmon TU Berlin

DOI:

https://doi.org/10.1609/aaai.v29i1.9429

Keywords:

Voting, NP-hard election control problem, parameterized complexity, W-hardness, fixed-parameter tractability

Abstract

We study the computational complexity of candidate control in elections with few voters (that is, we take the number of voters as a parameter). We consider both the standard scenario of adding and deleting candidates, where one asks if a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding/deleting some candidates, and a combinatorial scenario where adding/deleting a candidate automatically means adding/deleting a whole group of candidates. Our results show that the parameterized complexity of candidate control (with the number of voters as the parameter) is much more varied than in the setting with many voters.

Downloads

Published

2015-02-18

How to Cite

Chen, J., Faliszewski, P., Niedermeier, R., & Talmon, N. (2015). Elections with Few Voters: Candidate Control Can Be Easy. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9429

Issue

Section

AAAI Technical Track: Multiagent Systems