Control complexity in Borda elections: Solving all open cases of offline control and some cases of online control

摘要

Borda Count is one of the earliest and most important voting rules and has been central to many applications in artificial intelligence. We study the problem of control in Borda elections where an election chair seeks to either make a designated candidate win (constructive case), or prevent her from winning (destructive case), via actions such as adding, deleting, or partitioning either candidates or voters. These scenarios have been studied for many voting rules and the related control problems have been classified in terms of their computational complexity. However, for one of the most prominent natural voting rules, the Borda Count, complexity results have been known for only half of these cases until recently. We settle the complexity for all missing cases, focusing on the unique-winner model. We also exhibit two of the very rare cases where the complexity of control problems differs depending on the winner model chosen: For destructive control by partition and by run-off partition of candidates when ties promote, Borda is resistant in the unique-winner model (i.e., these two control problems are NP-hard), yet is vulnerable in the nonunique-winner model (i.e., one can decide in polynomial time whether control is possible). Finally, we turn to the model of online control in sequential elections that was recently proposed by Hemaspaandra et al. [62], [61]. We show that sequential Borda elections are vulnerable to constructive and destructive online control by adding or deleting candidates, whereas we obtain coNP-hardness results for all types of online voter control in sequential Borda elections.