  Bribery in elections is an important problem in computational social choice
theory. However, bribery with money is often illegal in elections. Motivated by
this, we introduce the notion of frugal bribery and formulate two new pertinent
computational problems which we call Frugal-bribery and Frugal- $bribery to
capture bribery without money in elections. In the proposed model, the briber
is frugal in nature and this is captured by her inability to bribe votes of a
certain kind, namely, non-vulnerable votes. In the Frugal-bribery problem, the
goal is to make a certain candidate win the election by changing only
vulnerable votes. In the Frugal-{dollar}bribery problem, the vulnerable votes
have prices and the goal is to make a certain candidate win the election by
changing only vulnerable votes, subject to a budget constraint of the briber.
We further formulate two natural variants of the Frugal-{dollar}bribery problem
namely Uniform-frugal-{dollar}bribery and Nonuniform-frugal-{dollar}bribery
where the prices of the vulnerable votes are, respectively, all the same or
different.
  We study the computational complexity of the above problems for unweighted
and weighted elections for several commonly used voting rules. We observe that,
even if we have only a small number of candidates, the problems are intractable
for all voting rules studied here for weighted elections, with the sole
exception of the Frugal-bribery problem for the plurality voting rule. In
contrast, we have polynomial time algorithms for the Frugal-bribery problem for
plurality, veto, k-approval, k-veto, and plurality with runoff voting rules for
unweighted elections. However, the Frugal-{dollar}bribery problem is
intractable for all the voting rules studied here barring the plurality and the
veto voting rules for unweighted elections.
