 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, 10^{th} Jan 2012
 Abstract:
We prove the it is NPhard 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 NPhardness, 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 NPhard, 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 NPhard to manipulate either rule with one manipulator,
whilst with weighted votes, it is NPhard to manipulate either
rule with a small number of candidates and a coalition of manipulators.
 [Permanent link]
