Between Proportionality and Diversity: Balancing District Sizes under the Chamberlin-Courant Rule
P. Faliszewski, N. Talmon
AAMAS 2018
Abstract
The Monroe and Chamberlin--Courant (CC) multiwinner rules proceed by partitioning the voters into virtual districts and assigning a unique committee member to each district, so that the voters are as satisfied with the assignment as possible. The difference between Monroe and CC is that the former creates equal-sized districts, while the latter has no constraints. We generalize these rules by requiring that the largest district can be at most X times larger than the smallest one (where X is a parameter). We show that our new rules inherit worst-case computational properties from their ancestors; evaluate the rules experimentally (in particular, we provide their visualizations, analyze actual district sizes and voter satisfaction); and analyze their approximability.
Experiments:
| Election type |
Culture |
Candidates |
Voters |
Instances |
Parameters |
| Ordinal |
Euclidean 2D |
{100} |
{100} |
5000 |
Specific(Uniform 2D Sphere, Gaussian 2D); Specific(Gaussian 2D); Uniform 2D Sphere ($(0,0)$ $r=3$); Uniform 2D ($[-3, 3]^2$) |
| Ordinal |
Impartial Culture |
{100} |
{100} |
500 |
None |
| Ordinal |
Urn Model |
{100} |
{100} |
500 |
{0, 0.05, 0.10, 0.25, 0.5, 1} |
| Ordinal |
Euclidean 2D |
{100} |
{100} |
500 |
Specific(Uniform 2D Sphere, Gaussian 2D); Specific(Gaussian 2D); Uniform 2D Sphere ($(0,0)$ $r=3$); Uniform 2D ($[-3, 3]^2$) |