Diverse Representation in Approval-Based Committee Voting

Davide Grossi; Feline Lindeboom; Jan Maly; Julian Chingoma

REVIEW

Diverse Representation in Approval-Based Committee Voting

Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly

Computer Science and Game Theory · Submitted 24 Sep 2026

Pith's verdict: New DR axioms and the CI-domain tractability hold up, but the SSJR greedy guarantee is wrong — the union-containment objective is supermodular, and a 10-voter instance gives greedy ratio 2/9.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 25, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.29332 (version 2)

Pith IDJWC23ALW, Pith's permanent record of this paper and its review

CitationDavide Grossi, Feline Lindeboom, Jan Maly, Julian Chingoma. "Diverse Representation in Approval-Based Committee Voting." arXiv:2609.29332 (2026). https://pith.science/paper/JWC23ALW

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper's real contribution is the DR/Local DR half and the CI-domain tractability, and those mostly hold up. But the headline claim that greedy achieves a 1−1/e ratio for SSJR (Theorem 18) is false, and Theorem 17's hardness transfer needs a condition the paper never states. This is a major revision, not a polish.

What is genuinely new and good: the Distinctive Representation axiom (Definition 22), the X3C NP-hardness reduction (Theorem 26), the Local DR swap algorithm with its termination argument (Props 28–29), and the clean separation of DR/Local DR from EJR, PJR, BJR, priceability, and Monroe/CC (Theorems 30, 31, 33). The CI-domain result (Theorem 20), reducing (S)SJR to interval max-coverage via Cohen–Gonen, is real and worth having, and the FPT candidate-deletion set (Theorem 21) is a sensible follow-on. The decision-complexity reduction for SSJR (Theorem 15) is structurally sound: the +k shift from the elected candidates is handled honestly by setting f(t)=t+k and adding unique per-candidate dummy voters. The logical map in Theorem 11/Figure 1 is a useful reference. The axiomatic side is self-contained and careful.

The load-bearing flaw is Theorem 18. The proof says the pigeonhole argument transfers to SSJR 'by the same... argument.' It transfers to SJR — there each elected candidate covers exactly the candidates it contains, so the score is a coverage function and greedy 1−1/e is standard. SSJR is different: c counts only if its support N_c is contained in the union of elected supports, and the union can satisfy the containment when no single elected candidate does. That function counts contained subsets, its marginals grow as the union grows, and it is not submodular. Concrete counterexample with n=10, k=2, threshold 5: N_a={1,...,7}, N_b={3,...,6,8}, N_c={3,...,6,10}, plus seven further cohesive candidates each supported by N_b∪N_c. With ties breaking toward a, greedy returns score 2/10; {b,c} scores 9/10. Ratio 2/9. So Theorem 18 as stated fails for SSJR, and the Section 8.1 framing that the greedy rules run 'far above the theoretical worst case bound of 1−1/e' rests, for SSJR, on a guarantee Algorithm 1 does not have.

Secondary issues, fixable: Theorem 17 converts the additive-k reduction into inapproximability by taking k=o(n), but it needs the hard max-coverage instances to have optimum near n, a condition not stated. Corollary 16 derives SJR-hardness from SSJR via 'any solution for SJR is also a solution for SSJR,' which is a property, not a reduction in the direction needed — the SJR-hardness is probably recoverable through a variant of the same construction, but the given argument does not do it. Experiments report means without error bars and release no code or data; the 'unique candidate/voter' measures are ad hoc and should not be over-read.

Bottom line: this is computational social choice work with a genuinely useful new axiom and a real interval-domain result. It deserves a serious referee. Send it out, but the referee should require the SSJR greedy claim to be cut to SJR (or fixed), the experiments reframed accordingly, and the hardness statements tightened.

Referee report

Significance

If valid, a tight (1−1/e) barrier for (S)SJR optimization, CI-domain tractability, and a provably hard new diversity axiom would each be substantial contributions to ABC voting; the paper also ships a careful experimental study. Creditable elements: the SSJR decision NP-completeness reduction (Theorem 15) is coherent; the Local DR search algorithm (Proposition 28) has a genuine termination argument; the comparison with BJR and Monroe (Theorems 30, 33, Proposition 31) is informative. However, the manuscript contains no machine-checked proofs, and its two marquee results fail on inspection: Theorem 18's SSJR claim is contradicted by an explicit 10-voter instance (greedy ratio 4/9 < 1−1/e), and Theorem 26's reduction is vacuous because mixed committees satisfy DR even in no-instances of X3C. These are load-bearing errors, not presentation defects, and they cannot be repaired by local edits: the SSJR (1−1/e) statement is outright false, and the DR hardness proof requires a new construction.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Diverse representation in committees, defined through cohesive voter groups, cannot be approximated within a factor better than $1-1/e$ on general approval profiles unless P=NP, yet becomes exactly solvable when candidates admit an…

The reading

