Possible Winners in Noisy Elections

Authors

  • Krzysztof Wojtas AGH University of Science and Technology
  • Piotr Faliszewski AGH Univesity of Science and Technology

DOI:

https://doi.org/10.1609/aaai.v26i1.8255

Keywords:

elections, voting, control, counting problems, computational complexity

Abstract

We consider the problem of predicting winners in elections given complete knowledge about all possible candidates, all possible voters (together with their preferences), but in the case where it is uncertain either which candidates exactly register for the election or which voters cast their votes. Under reasonable assumptions our problems reduce to counting variants of election control problems. We either give polynomial-time algorithms or prove #P-completeness results for counting variants of control by adding/deleting candidates/voters for Plurality, k-Approval, Approval, Condorcet, and Maximin voting rules.

Downloads

Published

2021-09-20

How to Cite

Wojtas, K., & Faliszewski, P. (2021). Possible Winners in Noisy Elections. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 1499-1505. https://doi.org/10.1609/aaai.v26i1.8255

Issue

Section

AAAI Technical Track: Multiagent Systems