- CARMA SEMINAR
- Speaker: Nina Narodytska
- Title: Complexity of and Algorithms for Borda Manipulation
- Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
- Time and Date: 3:00 pm, Tue, 10th Jan 2012
We prove the 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 also consider Nanson’s and Baldwin’s voting rules that
select a winner by successively eliminating candidates with low
Borda scores. We theoretically and experimentally
demonstrate that these rules are significantly
more difficult to manipulate compared to Borda rule.
In particular, with unweighted votes, it
is NP-hard to manipulate either rule with one manipulator,
whilst with weighted votes, it is NP-hard to manipulate either
rule with a small number of candidates and a coalition of manipulators.
- [Permanent link]