Total: 1
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.IntheFRUGAL−BRIBERYproblem,thegoalistomakeacertaincandidatewintheelectionbychangingonlythevulnerablevotes.IntheFRUGAL−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 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.