This paper builds a theory of diverse representation in approval-based committee elections that treats voters as members of cohesive groups rather than as isolated individuals. Its central results are boundary results: maximizing the Strong JR and Semi-Strong JR scores cannot be approximated within a factor better than $1-1/e$ by any polynomial-time algorithm unless P=NP, yet both maximization problems become exactly solvable when each voter's approved candidates form an interval in a fixed ordering of the candidates. The paper also introduces Distinctive Representation, a new axiom requiring every elected candidate to be supported by exactly $\lceil n/k \rceil$ voters, shows its decision problem is NP-hard, and provides a polynomial-time local-search variant. Experiments on real and synthetic election data indicate that the worst-case $1-1/e$ bound is rarely binding: the greedy rules and local search return near-optimal committees on the tested instances.

What carries the argument

The load-bearing objects are the SJR and SSJR scores, which count the fraction of cohesive candidates (those with at least $n/k$ supporters) that a committee fully represents — SJR requiring one elected candidate approved by all group members, SSJR requiring every group member to be represented by some elected candidate. The arguments ride on two reductions. NP-hardness of (S)SJR comes from reducing the Chamberlin–Courant (max $k$-coverage) decision problem by turning each voter into a candidate and adding dummy voters to satisfy the cohesion threshold; the inapproximability bound transfers the $1-1/e$ barrier of max coverage onto (S)SJR. The matching upper bound is the greedy algorithm, whose $1-1/e$ guarantee the paper claims follows from the same pigeonhole argument that gives the greedy guarantee for max $k$-coverage. On the Candidate Interval domain, optimizing (S)SJR is shown equivalent to Interval Maximum Coverage, for which a polynomial-time algorithm exists. Distinctive Representation's hardness comes from a reduction of Exact 3-Cover.

Extended reading notes

Core claim

The paper claims that diverse representation, when formalized through cohesive voter groups, is computationally demanding in general and tractable only under structure. It proves that the decision versions of the Semi-Strong JR and Strong JR maximization problems are NP-complete, that no polynomial-time algorithm approximates the optimal (S)SJR score within a ratio better than $1-1/e$ for committee size $k \in o(n)$ unless P=NP (Theorem 17), and that greedy selection attains exactly that ratio (Theorem 18). On the Candidate Interval domain, where each voter's approved candidates form an interval in a linear candidate order, exact maximization becomes polynomial via an equivalence to Interval Maximum Coverage (Theorem 20), and an FPT algorithm exists when a small candidate-deletion set is given. For the new Distinctive Representation axiom — a committee satisfying JR in which every elected candidate has exactly $\lceil n/k \rceil$ supporters — the paper proves the decision problem NP-hard via a reduction from Exact 3-Cover (Theorem 26), and shows the local-search variant Local DR is satisfiable in polynomial time.

Load-bearing premise

The $1-1/e$ barrier rests on two transfers the paper asserts rather than fully demonstrates: that the (S)SJR score grows under greedy selection at least as fast as Chamberlin–Courant coverage under the pigeonhole argument (the proof of Theorem 18 says this is 'not hard to see' without showing it), and that the CC-to-SSJR reduction preserves approximation despite converting optimal values only up to an additive $k$, which requires the underlying hard coverage instances to have optimum near $n$ with $k \in o(n)$.

Editorial extensions

If this is right

No polynomial-time algorithm can get within a factor better than $1-1/e$ of the optimal Strong JR or Semi-Strong JR committee on general approval profiles, unless P=NP.
On profiles where candidates can be ordered so that each voter approves an interval, exact (S)SJR optimization is efficiently computable, opening a tractable class for diversity-oriented committee selection.
Exact Distinctive Representation — committees whose members each have exactly $\lceil n/k \rceil$ supporters — is NP-hard to find, while its local variant is always computable in polynomial time.
When a small set of problematic candidates blocks interval structure, (S)SJR optimization is fixed-parameter tractable in the size of that set.
Distinctive Representation is logically independent of Extended and Proportional JR, priceability, and Balanced JR, so it captures a diversity goal that the proportionality axioms do not.
On real and synthetic data, the greedy and local-search rules score far above the worst-case $1-1/e$ guarantee, so the theoretical barrier is rarely reached in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The additive-$k$ slack in the hardness reduction suggests the $1-1/e$ barrier is tight only on profiles where the best committee already covers nearly all voters; on sparser profiles with small optimum, the practical gap to optimality may be far smaller, which would be consistent with the paper's near-optimal experimental scores.
Because Local DR is a polynomial-time local search that performs well on the paper's unique-voter and unique-candidate diversity measures, it is a plausible cheap heuristic for deliberation summaries or AI alignment panels where diversity of opinion, not proportionality, is the objective.
The CI-domain tractability rest on an equivalence to Interval Maximum Coverage, so any other domain restriction guaranteeing interval structure — for instance single-peaked or single-crossing preferences — plausibly inherits the same polynomial-time optimization, a testable extension across further restricted domains.
The gap between the greedy guarantee and observed performance raises the question whether a refined worst-case analysis of the (S)SJR score itself, rather than the CC-style pigeonhole bound, could sharpen the guarantee; the paper leaves this open.
Local DR's swap dynamics, which replace over-large candidates by candidates closer to $\lceil n/k \rceil$ supporters while preserving JR, could be adapted into a user-facing fairness knob in multi-winner systems that trades coverage against distinctiveness.

