Frugal bribery in voting

Show simple item record

dc.contributor.author Dey, Palash
dc.contributor.author Misra, Neeldhara
dc.contributor.author Narahari, Y.
dc.date.accessioned 2017-04-15T19:13:28Z
dc.date.available 2017-04-15T19:13:28Z
dc.date.issued 2017-05
dc.identifier.citation Dey, Palash; Misra, Neeldhara and Narahari, Y., “Frugal bribery in voting”, Theoretical Computer Science, DOI: 10.1016/j.tcs.2017.02.031, vol. 676, pp. 15-32, Mar. 2017. en_US
dc.identifier.citation Dey, Palash; Misra, Neeldhara and Narahari, Y., “Frugal bribery in voting”, Theoretical Computer Science, DOI: 10.1016/j.tcs.2017.02.031, vol. 676, pp. 15-32, May 2017.
dc.identifier.issn 0304-3975
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2841
dc.identifier.uri http://doi.org/10.1016/j.tcs.2017.02.031
dc.description.abstract Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the classical $Bribery problem, namely, Frugal-bribery and Frugal-$bribery where the briber is frugal in nature. By this, we mean that the briber is only able to influence voters who benefit from the suggestion of the briber. More formally, a voter is vulnerable if the outcome of the election improves according to her own preference when she accepts the suggestion of the briber. In the Frugal-bribery problem, the goal is to make a certain candidate win the election by changing only the vulnerable votes. In the Frugal-$bribery problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only the vulnerable votes, subject to a budget constraint. We further formulate two natural variants of the Frugal-$bribery problem namely Uniform-frugal-$bribery and Nonuniform-frugal-$bribery where the prices of the vulnerable votes are, respectively, all the same or different. The Frugal-bribery problem turns out to be a special case of sophisticated $Bribery as well as Swap-bribery problems. Whereas the Frugal-$bribery problem turns out to be a special case of the $Bribery problem. We show that the Frugal-bribery problem is polynomial time solvable for the k-approval, k-veto, and plurality with run off voting rules for unweighted elections. These results establish success in finding practically appealing as well as polynomial time solvable special cases of the sophisticated $Bribery and Swap-bribery problems. On the other hand, we show that the Frugal-bribery problem is NP-complete for the Borda voting rule and the Frugal-$bribery problem is NP-complete for most of the voting rules studied here barring the plurality and the veto voting rules for unweighted elections. Our hardness results of the Frugal-bribery and the Frugal-$bribery problems thus subsumes and strengthens the hardness results of the $Bribery problem from the literature. For the weighted elections, we show that the Frugal-bribery problem is NP-complete for all the voting rules studied here except the plurality voting rule even when the number of candidates is as low as 3 (for the STV and the plurality with run off voting rules) or 4 (for the maximin, the Copelandα with α∈[0,1), and the simplified Bucklin voting rules). In our view, the fact that the simplest Frugal-bribery problem becomes computationally intractable for many important voting rules (except the plurality voting rule) even with very few candidates is surprising as well as interesting. en_US
dc.description.statementofresponsibility by Palash Dey, Neeldhara Misra and Y. Narahari
dc.format.extent Vol. 676, pp. 15-32
dc.language.iso en_US en_US
dc.publisher Elsevier en_US
dc.subject Computational social choice en_US
dc.subject Voting; Bribery en_US
dc.subject Frugal en_US
dc.subject Manipulation en_US
dc.subject Algorithm en_US
dc.subject Theory en_US
dc.title Frugal bribery in voting 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