Nanson's and Baldwin's voting rules selecta winner by successively eliminatingcandidates with low Borda scores. We showthat these rules have a number of desirablecomputational properties. In particular,with unweighted votes, it isNP-hard to manipulate either rule with one manipulator, whilstwith weighted votes, it isNP-hard to manipulate either rule with a small number ofcandidates and a coalition of manipulators.As only a couple of other voting rulesare known to be NP-hard to manipulatewith a single manipulator, Nanson'sand Baldwin's rules appearto be particularly resistant to manipulation from a theoretical perspective.We also propose a number of approximation methodsfor manipulating these two rules.Experiments demonstrate that both rules areoften difficult to manipulate in practice.These results suggest that elimination stylevoting rules deserve further study.
We study the problem of coalitional manipulation---where k manipulators try to manipulate an election on m candidates---for any scoring rule, with focus on the Borda protocol. We do so in both the weighted and unweighted settings. For these problems, recent approximation approaches have tried to minimize k, the number of manipulators needed to make some preferred candidate p win (thus assuming that the number of manipulators is not limited in advance). In contrast, we focus on minimizing the score margin of p which is the difference between the maximum score of a candidate and the score of p. We provide algorithms that approximate the optimum score margin, which are applicable to any scoring rule.
Davies, Jessica (University of Toronto) | Katsirelos, George (LRI, Universite Paris Sud 11) | Narodytska, Nina (NICTA and University of New South Wales) | Walsh, Toby (NICTA and University of New South Wales)
We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.
We study the problem of coalitional manipulation in elections using the unweighted Borda rule. We provide empirical evidence of the manipulability of Borda elections in the form of two new greedy manipulation algorithms based on intuitions from the bin-packing and multiprocessor scheduling domains. Although we have not been able to show that these algorithms beat existing methods in the worst-case, our empirical evaluation shows that they significantly outperform the existing method and are able to find optimal manipulations in the vast majority of the randomly generated elections that we tested. These empirical results provide further evidence that the Borda rule provides little defense against coalitional manipulation.
We propose a simple method for combining together voting rules that performs a run-off between the different winners of each voting rule. We prove that this combinator has several good properties. For instance, even if just one of the base voting rules has a desirable property like Condorcet consistency, the combination inherits this property. In addition, we prove that combining voting rules together in this way can make finding a manipulation more computationally difficult. Finally, we study the impact of this combinator on approximation methods that find close to optimal manipulations.