Piotr Faliszewski, Edith Hemaspaandra and Lane A. Hemaspaandra (2015) "Weighted Electoral Control", Volume 52, pages 507-542 AAMAS 2013 Best Paper Award Finalist

PDF | PostScript | doi:10.1613/jair.4621

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.

Click here to return to Volume 52 contents list