Source-linked AI summary
On the Computation of Fully Proportional Representation
Nadja Betzler, Arkadii Slinko, Johannes Uhlmann
TL;DR
The paper asks whether fully proportional representation can be computed efficiently despite known hardness, including under minimax objectives, parameterizations, and structured electorates. It analyzes classical and minimax Chamberlin–Courant and Monroe problems, finding persistent general-case hardness but mostly polynomial-time solvability for single-peaked elections, with classical Monroe remaining NP-hard.
Problem
Winner determination for Chamberlin–Courant and Monroe fully proportional representation is known to be NP-hard, motivating a search for tractable variants, parameters, and electorates.
Method
The paper analyzes sum-minimization and minimax variants using parameterized complexity and algorithms for single-peaked elections.
Results
The minimax variants remain NP-complete in general, while CC-Multiwinner and both minimax variants are polynomial-time solvable for single-peaked elections; classical Monroe remains NP-hard there.
Takeaways & Limitations
Tractability depends strongly on the electoral setting: single-peakedness yields polynomial-time algorithms for most studied problems, whereas general minimax computation remains hard.
Takeaways & Limitations
The single-peakedness assumption may be fragile, and extending the results to generalized or almost single-peaked profiles remains open.
Abstract
from arXiv · showhide
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.
1. Introduction
Multiwinner rules seek assemblies that represent diverse political opinions, motivating fully proportional representation based on voter preferences and misrepresentation. This paper studies the complexity of classical and minimax rules, parameterized settings, and single-peaked electorates.
- Motivation: Multiwinner elections aim to produce assemblies that adequately represent society rather than make a single final decision.Single-winner rules can be extended mechanically, but their majoritarian logic cannot ensure balanced assembly membership.
- Motivation: Fully proportional representation assigns representatives to voters using their preference rankings and measures the resulting misrepresentation.A first-preference representative has zero misrepresentation, while lower-ranked representatives receive nondecreasing penalties s1 ≤ s2 ≤ ... ≤ sm.
- Approach: The paper investigates whether Rawlsian minimax objectives, parameterization, and single-peaked electorates make fully proportional representation computationally tractable.The parameters include the number of winners and the misrepresentation bound, with Borda and approval misrepresentation functions analyzed.
- Models: Chamberlin–Courant allows representatives to represent arbitrary numbers of voters, whereas Monroe requires each representative to represent roughly the same number.These rules address proportional representation through voter-to-candidate assignments rather than only first preferences.
- Results: For general elections, the four considered problems remain computationally difficult in several settings, although some parameterized cases become tractable.In particular, all considered problems are W[2]-hard when parameterized by the number of winners, while Borda variants with constant misrepresentation bound are solvable in XP time.
- Results: For single-peaked elections, CC-Multiwinner and both minimax variants are polynomial-time solvable, while classical Monroe remains NP-hard.The single-peaked Monroe results include polynomial-time solvability for approval misrepresentation, but NP-hardness for an unrestricted integer-valued function.
2. Preliminaries
The preliminaries define parameterized complexity, fixed-parameter tractability, and XP, then introduce the graph structures and algorithms used in the paper.
- A parameterized problem takes a main input and a parameter, often a positive integer or tuple of positive integers.
- Fixed-parameter tractability requires running time f(p) · |x|^O(1), with the non-polynomial dependence confined to the parameter.
- XP permits running time O(|x|^f(p)), which differs from fixed-parameter tractability because the input-size exponent depends on the parameter.
- The paper uses parameterized reductions and W[2]-hardness results, including reductions from the W[2]-complete Hitting Set problem.
- The graph preliminaries define bipartite graphs, matchings, maximum-weight matchings, flow networks, and capacities.
- Maximum-weight bipartite matching and maximum flow can be computed in polynomial time using standard graph algorithms.
3. Basic Results and Observations
The paper establishes equivalences for special misrepresentation settings and gives fixed-parameter algorithms for all four problems when voters or candidates are few.
- For R = 0, each minimax problem coincides with its corresponding classical problem.
- Minimax instances with arbitrary misrepresentation functions reduce to equivalent approval instances by replacing values above R with 1 and all others with 0.The transformed threshold is R′ := 0.
- Algorithms and hardness results transfer between general and approval misrepresentation functions for the minimax versions under the stated reductions.
- All four problems are fixed-parameter tractable by the number of voters and by the number of candidates.The algorithms combine brute-force search with matching, maximum flow, and related techniques.
- Number of voters: The voter-parameter algorithm enumerates voter partitions and uses matching to select candidates representing the partition blocks.
- Number of candidates: For the candidate parameter, CC variants enumerate candidate subsets, while Monroe variants use network flow to enforce balanced assignments.
4. The Number of Winners and the Misrepresentation Bound as Parameters
The number of winners is a hard parameter, while the misrepresentation bound yields different outcomes for approval and Borda functions, including tractability for constant Borda bounds.
- Number of winners: All four problems are W[2]-hard when parameterized by the number k of winners.For approval misrepresentation, this holds even when R = 0; the Borda reduction does not hold for R = 0.
- Number of winners: The hardness proofs reduce Hitting Set to winner-selection instances, with zero-cost or bounded-cost representations encoding whether selected candidates hit every set.
- Misrepresentation bound: The Borda hardness constructions use thresholds such as z = nmk for sum minimization and R := m −1 for minimax formulations.
- Misrepresentation bound: For Borda misrepresentation, the classical CC and Monroe problems are polynomial-time solvable when the total misrepresentation bound R is constant.
- Misrepresentation bound: For Borda minimax variants, R = 0 is polynomial-time solvable, whereas every R ≥1 yields NP-hardness.
15 end
The composite parameter (R, k) makes all four Borda problems fixed-parameter tractable, using branching or structural restrictions on candidate sets and assignments.
- All four considered Borda problems are fixed-parameter tractable with respect to the composite parameter (R, k).
- CC variants: For Minimax CC-MW, branching tries candidates representing a chosen voter within bound R, deletes covered voters, and decreases k recursively.
- CC variants: The CC branching algorithm explores at most (R + 1)^k possibilities for the minimax problem.
- CC variants: For CC-MW, recursion decreases the remaining misrepresentation budget or increases the selected-candidate set, yielding time (R+1)^(R+k) · poly(n, m).
- Monroe variants: The zero-candidate argument does not transfer directly from Monroe to Minimax Monroe because the Monroe criterion may prevent assigning a voter to her best alternative.
- Monroe variants: For Borda M-MW, at most R + k zero-candidates can occur in a yes-instance.
- Monroe variants: If n > (R + 1)k, every size-k Monroe winner set consists of zero-candidates, enabling candidate reduction and fixed-parameter tractability.
5. Single-Peaked Elections
Single-peaked preferences are organized around a societal axis, producing single-troughed voter misrepresentation functions. This structure enables polynomial-time algorithms for most considered rules, although classical Monroe remains NP-hard.
- Definition: Single-peakedness means every voter’s preferences are compatible with one societal order over candidates.
- Misrepresentation structure: For each voter, misrepresentation decreases toward the bliss point and increases afterward along the societal axis.
- Overall results: Among the considered single-peaked problems, classical Monroe is NP-hard, while approval-based Monroe remains polynomial-time solvable.
- CC-Multiwinner: CC-Multiwinner is solvable in polynomial time for arbitrary misrepresentation functions using dynamic programming.
- Minimax CC-Multiwinner: Minimax CC-Multiwinner is also polynomial-time solvable for arbitrary misrepresentation functions through a greedy algorithm.
- CC-Multiwinner: Theorem 8 gives an O(nm^2)-time algorithm for CC-Multiwinner on single-peaked profiles.
17 end
The algorithms exploit dynamic programming, interval stabbing, and representation ranges to solve several single-peaked winner-determination problems efficiently. The main negative result is NP-hardness for classical Monroe, while approval and minimax variants admit polynomial-time procedures.
- CC dynamic programming: The CC dynamic program stores the minimum total misrepresentation for j winners chosen from an initial candidate prefix and including the latest candidate.
- CC dynamic programming: An optimal k-winner solution is obtained by minimizing z(i, k) over i from k through m.
- CC dynamic programming: The CC algorithm runs in O(nm^2) time.
- Minimax CC: Minimax CC selects candidates greedily by covering voters’ consecutive representation ranges along the societal axis.
- Minimax CC: Minimax CC-Multiwinner is solvable in O(nm) time for single-peaked profiles and arbitrary misrepresentation functions.
- Monroe variants: M-Multiwinner is NP-hard even for single-peaked profiles, but approval M-Multiwinner and arbitrary-function Minimax M-Multiwinner are polynomial-time solvable.
- Rectangle stabbing: When n mod k = 0 and the misrepresentation bound is R = 0, M-Multiwinner reduces to Hard-1-RS and is solvable in O(n^2m^2(n + m)) time.
- Rectangle stabbing: Approval M-Multiwinner is reduced to maximum balanced one-dimensional rectangle stabbing, solvable in O(m^3n^3k^3) time.
38 end
The rectangle-stabbing dynamic program uses an update step that scans candidate intervals in increasing order of interval length.
- Algorithm 3 updates the dynamic program by considering all intervals [x1, x2] in increasing order of x2 − x1.
14 end
The section establishes dynamic-programming correctness and polynomial running time for several single-peaked M-Multiwinner variants, while proving NP-hardness for the general M-Multiwinner problem under restricted conditions.
- Algorithm and correctness: The dynamic program initializes partial solutions covering an interval and respecting winner capacities and assignment constraints.Initialization stores the maximum value for a solution containing x1, while satisfying conditions (C1)–(C6).
- Algorithm and correctness: Algorithm 3 systematically considers whether the leftmost solution line covers the current interval, including cases with remaining capacity and capacity one.It also tests new solution lines and leftmost intervals, combining optimal left and right subinstances.
- Algorithm and correctness: The table is evaluated in an order ensuring that every accessed entry has already been computed, including entries with smaller ranges or capacities.The algorithm iterates over capacities in increasing order and ranges by increasing size.
- Polynomial-time results: O(n3m3k3) time solves M-Multiwinner with approval misrepresentation and single-peaked profiles.Theorem 10 gives this bound for the approval misrepresentation function.
- Polynomial-time results: O(n3m3k3) time solves Minimax M-Multiwinner for single-peaked profiles with an arbitrary misrepresentation function.This proposition extends the same polynomial bound to the minimax variant.
- NP-hardness result: M-Multiwinner remains NP-hard for single-peaked profiles with integer-valued misrepresentation functions, even when maximum voter misrepresentation is polynomial and every winner represents exactly three voters.The reduction uses an exact 3-cover instance and establishes the equivalence between exact covers and feasible winning sets.
6. Conclusion and Outlook
The paper seeks efficient settings for fully proportional representation despite general computational hardness. It reports mixed parameterized results, mostly positive results for single-peaked elections, and several directions for extending the analysis.
- Relevance of Results: The study addresses whether fully proportional representation can be made practical despite NP-hard winner-determination problems.It examines parameter restrictions, single-peaked domains, and related models as routes to efficient computation.
- Relevance of Results: Minimax misrepresentation does not remove computational hardness in general, but it makes single-peaked Minimax Monroe solvable in polynomial time.The classical Monroe scheme remains NP-hard on single-peaked elections.
- Relevance of Results: For the number of winners, the four studied problems are W[2]-complete, while additional structure and parameters yield tractability for some Borda cases.Three of four problems become tractable when a winner set has small total misrepresentation, and fixed-parameter tractability holds for the numbers of voters and candidates in restricted settings.
- Relevance of Results: Almost all single-peaked-election results are positive and accompanied by polynomial-time algorithms.The authors identify near single-peakedness as a possible direction for extending these algorithms beyond the exact domain restriction.
- Outlook: The paper also relates multiwinner representation to facility location and proposes a multiset-of-candidates model between Chamberlin–Courant and Monroe.The multiset model permits one candidate to represent multiple equal-sized voter groups, potentially yielding zero misrepresentation where a set solution does not.
- Open Questions: Extending the single-peaked results to generalized or almost single-peaked profiles remains an open question.The authors specifically connect this question to the complexity of finding a closest single-peaked profile.