  Studying complexity of various bribery problems has been one of the main
research focus in computational social choice. In all the models of bribery
studied so far, the briber has to pay every voter some amount of money
depending on what the briber wants the voter to report and the briber has some
budget at her disposal. Although these models successfully capture many real
world applications, in many other scenarios, the voters may be unwilling to
deviate too much from their true preferences. In this paper, we study the
computational complexity of the problem of finding a preference profile which
is as close to the true preference profile as possible and still achieves the
briber's goal subject to budget constraints. We call this problem Optimal
Bribery. We consider three important measures of distances, namely, swap
distance, footrule distance, and maximum displacement distance, and resolve the
complexity of the optimal bribery problem for many common voting rules. We show
that the problem is polynomial time solvable for the plurality and veto voting
rules for all the three measures of distance. On the other hand, we prove that
the problem is NP-complete for a class of scoring rules which includes the
Borda voting rule, maximin, Copeland$^\alpha$ for any $\alpha\in[0,1]$, and
Bucklin voting rules for all the three measures of distance even when the
distance allowed per voter is $1$ for the swap and maximum displacement
distances and $2$ for the footrule distance even without the budget constraints
(which corresponds to having an infinite budget). For the $k$-approval voting
rule for any constant $k>1$ and the simplified Bucklin voting rule, we show
that the problem is NP-complete for the swap distance even when the distance
allowed is $2$ and for the footrule distance even when the distance allowed is
$4$ even without the budget constraints.
