PaperlayerView exact revision on arXiv

Source-linked AI summary

Diverse Representation in Approval-Based Committee Voting

Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly

arXiv:2609.29332v1cs.GT

TL;DR

Diverse representation in approval-based committee voting has largely been studied through proportionality, while the standard Chamberlin–Courant measure counts individual voter coverage. The paper develops group-based strengthenings of Justified Representation and introduces Distinctive Representation. It reports computational boundaries for these axioms and finds that Local DR performs well on multiple empirical measures of diversity.

  • Problem

    The standard Chamberlin–Courant notion counts voters with at least one representative, while the paper seeks a diversity notion that represents voters as members of groups.

    Source: §1 · p. 1

  • Method

    The paper studies SJR and SSJR as stricter forms of JR and introduces DR, which requires candidates to uniquely represent cohesive groups, alongside Local DR.

    Source: Our contribution · p. 2

  • Results

    SJR and SSJR cannot be efficiently optimized on general domains unless P=NP, both can be optimized on Candidate Interval, and Local DR performs well on multiple empirical diversity measures.

    Source: Our contribution · p. 2

  • Takeaways & Limitations

    The paper frames diverse representation as representing many cohesive groups and finds Local DR performs well across multiple empirical measures of diversity.

    Source: Our contribution · p. 2, §9 · p. 7

    There are instances with a DR committee that LS-DR fails to find.

    Source: §7 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The paper reframes diverse representation around groups of voters rather than only individual voter coverage. It strengthens Justified Representation in two directions and studies their computational and empirical properties.

1 Introduction

  • The established Chamberlin–Courant notion measures diversity by counting voters with at least one representative, whereas the paper’s group-based approach accounts for communities.The paper notes that the Chamberlin–Courant problem is equivalent to unit-weight Maximum k-Coverage, which is NP-hard.Source: §1 · p. 1
  • The paper’s conceptual contribution is to treat diverse representation as representing many voter groups, a perspective previously used in proportionality research.The authors ground this approach in Justified Representation and cohesive groups.Source: §1 · p. 1, Our contribution · p. 2
  • SJR and SSJR cannot be efficiently optimized on general domains unless P=NP, but both can be efficiently optimized on the Candidate Interval domain.The paper also studies their logical relations to other axioms and optimization variants.Source: Our contribution · p. 2
  • Distinctive Representation (DR) requires candidates to uniquely represent cohesive groups, and DR optimization is infeasible in polynomial time unless P=NP.The paper uses Local DR to compare this diversity notion with known diversity and proportionality axioms.Source: Our contribution · p. 2
  • Experiments find that SSJR is often satisfiable in practice despite theoretical insatisfiability, and Local DR performs well on multiple empirical diversity measures.Polynomial-time algorithms can attain results better than the 1 − 1/e ratio reported in the passage.Source: Our contribution · p. 2

2 Preliminaries

The preliminaries define approval-based committee elections and cohesive voter groups, then introduce coverage and representation axioms used in the paper. They also describe the relationships depicted in the figures.

2 Preliminaries

  • An election instance has voters, candidates, approval sets, and a committee of size k selected from the candidates.The approval profile records each voter’s approved candidates.Source: §2 · p. 2
  • The Chamberlin–Courant objective is to maximize the score of a k-candidate committee, and its greedy approximation has ratio 1 − 1/e.The passage states that the decision problem is NP-complete and that the greedy ratio is optimal unless P=NP.Source: §2 · p. 2
  • A group is ℓ-cohesive when it has at least ℓn/k voters and its members share at least ℓ approved candidates; for diversity, the paper considers ℓ=1.A candidate approved by every member of a group is called a cohesive candidate.Source: §2 · pp. 2–3
  • Figure 2 encodes approval by voter-node containment in candidate sets, while Figure 1 uses arrows for implications, conditional implications, and logical independence.A missing path in Figure 1 denotes logical independence.Source: Figure 1 · p. 2, Figure 2 · p. 3
  • JR requires every cohesive group to have at least one represented voter, and it is always satisfiable in polynomial time.The passage contrasts this with an example where a single non-cohesive candidate satisfies JR despite leaving voter coverage incomplete.Source: §2 · p. 3
  • SJR requires a cohesive group to share an elected approved candidate, while SSJR requires every member of that group to be represented.SSJR does not require the group’s members to be represented by the same candidate.Source: §2 · p. 3

