Speaker:     Arkadii Slinko

Affiliation: Department of Mathematics

Title:       Approximation Algorithms for Fully Proportional Representation by Clustering Voters

Date:        Wednesday, 9 Dec 2015

Time:        12:00 pm

Location:    303-561

Charles Dodgson (Lewis Carroll) asserted that “a representation system should find the coalitions in the election that would have formed if the voters had the necessary time and information … and allow each of the coalitions to elect their representative using some single-winner voting method.”

Both the Chamberlin-Courant and Monroe voting rules do exactly that. Given the preferences of voters, they select committees whose members represent the voters so that voters’ satisfaction with their assigned representatives is maximised. These rules suffer from a common disadvantage, being computationally intractable to compute the winning committee exactly when the numbers get large. As both of these rules, explicitly or implicitly, partition voters, they can be seen as clustering of voters so that the voters in each group share the same representative.This suggest studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. We develop several such algorithms and experimentally analyse their performance.

Joint work with Piotr Faliszewski and Nimrod Talmon.

Everyone welcome!