A parameterized perspective on protecting elections

Show simple item record

dc.contributor.author Dey, Palash
dc.contributor.author Misra, Neeldhara
dc.contributor.author Nath, Swaprava
dc.contributor.author Shakya, Garima
dc.coverage.spatial United States of America
dc.date.accessioned 2021-06-15T14:10:28Z
dc.date.available 2021-06-15T14:10:28Z
dc.date.issued 2021-06
dc.identifier.citation Dey, Palash; Misra, Neeldhara; Nath, Swaprava; Shakya, Garima, "A parameterized perspective on protecting elections", Theoretical Computer Science, DOI: 10.1016/j.tcs.2021.05.006, vol. 874, pp. 15-31, Jun. 2021. en_US
dc.identifier.issn 0304-3975
dc.identifier.uri https://doi.org/10.1016/j.tcs.2021.05.006
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/6567
dc.description.abstract We study the parameterized complexity of the Optimal Defense and Optimal Attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a district consisting of a set of votes) and two integers and corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the Optimal Defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most voter groups such that, no matter which voter groups the attacker attacks, the outcome of the election does not change. In the Optimal Attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking voter groups such that, no matter which voter groups the defender defends, the outcome of the election is always different from the original one (without any attack). We show that both the Optimal Defense problem and the Optimal Attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only 3 candidates. We also show that the Optimal Defense problem for every scoring rule and the Condorcet voting rule is -hard for both the parameters and , while it admits a fixed parameter tractable algorithm parameterized by the combined parameter . The Optimal Attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder - it is -hard even for the combined parameter . We propose two greedy algorithms for the Optimal Defense problem and empirically show that they perform effectively on many voting profiles.
dc.description.statementofresponsibility by PalashDey, Neeldhara Misra, Swaprava Nath and Garima Shakya
dc.format.extent vol. 874, pp. 15-31
dc.language.iso en_US en_US
dc.publisher Elsevier en_US
dc.subject Parameterized complexity en_US
dc.subject Election control en_US
dc.subject Optimal attack en_US
dc.subject Optimal defense en_US
dc.title A parameterized perspective on protecting elections en_US
dc.type Article en_US
dc.relation.journal Theoretical Computer Science


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account