3 (S)SJR, CC and CNASH

The section compares SJR, SSJR, CC, and CNASH, including their optimization variants. Their logical relationships are not a simple hierarchy, and CNASH and SSJR maximization coincide when SSJR is feasible.

3 (S)SJR, CC and CNASH

  • Because SJR and SSJR may be infeasible alongside CC, the section motivates maximization variants for these axioms.For n = 12 and k = 3, four cohesive groups can require representation even though only three candidates can be elected.Source: §3 · p. 3
  • CNASH selects a committee with maximal Nash score over cohesive groups, rather than calculating Nash welfare only across individual voters.The section introduces the rule in response to a limitation of voter-level Nash welfare when every committee leaves someone unrepresented.Source: §3 · p. 3
  • CC satisfaction implies SSJR, but CC may not be optimal for SJR, and optimizing SJR or SSJR need not even yield JR.The results also show that optimal committees for CC, SJR, SSJR, and CNASH can differ.Source: §3 · p. 4
  • When SSJR is feasible, the sets of NASH-maximizing and SSJR-satisfying committees are equal; otherwise, CNASH and SSJR maximization can diverge.Both SSJR maximization and CNASH depend monotonically on the union of the voters represented by elected candidates.Source: §3 · pp. 3–4

4 (Semi-)Strong JR maximization

SJR and SSJR maximization are computationally hard on general domains, but greedy optimization achieves the best possible approximation ratio. The section also shows that greedy CC can perform poorly on these objectives.

4 (Semi-)Strong JR maximization

  • The SJR and SSJR scores of a given committee can both be computed in polynomial time, even though finding an optimum is NP-hard.The paper's algorithm repeatedly adds a candidate that maximizes the score increase.Source: §4 · p. 4
  • The decision problems for SSJR, SJR, and CNASH are NP-complete, so exact optimization is not generally tractable unless P=NP.The section derives SSJR hardness by reduction from the Chamberlin–Courant decision problem.Source: §4 · p. 4
  • The greedy algorithm is (1−1/e)-approximate in polynomial time for both SJR and SSJR; for k∈o(n), no polynomial-time algorithm can do better unless P=NP.The hardness result establishes the ratio as optimal in that setting.Source: §4 · p. 4
  • Greedy CC can achieve a ratio no greater than 1/k for SJR and SSJR, because its first choice can block all other cohesive groups.This contrasts with the dedicated greedy algorithm's (1−1/e) approximation guarantee.Source: §4 · p. 4

5 (S)SJR on restricted domains

The section examines SJR and SSJR under restricted preference domains. Satisfiability varies by domain, while maximization is tractable on Candidate Interval instances and fixed-parameter tractable given a candidate-deletion set.

5 (S)SJR on restricted domains

  • (S)SJR is satisfiable on VEI; SJR is not satisfiable on CI, VI, or CEI, while SSJR is not satisfiable on CI or VI but is satisfiable on CEI.The results distinguish satisfiability from the separate question of efficient maximization.Source: §5 · p. 5
  • Both SJR-score and SSJR-score maximization can be performed efficiently on the Candidate Interval domain.Source: §5 · p. 5
  • Given a candidate-deletion set D whose removal makes preferences Candidate Interval, (S)SJR maximization has an FPT algorithm parameterized by |D|.Candidate Interval domains require an ordering of candidates in which each voter's approved candidates form an interval.Source: §5 · p. 5

6 Distinctive Representation

Distinctive Representation (DR) strengthens JR by requiring cohesive groups to have distinctive representatives, not merely some representation. DR can be unsatisfiable and is computationally hard to decide.

