A parameterized perspective on attacking and defending elections

Show simple item record

dc.contributor.author Gowda, Kishen N.
dc.contributor.author Misra, Neeldhara
dc.contributor.author Patel, Vraj
dc.date.accessioned 2020-05-21T10:45:25Z
dc.date.available 2020-05-21T10:45:25Z
dc.date.issued 2020-05
dc.identifier.citation Gowda, Kishen N.; Misra, Neeldhara and Patel, Vraj, "A parameterized perspective on attacking and defending elections", arXiv, Cornell University Library, DOI: arXiv:/2005.03176, May 2020. en_US
dc.identifier.uri http://arxiv.org/abs/2005.03176
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/5414
dc.description.abstract We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the problem formulations are based on the model proposed recently by~[Elkind et al, IJCAI 2019]. It turns out that both of the manipulation and protection problems are NP-complete even in fairly simple settings. We study these problems from a parameterized perspective with the goal of establishing a more detailed complexity landscape. The parameters we consider include the number of voters, and the budgets of the attacker and the defender. While we observe fixed-parameter tractability when parameterizing by number of voters, our main contribution is a demonstration of parameterized hardness when working with the budgets of the attacker and the defender.
dc.description.statementofresponsibility by Kishen N. Gowda, Neeldhara Misra and Vraj Patel
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title A parameterized perspective on attacking and defending elections en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv

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


My Account