In:
Proceedings of the AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence (AAAI), Vol. 33, No. 01 ( 2019-07-17), p. 2572-2579
Abstract:
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 ε.
Type of Medium:
Online Resource
ISSN:
2374-3468
,
2159-5399
DOI:
10.1609/aaai.v33i01.33012572
Language:
Unknown
Publisher:
Association for the Advancement of Artificial Intelligence (AAAI)
Publication Date:
2019
Permalink
