Speaker: Nadja Betzler
Affiliation: Technical University of Berlin
Title: Parameterized algorithmics for Kemeny’s voting system
Date: Tuesday, 1 Mar 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

Kemeny’s voting system is concerned with optimally aggregating a multiset of preference lists into a consensus list. We study the parameterized complexity of the underlying decision problem, called Kemeny Score, with respect to several different parameterizations.This includes a discussion about the relevance and motivation of the parameterizations illustrating the usefulness of a multivariate complexity analysis for voting problems.
We further extend this study by introducing the concept of “partial kernelization”. Based on this, we devise an additional result for the parameter measuring the average distance between pairs of input votes. Moreover, the partial kernelization concept naturally leads to additional parameterizations. Finally, we provide experimental results for computing optimal Kemeny rankings based on some of the previously introduced methods.