10128@AAAI

Total: 1

#1 Frugal Bribery in Voting [PDF] [Copy] [Kimi] [REL]

Authors: Palash Dey, Neeldhara Misra, Y. Narahari

Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the bribery problem, namely, FRUGAL-BRIBERY and FRUGAL-BRIBERYwherethebriberisfrugalinnature.Bythis,wemeanthatthebriberisonlyabletoinfluencevoterswhobenefitfromthesuggestionofthebriber.Moreformally,avoterisvulnerableiftheoutcomeoftheelectionimprovesaccordingtoherownpreferencewhensheacceptsthesuggestionofthebriber.IntheFRUGALBRIBERYproblem,thegoalistomakeacertaincandidatewintheelectionbychangingonlythevulnerablevotes.IntheFRUGALBRIBERY 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 show that both the FRUGAL-BRIBERY and the FRUGAL-$BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections. These intractability results demonstrate that bribery is a hard computational problem, in the sense that several special cases of this problem continue to be computationally intractable. This strengthens the view that bribery, although a possible attack on an election in principle, may be infeasible in practice.

Subject: AAAI.2016 - Multiagent Systems