6 Distinctive Representation

  • DR requires JR and that every elected candidate have exactly ⌈n/k⌉ supporters, making elected candidates distinctive representatives of cohesive groups.The paper introduces DR to address the possibility that broadly acceptable candidates represent groups without capturing their unique opinions.Source: §6 · p. 5
  • DR can be unsatisfiable, even on Candidate Interval or Voter Interval instances.Source: §6 · p. 5
  • Unless P = NP, no optimization function that equals zero whenever DR is met can be optimized efficiently.The paper motivates optimization by DR's possible insatisfiability, then establishes this hardness using a reduction from Exact 3-Cover.Source: §6 · p. 5
  • The DR decision problem is NP-hard, so deciding whether a DR committee exists is computationally intractable unless P = NP.Source: §6 · p. 5

7 Local DR

Local DR is a locally optimal, tractable alternative to DR, which cannot be optimized efficiently. The paper gives a polynomial-time local-search algorithm and establishes that Local DR is distinct from several known axioms and rules.

7 Local DR

  • Local DR requires JR and rules out a JR-preserving swap that moves an elected candidate's supporter count closer to ⌈n/k⌉, subject to an exception for certain over- and under-sized groups.Source: §7 · p. 5
  • LS-DR satisfies Local DR in polynomial time, but can fail to find a DR committee even when one exists.Source: §7 · p. 5
  • Local DR and EJR/PJR are mutually non-implicative; Local DR is also independent of (S)SJR, priceability, and Monroe-optimality.DR and priceability are mutually non-implicative as well; Monroe's rule uses voter assignments, whereas Local DR concerns candidate supporter-set sizes close to ⌈n/k⌉.Source: §7 · pp. 5–6
  • The paper does not specify a single optimization function for DR; possible objectives include summing or multiplying deviations from ⌈n/k⌉.Source: §7 · p. 5
  • LS-DR starts from a JR committee and repeatedly selects eligible swaps that improve the candidates' supporter-count closeness to ⌈n/k⌉.The swap must preserve JR and satisfy the stated condition on supporter counts.Source: §7 · p. 6
  • DR implies Balanced JR for approval ballots, but Local DR and Balanced JR are mutually non-implicative.Balanced JR uses an assignment of voters to committee candidates; DR additionally requires candidates to be distinctive for their matched groups.Source: §7 · p. 6

8 Experiments

Experiments evaluate the voting rules on real-world and synthetic elections, first examining (S)SJR existence and greedy performance, then comparing diversity measures. LS-DR stands out on unique-opinion measures while retaining reasonable performance on standard diversity measures.

8 Experiments

  • The evaluation covers SCOTUS and Situ profiles and synthetic Resampling Model elections, with committee sizes k from 2 to 7.The real-world sets comprise 152 SCOTUS and 16 Situ profiles; synthetic elections use n = 100, m = 20, p = 0.2, and ϕ ∈ {0.25, 0.5, 0.75}.Source: §8 · p. 6
  • The tested rules include Sequential CC, MES, greedy (S)SJR, simplified Cohesive Nash, and LS-DR initialized with simplified Cohesive Nash.Source: §8 · p. 6

8.2 Diversity Measures

  • On SCOTUS elections, LS-DR and simplified CNASH stand out on unique voter-score, while LS-DR, Sequential CC, and simplified CNASH perform similarly on unique candidate-score.LS-DR also performs well on unique voter-score in Situ and synthetic data for ϕ ∈ {0.25, 0.5}; it performs reasonably on CC and SJR coverage without significant sacrifice from adding localswap dynamics to simplified CNASH.Source: Figure 3 · p. 7, §8.2 · p. 7

8.1 (S)SJR Existence, and Performance of Algorithm 1

  • SSJR is generally satisfiable more often than SJR; SCOTUS has almost all candidates cohesive for k ≥ 3, making (S)SJR satisfaction more challenging there than in Situ or synthetic data.Source: Figure 3 · p. 7, §8.1 · p. 7
  • Greedy rules and all other tested voting rules consistently return committees with near-optimal (S)SJR scores, well above the theoretical 1 − 1/e worst-case bound.Source: §8.1 · p. 7

