you're reading...

Complexity of and Algorithms for Borda Manipulation – Nina Narodytska

This Friday (19/8) Nina Norodytska from UNSW is giving a talk in our seminar. She’ll present her work on complexity and algorithmic results for manipulating voting systems.

Title: Complexity of and Algorithms for Borda Manipulation

Abstract: 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.




  1. Pingback: Assorted Links | David Cerezo Sánchez - October 3, 2011

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: