The bribery problem asks whether there exists an appropriate-“cost” collection of voters in an election such that, if one strategically changes their votes, one’s favored candidate will win. In that model, each voter comes with a “bribery cost” that, if paid, will allow one to completely control the voter’s vote. However, even the paper that initiated the complexity-theoretic study of bribery [1] already realized that not all replacement votes might be equally palatable to the bribed voters. And so it also defined and studied a variant, called microbribery, in which one paid based on how far from the voter’s initial vote the voter was being bribed to. Later papers explored using many other distance notions to define the cost of bribery.

The paper under review, however, studies a case where there separately are costs on the voters, but also each voter has a (or in some cases, all share the same) maximum distance that the voter can be bribed. Within that distance, all votes that the voter might be bribed to are priced the same as each other; beyond it, their cost becomes infinite. Within this setting, the paper proves polynomial-time and NP-completeness results over a range of different election systems and distance notions, often focusing particularly on the case where the maximum distance is set to be one or two.

This interesting paper’s natural audience is the computational social choice community.