Structured Proportional Representation

Multi-winner voting rules aiming at proportional representation, such as those suggested by Chamberlin and Courant [9] and by Monroe [20], 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, and we require each virtual district to be connected (with respect to the network). We discuss applications of a corresponding combinatorial problem and study its computational complexity, identifying several variants and special cases which can be solved efficiently. CCS Concepts •Computing methodologies → Multi-agent systems; •Theory of computation → Problems, reductions and completeness; Keywords multiwinner elections; graph algorithms; treewidth 1 These are called virtual districts as they resemble electoral districts, but are based on preferences and not on geography.