8.2 Diversity Measures

  • The study uses (S)SJR scores and unique voter- and candidate-scores alongside CC score; the unique-opinion measures are averaged over election instances by committee size.Unique voter-score tracks retained unique approval ballots, while unique candidate-score tracks distinct candidate supporter groups.Source: §8.2 · p. 7
  • The authors focus the remaining diversity-measure analysis on SCOTUS because it has more cohesive candidates and generally clearer differences between rules than the other datasets.Most Situ and synthetic results are relegated to the appendix.Source: §8.2 · p. 7

9 Conclusions

The paper frames diverse representation around cohesive groups and strengthens JR in two directions: stricter representation through SJR and SSJR, and distinctive representation through DR. Its supplementary results show that the axioms and their optimization variants have limited logical equivalences.

9 Conclusions

  • The paper's central contribution is to study diverse representation through cohesive groups, using SJR and SSJR for stricter representation and DR for distinctive representation.DR requires elected candidates to represent voter groups of equal size.Source: §9 · p. 7

A Supplementary material to Section 3

A.1 Figures that accompany the proof of Theorem 11

The examples and relation analysis show that satisfying or optimizing one representation objective need not optimize another. The appendix also records a hierarchy among the JR axioms and examples separating their maximization variants.

A.1 Figures that accompany the proof of Theorem 11

  • CC-optimal committees need not be SJR- or SSJR-optimal, and SJR-optimal committees need not be SSJR-optimal.The examples also show that committees satisfying CC can fail SJR, while satisfying (Semi-)Strong JR need not yield CC-optimality.Source: Figure 4 · p. 11, Figure 5 · p. 11, Figure 6 · p. 12

A.2 Explanation of relations in Figure 1

  • SJR is strictly stronger than SSJR, which is strictly stronger than JR; CC satisfaction implies SSJR and JR satisfaction.The appendix lists these hierarchy relations alongside further implications and non-implications among the axioms and their maximization variants.Source: §A.2 · pp. 12–13
  • An (Semi-)Strong-JR-optimal committee may fail JR, and a CNASH-optimal committee may fail to yield an SJR-satisfying committee even when one exists.Other examples separate CNASH from SSJR maximization and CC from CNASH maximization.Source: Figure 9 · p. 13, Figure 11 · p. 14, Figure 8
  • A committee optimal for SJR may not be optimal for CNASH, and CC-optimality and CNASH-optimality can also diverge.The figures give separate examples for these comparisons.Source: Figure 11 · p. 14, Figure 10

B Supplementary material to Section 4

The appendix completes the computational analysis of Strong and Semi-Strong JR maximization. It establishes hardness, an approximation threshold, and a matching polynomial-time greedy guarantee.

B Supplementary material to Section 4

  • Both SSJR and SJR maximization scores can be computed in polynomial time for a given committee.The appendix describes checking cohesive candidates and, for SJR, comparing the represented approval sets.Source: B Supplementary material to Section 4 · p. 14
  • The hardness reduction maps a CC instance with score x to an SSJR instance with score x+k, preserving whether the target score is attainable.It adds voter-candidates and dummy voters, and gives each original candidate a unique dummy voter to prevent unintended coverage.Source: B Supplementary material to Section 4 · p. 15
  • The Strong JR and CNASH decision problems are NP-complete, and the Semi-Strong JR decision problem is also NP-complete.The SSJR hardness proof reduces from CC decision; the SJR and CNASH results follow by reductions from SSJR.Source: B Supplementary material to Section 4 · pp. 14–15
  • For k=o(n), no polynomial-time algorithm approximates (S)SJR within a ratio better than 1−1/e unless P=NP.The result follows through a reduction preserving the CC score up to an additive k.Source: B Supplementary material to Section 4 · pp. 15–16
  • A polynomial-time greedy algorithm achieves a (1−1/e)-approximation for both SJR and SSJR maximization.Its guarantee uses the greedy coverage argument: each round increases the score by at least the remaining optimal-score gap divided by k.Source: B Supplementary material to Section 4 · p. 16

