"Approximability and Inapproximability of Dodgson and Young Elections"

Speaker: Ariel Procaccia
Date: Wednesday, 9 January 2008
Time: 2:30pm
Place: Ross 201

Abstract:

The voting rules proposed by Dodgson and Young are both designed to
find the candidate closest to being a Condorcet winner, according to
two different notions of proximity; the score of a given candidate is
known to be hard to compute under both rules. In this paper, we put
forward an LP-based randomized rounding algorithm which yields an
O(log m) approximation ratio for the Dodgson score, where m is the
number of candidates. Surprisingly, we show that the seemingly simpler
Young score is NP-hard to approximate by any factor.

Joint work with Michal Feldman and Jeffrey S. Rosenschein.