Optimal algorithms for multiwinner elections and the Chamberlin–Courant Rule

Kamesh Munagala (), Zeyu Shen () and Kangning Wang ()
Additional contact information
Kamesh Munagala: Duke University
Zeyu Shen: Princeton University
Kangning Wang: Rutgers University

Social Choice and Welfare, 2025, vol. 64, issue 1, No 6, 143-178

Abstract: Abstract We consider the algorithmic question of choosing a subset of candidates of a given size k from a set of m candidates, with knowledge of voters’ ordinal rankings over all candidates. We consider the well-known and classic scoring rule for achieving diverse representation: the Chamberlin–Courant (CC) or 1-Borda rule, where the score of a committee is the average over the voters, of the rank of the best candidate in the committee for that voter; and its generalization to the average of the top s best candidates, called the s-Borda rule. Our first result is an improved analysis of the natural and well-studied greedy heuristic. We show that greedy achieves a $$\left( 1 - \frac{2}{k+1}\right) $$ 1 - 2 k + 1 -approximation to the maximization (or satisfaction) version of CC rule, and a $$\left( 1 - \frac{2\,s}{k+1}\right) $$ 1 - 2 s k + 1 -approximation to the s-Borda score. This significantly improves the existing submodularity-based analysis of the greedy algorithm that only shows a $$(1-1/e)$$ ( 1 - 1 / e ) -approximation. Our result also improves on the best known approximation algorithm for this problem. We achieve this result by showing that the average dissatisfaction score for the greedy algorithm is at most $$2\cdot \frac{m+1}{k+1}$$ 2 · m + 1 k + 1 for the CC rule, and at most $$2\,s^2 \cdot \frac{m+1}{k+1}$$ 2 s 2 · m + 1 k + 1 for s-Borda. We show these dissatisfaction score bounds are tight up to constants, and even the constant factor of 2 in the case of the CC rule is almost tight. For the dissatisfaction (or minimization) version of the problem, it is known that the average dissatisfaction score of the best committee cannot be approximated in polynomial time to within any constant factor when s is a constant (under standard computational complexity assumptions). As our next result, we strengthen this to show that the score of $$\frac{m+1}{k+1}$$ m + 1 k + 1 can be viewed as an optimal benchmark for the CC rule, in the sense that it is essentially the best achievable score of any polynomial-time algorithm even when the optimal score is a polynomial factor smaller. We show that another well-studied algorithm for this problem, called the Banzhaf rule, attains this benchmark. We finally show that for the s-Borda rule, when the optimal value is small, these algorithms can be improved by a factor of $$\tilde{\Omega }(\sqrt{s})$$ Ω ~ ( s ) via LP rounding. Our upper and lower bounds are a significant improvement over previous results, and taken together, not only enable us to perform a finer comparison of greedy algorithms for these problems, but also provide analytic justification for using such algorithms in practice.

Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00355-024-01555-w 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:sochwe:v:64:y:2025:i:1:d:10.1007_s00355-024-01555-w

Ordering information: This journal article can be ordered from
http://www.springer. ... c+theory/journal/355

DOI: 10.1007/s00355-024-01555-w

Access Statistics for this article

Social Choice and Welfare is currently edited by Bhaskar Dutta, Marc Fleurbaey, Elizabeth Maggie Penn and Clemens Puppe

More articles in Social Choice and Welfare from Springer, The Society for Social Choice and Welfare Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().