Structured proportional representation

Multi-winner voting rules aiming at proportional representation,1 such as those suggested by Chamberlin and Courant [2] and by Monroe [5], partition an electorate into virtual districts, such that a representative is assigned to each district; these districts are formed based on the voters' pre...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2018-01, Vol.708, p.58-74
Main Author: Talmon, Nimrod
Format: Article
Language:English
Subjects:
Graph algorithms
Multiwinner elections
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multi-winner voting rules aiming at proportional representation,1 such as those suggested by Chamberlin and Courant [2] and by Monroe [5], partition an electorate into virtual districts, such that a representative is assigned to each district; these districts are formed based on the voters' preferences. In some applications it is beneficial to require certain structural properties to be satisfied by these virtual districts. In this paper we consider situations where the voters are embedded in a network, modeled as an undirected graph, and we require the virtual districts to satisfy certain structural properties with respect to this network. Specifically, we consider two structural properties, corresponding to two different combinatorial problems: in the first problem, we require each virtual district to be connected, while in the second problem, we require the diameter of each virtual district to be small. We discuss applications of these combinatorial problems and study their computational complexity, identifying several variants and special cases which can be solved efficiently.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.10.028