Achieving fully proportional representation by clustering voters

Piotr Faliszewski (), Arkadii Slinko (), Kolja Stahl () and Nimrod Talmon ()
Additional contact information
Piotr Faliszewski: AGH University
Arkadii Slinko: University of Auckland
Kolja Stahl: TU Berlin
Nimrod Talmon: Ben-Gurion University

Journal of Heuristics, 2018, vol. 24, issue 5, No 2, 725-756

Abstract: Abstract Both the Chamberlin–Courant and Monroe rules are voting rules that solve the problem of fully proportional representation: given a set of candidates and a set of voters, they select committees of candidates whose members represent the voters so that the voters’ total dissatisfaction is minimized. These two rules suffer from a common disadvantage, namely being computationally intractable. As both the Chamberlin–Courant and Monroe rules, explicitly or implicitly, partition voters so that the voters in each part share the same representative, they can be seen as clustering algorithms. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. Using ideas from cluster analysis we develop several approximation algorithms for the Chamberlin–Courant and Monroe rules and experimentally analyze their performance. We find that our algorithms are computationally efficient and, in many cases, are able to provide solutions which are very close to optimal.

Keywords: Multiwinner elections; Voting; Fully proportional representation; Clustering (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9376-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:24:y:2018:i:5:d:10.1007_s10732-018-9376-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9376-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().