C Supplementary material to Section 5

The supplementary results identify domains where (S)SJR maximization is tractable or satisfiable and establish limits on satisfiability and computation for DR. They also provide a fixed-parameter algorithm for elections close to the Candidate Interval domain.

C Supplementary material to Section 5

  • SJR is satisfiable on VEI but not on CI, VI, or CEI; SSJR is satisfiable on CEI and VEI but not on CI or VI.The appendix supplies example instances for the unsatisfiable domains.Source: C Supplementary material to Section 5 · p. 16
  • (S)SJR-score maximization is polynomial-time solvable on Candidate Interval and Voter Interval domains.On Candidate Interval preferences, the problem is reduced to Interval Maximum Coverage.Source: C Supplementary material to Section 5 · pp. 16–17
  • Given a candidate-deletion set D, (S)SJR maximization has an FPT algorithm parameterized by |D|.It guesses which deleted candidates are pre-elected, then solves weighted interval coverage on the remaining CI instance.Source: C Supplementary material to Section 5 · p. 17

D Supplementary material to Section 6

  • DR may be unsatisfiable even on CEI and VEI instances, and its decision problem is NP-hard.An instance lacking k candidates of size ⌈n/k⌉ witnesses general unsatisfiability; the hardness proof reduces from X3C.Source: D Supplementary material to Section 6 · p. 17

E Supplementary material to Section 7

The appendix analyzes Local DR’s algorithmic behavior and separates it from global DR and established representation rules. Its examples show that local optimality does not ensure global DR or equivalence with other committee objectives.

E Supplementary material to Section 7

  • The LS-DR algorithm returns a Local DR committee in polynomial time.Its swap objective strictly decreases, and the number of iterations and the work per iteration are polynomially bounded.Source: E Supplementary material to Section 7 · p. 18
  • A DR committee can exist even when LS-DR reaches a suboptimal local optimum.The example traps the algorithm at a committee containing an oversized candidate because reaching the better committee requires an intermediate swap that does not improve its score.Source: E Supplementary material to Section 7 · p. 18
  • Local DR does not imply EJR, priceability, or (S)SJR, and none of those properties implies Local DR.The appendix gives separate counterexamples for these relationships.Source: E Supplementary material to Section 7 · p. 18
  • Monroe/CC winners and Local DR winners are distinct, and DR implies BJR while Local DR and BJR do not imply one another.In the Figure 13 instance, EJR/PJR require both a and b, whereas Local DR selects only one of them and can still cover all voters.Source: E Supplementary material to Section 7 · pp. 18–19, Figure 13 · p. 19

F.1 (S)SJR

The real-world results compare rules on their ability to approximate the optimal SJR and SSJR scores, with each axiom’s own rule performing particularly well on its corresponding score. The implementation uses ILPs for verification and constraint generation, and the additional plots report further diversity and representation measures.

F.1 (S)SJR

  • The real-world table reports average approximation ratios for SJR and SSJR across election profiles with committee sizes k ∈ {2, 7}.The prose compares the rules with the theoretically optimal approximation ratio of 1 − 1/e but supplies no individual table values here.Source: §F.1 · pp. 19–20, Table 1 · p. 20
  • SJR and SSJR perform particularly well on their own scores, while each performs relatively poorly on the other axiom’s score.The simplified CNASH rule even beats SSJR on its own score when averaging over Situ and SCOTUS data.Source: §F.1 · p. 20

F.2 Implementation details

  • SJR committee search uses constraint generation: a verification ILP finds a violating 1-cohesive group, adds a constraint, and repeats until a valid committee is found or none exists.The verification oracle searches for a group with no committee member approved by all its members.Source: Finding SJR committees · pp. 20–21
  • The SJR verification ILP maximizes the size of a violating 1-cohesive group; SSJR checking instead flags unrepresented voters who approve a 1-cohesive candidate.The algorithms were implemented in Python using Gurobi.Source: §F.2 · p. 20, SJR verification · p. 21, Finding SSJR · p. 21

F.3 Additional Plots

Loading 2609.29332v1…