Election with Bribed Voter Uncertainty: Hardness and Approximation Algorithm
This addresses a novel variant of election bribery for computational social choice, but it is incremental as it builds on classic bribery problems.
The paper tackles the problem of election bribery with uncertainty in whether bribed voters' votes are counted, showing that no constant-factor multiplicative approximation algorithm exists under standard complexity assumptions, and provides an additive-ε approximation algorithm with fixed-parameter tractable time.
Bribery in election (or computational social choice in general) is an important problem that has received a considerable amount of attention. In the classic bribery problem, the briber (or attacker) bribes some voters in attempting to make the briber's designated candidate win an election. In this paper, we introduce a novel variant of the bribery problem, "Election with Bribed Voter Uncertainty" or BVU for short, accommodating the uncertainty that the vote of a bribed voter may or may not be counted. This uncertainty occurs either because a bribed voter may not cast its vote in fear of being caught, or because a bribed voter is indeed caught and therefore its vote is discarded. As a first step towards ultimately understanding and addressing this important problem, we show that it does not admit any multiplicative $O(1)$-approximation algorithm modulo standard complexity assumptions. We further show that there is an approximation algorithm that returns a solution with an additive-$ε$ error in FPT time for any fixed $ε$.