Original abstract

The study of approval-based committee voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin-Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P = NP), but both can be on the Candidate Interval and Voter Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show that Local DR performs well on multiple empirical measures of diversity.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-25: 1 request, 6,248 input tokens.

What the abstract itself states, as probabilities: claims first 0.17 · states limitation 0.75 · human participants 0.04 · controlled comparison 0.07 · randomized assignment 0.02 · states quantitative result 0.23 · compares with prior results 0.85 · mentions code or data availability 0.03.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

The study of approval-based committee (ABC) voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin--Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P=NP), but both can be on the Candidate Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show Local DR performs well on multiple empirical measures of diversity.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	The study of approval-based committee (ABC) voting has so far focused predominantly on proportional representation.	background 0.96	0.04	0.02	asserted 1.00
s1	The canonical notion of diverse representation, based on the Chamberlin--Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion.	background 1.00	0.06	0.04	asserted 1.00
s2	We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions.	contribution 1.00	0.92	0.26	asserted 0.99
s3	First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation.	contribution 0.85	0.42	0.05	asserted 0.95
s4	We show that neither can be optimized efficiently on general domains (unless P=NP), but both can be on the Candidate Interval domain.	result 0.99	0.92	0.11	asserted 0.99
s5	Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR.	contribution 1.00	0.94	0.09	asserted 0.99
s6	We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms.	result 0.82	0.93	0.17	asserted 1.00
s7	Experiments on real-world and synthetic data show Local DR performs well on multiple empirical measures of diversity.	result 1.00	0.95	0.23	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.72 · evidence from proof or derivation 0.87.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Relations between axioms and optimizations. Nor

**Figure 3.** Subfigure (a)shows (S)SJR existence for the Situ dataset. Subfigure (b) and (c)show the unique candidate- respectively unique voter-scores for the SCOTUS data set. Results: In general, we see that SSJR is satisfiable much more often than SJR. Observe that for the SCOTUS data, when k ≥ 3, almost all candidates are cohesive (see Figure 3b). This contrasts the Situ data (see Figure 3a) and the synthetic data (plots in Appendix F), where there is a lower portion of cohesive candidates. Thus, it is more challenging to satisfy (S)SJR on the SCOTUS data, whereas (S)SJR committees occur…

**Figure 4.** Example instance for claim “A committee W that satisfies the CC axiom, may not be optimal for Strong JR". There are 12 voters and 5 candidates. a b c d e

**Figure 5.** Example instance for claim “A committee W that satisfies the (Semi-)Strong JR axiom, may not be optimal for CC, and vice versa". There are 14 voters and 3 candidates. b c a

**Figure 7.** Example instance for claim "A committee W that is optimal for Strong JR, may not be optimal for Semi-Strong JR." There are 9 voters and 4 candidates. a b c d A.2 Explanation of relations in

**Figure 9.** Example instance for the claim “A committee

**Figure 11.** Example instance for claim “A committee W that is optimal for CC, may not be optimal for CNASH, and vice versa". There are 15 voters and 5 candidates. a b c d e B Supplementary material to Section 4 Proposition 12. For any approval-based committee election instance and committee W, the Semi-Strong JR maximization score and the Strong-JR maximization score of W can both be computed in polynomial time. Proof. For SSJR, iterate over all c /∈ W, check whether |Nc| ≥ n k and if so, check for all i ∈ Nc whether A(i) ∩ W ̸= ∅. For SJR we do almost the same, now we keep track of the sets

**Figure 14.** Relations between DR, Local DR and BJR for approval ballots. Arrows denote logical implications, the absence of

**Figure 16.** Bar plots for the unique candidate and unique voter scores of the rules on the Situ dataset.

**Figure 17.** Bar plot for the unique vote scores of the rules on the SCOTUS dataset

**Figure 18.** Bar plots for the CC scores of the rules on the SCOTUS and Situ datasets.

**Figure 19.** Bar plots for the (S)SJR existence rates of the rules on the synthetic datasets.

**Figure 20.** Bar plots for the unique voter-scores of the rules on the synthetic dataset.

**Figure 21.** Bar plots for the unique candidate-scores of the rules on the synthetic dataset.

**Figure 22.** Bar plots for the SSJR ratios of the rules on the synthetic dataset.

**Figure 23.** Bar plots for the SJR ratios of the rules on the synthetic dataset.

**Figure 24.** Bar plots for the CC scores of the rules on the synthetic dataset.

Showing 18 of the paper's 24 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:2609.29332 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.