PaperlayerView exact revision on arXiv

Source-linked AI summary

Approval-Based Multiwinner Voting with Candidate Qualities

Niclas Boehmer, Chris Dong, Luca Kreisel, Markus Utke

arXiv:2609.08830v1cs.GT

TL;DR

The paper asks how proportional representation should account for exogenous candidate qualities while preserving the goal of maximizing summed quality. It introduces quality-aware proportionality axioms and rules, and shows reciprocal variants can retain at least 3/4 of optimal summed quality.

  • Problem

    The paper asks how proportional representation should change when candidates have exogenous qualities, and how it can be reconciled with maximizing summed quality.

    Source: §1 · p. 3, §5 · p. 13

  • Method

    The paper defines threshold- and value-based adaptations of JR, PJR, and EJR, and gives rules for the strongest jointly satisfiable combinations.

    Source: §6 · p. 16

  • Results

    3/4 of optimal summed quality is retained by committees satisfying reciprocal proportionality axioms, and the rules compute them at no additional computational cost.

    Source: §1.1 · p. 4, §6 · p. 16

  • Takeaways & Limitations

    Reciprocal entitlement scaling provides a compromise between proportional representation and summed-quality maximization without additional computational cost.

    Source: §1.1 · p. 4, §6 · p. 16

    Computing a value-EJR committee is NP-hard, and no polynomial-time rule guarantees value-EJR unless P != NP.

    Source: §4.2 · p. 12

Abstract

from arXiv · show

We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.

1. Introduction

The paper extends approval-based multiwinner voting to candidates with exogenous quality scores, then asks how proportional representation should account for quality while supporting summed-quality maximization. It proposes quality-aware proportionality axioms and rules, and analyzes their relationships, complexity, and compatibility with quality maximization.

1. Introduction

  • The model adds exogenous candidate quality scores to approval-based multiwinner voting and asks how proportionality can coexist with maximizing summed quality.Source: §1 · pp. 2–3

1.1. Our Contributions

  • Threshold-based axioms require representation by enough sufficiently high-quality candidates, while value-based axioms require sufficient summed quality from approved selected candidates.Source: §1.1 · p. 3
  • Party-list requirements combined with well-behavedness properties characterize refinements of the proposed axioms, clarifying the normative difference between the two families.Source: §1.1 · p. 4
  • Threshold-, value-, and standard PJR are jointly satisfiable, as are value-EJR and standard PJR; computing value-EJR is NP-hard even with two quality values.Source: §1.1 · p. 4
  • Reciprocal axioms scale voter groups’ entitlements by the quality of commonly approved candidates, and rules satisfy them while retaining at least 3/4 of optimal summed quality at no extra computational cost.Source: §1.1 · p. 4

1.2. Related Work

  • Earlier work studies candidate costs and diversity constraints, whereas these quality scores do not restrict which fixed-size candidate sets are admissible.Source: §1.2 · p. 4
  • Unlike prior work on welfare loss from proportionality, this paper optimizes summed candidate quality, independent of approvals, and proposes quality-aware relaxations of proportionality axioms.Source: §1.2 · p. 5

2. Model

The model equips an approval-based multiwinner election with candidate quality scores and retains fixed-size committees. It defines total quality and uses voter-group size and shared approvals to frame proportionality requirements.

2. Model

  • Each voter has an approval set, and a committee is a candidate subset of the target size k selected to represent voters.Source: §2 · p. 5
  • Each candidate receives a quality score h_c in (0, 1], and a set’s total quality is the sum of its candidates’ scores.Source: §2 · p. 5
  • A voter group is ℓ-large when it meets a size threshold and ℓ-cohesive when it also commonly approves at least ℓ candidates; JR, PJR, and EJR specify representation for such groups.Source: §2 · p. 6

3. Defining Quality-Aware Proportionality

The paper adapts JR, PJR, and EJR to candidate qualities through value-based and threshold-based entitlements. It also studies their axiomatic properties, satisfiability, and verification complexity.

3.1. Adapting JR

  • Value-JR requires a 1-cohesive group to receive summed approved quality at least that of its best commonly approved candidate; threshold-JR requires representation above every qualifying quality cutoff.Both notions allow entitlements to be met by selected candidates approved by any voter in the group.Source: §3.1 · p. 7
  • Under natural well-behavedness axioms, value-JR and threshold-JR are canonical extensions of distinct party-list representation principles for 1-cohesive groups.The party-list principles are weak total representation and weak best-in-slot representation, respectively.Source: §3.1 · p. 8

3.2. Adapting PJR and EJR

  • Value-EJR requires some voter in an ℓ-cohesive group to reach the summed quality of its best ℓ commonly approved candidates, while threshold-EJR imposes representation requirements above quality cutoffs.The paper also establishes lower-quota foundations for the value and threshold PJR/EJR notions and characterizes threshold-PJR+ as a canonical strengthening of threshold-PJR.Source: §3.2 · pp. 8–9

3.3. Satisfiability and Verification

  • All discussed notions except threshold-EJR are always satisfiable, and deciding whether a threshold-EJR committee exists is NP-hard.Verification is polynomial-time for JR-level notions except value-JR; PJR/EJR-level verification is intractable, while threshold-PJR+ is polynomial-time verifiable.Source: §3.3 · p. 10

4. Axiom Relations and Designing Proportional Rules

The section maps implications and incompatibilities among threshold-, value-, and standard proportionality axioms, then gives rules attaining the strongest jointly satisfiable combinations. The rules range from polynomial-time expanding approvals rules to an exponential-time value-based rule, with value-EJR computation ruled out in polynomial time unless P=NP.

4.1. Axiom Relations

  • Within each family, EJR implies PJR, which implies JR; threshold-PJR+ also implies threshold-PJR.Each threshold notion implies its standard counterpart, while value-JR implies JR; value-PJR and value-EJR need not imply standard PJR.Source: §4.1 · pp. 10–11
  • At the JR and PJR levels, threshold notions imply their value counterparts, but threshold-EJR and value-EJR are incompatible even when a threshold-EJR committee exists.The figure distinguishes implications, incompatibilities, and compatibilities without implication.Source: §4.1 · p. 11, Figure 1 · p. 11
  • All PJR-level notions are jointly satisfiable, whereas EJR conflicts with threshold- and value-JR, and value-EJR conflicts with threshold-JR.The section identifies these as constraints on which guarantees can be combined.Source: §4.1 · p. 11

4.2. Designing Rules

  • Expanding approvals rules run in polynomial time and satisfy threshold-PJR+, which implies threshold-, value-, and standard PJR.Threshold-MES is a tractable example that selects an affordable candidate minimizing its payment threshold.Source: §4.2 · p. 12
  • Value-GCR satisfies value-EJR and standard PJR, but runs in exponential time because it checks voter groups for value-EJR violation witnesses.It iteratively addresses the strongest-value-entitlement witnesses, then adds affordable candidates and completes the committee if needed.Source: §4.2 · p. 12
  • Unless P=NP, no polynomial-time algorithm can always compute a value-EJR committee, even with only quality-1 candidates and one other unary-encoded quality.The result also rules out pseudo-polynomial-time algorithms for the cited unit-cost, unary-encoded setting.Source: §4.2 · pp. 12–13

5. Quality-Aware Proportionality and Quality Maximization

The section defines reciprocal proportionality by scaling group entitlement according to the quality of commonly approved candidates, then studies its compatibility with maximizing total committee quality. Reciprocal axioms admit a 3/4 quality guarantee, while the considered non-reciprocal notions can incur much larger losses.

5.1. Reciprocal Proportionality

  • Reciprocal proportionality scales a group's entitlement with the quality of its commonly approved candidates, so lower-quality candidates require more support for comparable representation.The reciprocal axioms weaken their non-reciprocal counterparts; reciprocal threshold-EJR remains unsatisfiable.Source: §5.1 · pp. 13–14, §5 · p. 13
  • A group can reciprocally afford commonly approved candidates when its size meets the quality-adjusted support requirement, making low-quality candidates costlier in voter entitlement.For reciprocal JR, the group-size threshold is based on the reciprocal quality of its commonly approved candidates.Source: §5.1 · pp. 13–14

5.2. Price of Representation

  • JR, value-JR, and threshold-JR each have quality-price of representation at least k, and unsupported candidates make that price unbounded.The paper assumes every candidate has at least one supporter when analyzing quality loss.Source: §5.2 · pp. 14–15
  • Any quality-greedy completion of a reciprocally affordable candidate set retains at least 3/4 of the optimal summed quality.A quality-greedy completion fills the committee to size k while maximizing quality among supersets of the affordable set.Source: §5.2 · p. 15
  • Reciprocal versions of MES, EAR-rules, and GCR satisfy reciprocal EJR, reciprocal threshold-PJR+, and reciprocal value-EJR, respectively, and output quality-greedy completions of reciprocally affordable candidate sets, achieving the optimal 3/4 quality approximation.Source: §5.2 · p. 15
  • Threshold-JR can guarantee only a 1/k fraction of optimal welfare even when qualities approach 1, while value-JR admits a polynomial-time welfare approximation.The value-JR guarantee is stated as h−/8 · 1/k in the supplied passage.Source: §5.2 · p. 16

6. Conclusion

The conclusion summarizes a framework for quality-aware proportionality, its satisfiable combinations and computational limits, and reciprocal axioms that preserve a constant fraction of optimal committee quality. It also identifies further theoretical and empirical directions.

6. Conclusion

  • The paper introduces threshold- and value-based adaptations of JR, PJR, and EJR, and gives rules for the strongest jointly satisfiable combinations.Threshold-MES and value-GCR are highlighted among the rules; computing value-EJR is NP-hard.Source: §6 · p. 16
  • Reciprocal versions of the axioms remain compatible with quality maximization, allowing an optimal constant-factor approximation of total committee quality while maintaining representation guarantees at no additional computational cost.Source: §6 · p. 16
  • Future work includes quality-aware axioms beyond proportionality, robustness to noisy externally assessed scores, and empirical study in application domains.The paper names information retrieval and participatory budgeting as possible application domains.Source: §6 · p. 16

A. Hardness of Finding a Value-EJR Committee

The appendix proves that computing a value-EJR committee is NP-hard by reducing Balanced Biclique to committee construction. The constructed instance has a unique value-EJR committee exactly when the graph has no biclique of the target size.

A. Hardness of Finding a Value-EJR Committee

  • The reduction maps a bipartite graph and target t to an election whose candidates are private quality-1 options and lower-quality blocks associated with right-side vertices.Each private candidate is approved only by its voter; each block candidate is approved by the corresponding neighborhood and filler voters.Source: A. Hardness of Finding a Value-EJR… · p. 20
  • If the graph contains a Kt,t biclique, its left-side voters and filler voters form a cohesive group whose entitlement makes the all-private committee violate value-EJR.The construction makes the group commonly approve the block candidates associated with the biclique's right-side vertices.Source: A. Hardness of Finding a Value-EJR… · pp. 20–21
  • If the graph has no Kt,t, the all-private committee is the unique value-EJR committee.Any different value-EJR committee would require enough shared block candidates among at least t vertex voters to imply a Kt,t biclique.Source: A. Hardness of Finding a Value-EJR… · p. 21
  • A polynomial-time value-EJR algorithm would decide Balanced Biclique in polynomial time, implying P=NP.The reduction answers yes exactly when the algorithm returns a committee other than the all-private committee.Source: A. Hardness of Finding a Value-EJR… · pp. 20, 22

B.1. Justified Representation

The JR-level axioms are canonical among proportionality notions that satisfy three well-behavedness conditions. Quality-aware lower quotas extend party-list representation requirements, and the threshold-PJR+ variant is characterized by best-in-slot lower quota plus those conditions.

B.1. Justified Representation

  • On party-list profiles, the JR-level axioms require representation through a candidate, total quality at least the best shared candidate’s quality, or best-in-slot representation, respectively.The weak representation hierarchy parallels these JR-level definitions.Source: §B.1 · pp. 22–23
  • Weak representation, weak total representation, and weak best-in-slot representation correspond respectively to JR, value-JR, and threshold-JR under the three well-behavedness conditions.Each matching JR-level notion satisfies the corresponding weak representation axiom and all three conditions.Source: §B.1 · p. 23
  • Best-in-slot and total lower quota require, respectively, high-quality seats or summed quality matching each party’s quota entitlement.Classic PJR and EJR satisfy lower quota; value-PJR and value-EJR satisfy total lower quota; threshold-PJR and threshold-EJR satisfy best-in-slot lower quota.Source: §B.1 · p. 24
  • Threshold-PJR+ is characterized by best-in-slot lower quota together with independence of losers, robustness to fully satisfied voters, and monotonicity.Under these three conditions, best-in-slot lower quota implies refinement of threshold-PJR+; threshold-PJR+ itself satisfies all four properties.Source: §B.1 · p. 24

C. Hardness of Value-JR Verification

This section establishes that verifying whether a committee satisfies value-JR is computationally intractable. A reduction from Minimum t-Union proves coNP-completeness even with only two distinct candidate qualities.

C. Hardness of Value-JR Verification

  • Value-JR verification is coNP-complete even when the instance has only two distinct candidate qualities.A violating voter group and a highest-quality commonly approved candidate provide a certificate that verification lies in coNP.Source: C. Hardness of Value-JR Verification · p. 25
  • The hardness proof reduces Minimum t-Union to finding a voter group that witnesses a value-JR violation.The constructed instance uses universe candidates, filler candidates, and a potential witness candidate with quality 1; other candidates have quality β.Source: C. Hardness of Value-JR Verification · p. 25
  • A yes-instance of Minimum t-Union yields a group whose approved selected candidates have total quality below the quality-1 witness candidate.Selecting t sets whose union has at most b elements makes the selected shared quality at most bβ < 1.Source: C. Hardness of Value-JR Verification · p. 25
  • Conversely, any value-JR violation in the constructed instance yields a yes-instance of Minimum t-Union.The violation must be witnessed by set-voters and the omitted quality-1 candidate.Source: C. Hardness of Value-JR Verification · p. 25

D.1. Threshold- and Value-JR Notions

The section maps implications and incompatibilities among threshold-, value-, and standard JR notions. It also shows that value-EJR and PJR are always jointly satisfiable despite neither implying the other.

D.1. Threshold- and Value-JR Notions

  • Threshold-EJR and value-EJR are incompatible even on an instance where threshold-EJR is satisfiable.In the example, the unique threshold-EJR committee gives the relevant voters utility 1 against a value-EJR demand of 1.5.Source: §D.1 · p. 26, Table 4 · p. 27
  • Threshold-PJR implies value-PJR, and threshold-JR implies value-JR.The threshold-EJR/value-EJR incompatibility also strengthens to incompatibility between threshold-JR and value-EJR.Source: §D.1 · pp. 27–28

D.2. Threshold- and Basic JR Notions

  • Threshold-EJR, threshold-PJR, and threshold-JR each imply their standard counterparts, but EJR is incompatible with threshold-JR.The example’s unique threshold-JR committee violates EJR for the voter group.Source: §D.2 · p. 28

D.3. Value- and Basic JR Notions

  • Value-EJR does not imply PJR, yet the two axioms are simultaneously satisfiable in every profile.The example committee satisfies value-EJR but fails PJR; a rule satisfying both is defined elsewhere in the paper.Source: §D.3 · p. 29
  • EJR and value-JR are incompatible, while value-JR implies JR.The example’s unique value-JR committee violates EJR.Source: §D.3 · p. 29

E.1. Threshold-PJR+ via EAR

The section proves that EAR produces committees satisfying threshold-PJR+ through threshold-maximal affordability. It also establishes NP-hardness for computing a rule that returns threshold-EJR whenever possible and for deciding whether a threshold-EJR committee exists.

E.1. Threshold-PJR+ via EAR

  • Any completion of a threshold-maximally affordable candidate set satisfies threshold-PJR+.The EAR proof shows its uncompleted set is threshold-maximally affordable, so its completed committee satisfies threshold-PJR+.Source: §E.1 · p. 30, §G.2 · p. 44
  • Computing a rule that returns threshold-EJR whenever such a committee exists is NP-hard, as is deciding whether one exists.The reduction from Vertex Cover establishes both hardness results.Source: §E.1 · pp. 31–32
  • The Vertex Cover reduction constructs an instance whose threshold-EJR committees contain all dummy candidates and whose vertex candidates form a size-q vertex cover.The construction’s equivalence between a threshold-EJR committee and a size-q vertex cover underlies both hardness results.Source: §E.1 · p. 31

E.2. PJR and Value-EJR via Value-GCR

Value-GCR constructs committees that satisfy value-EJR and standard PJR. Its witness-driven selection and budgeted completion phases ensure these representation guarantees while keeping the committee within the target size.

E.2. PJR and Value-EJR via Value-GCR

  • In phase 1, the rule repeatedly chooses a value-EJR violation witness maximizing h(C∩S | ℓ), adds a corresponding set of ℓ candidates, and charges its voters.Phase 2 adds candidates affordable by their supporting voters, then completes the committee arbitrarily if needed.Source: §E.2 · p. 32
  • Value-GCR satisfies value-EJR and standard PJR while returning a committee of size at most k.Value-EJR follows from phase 1's termination condition; the proof of PJR uses voters' remaining budget in phase 2.Source: §E.2 · pp. 32–33
  • The proof bounds committee size by showing that phase-1 witness voter sets are disjoint and candidate costs are covered by voters' budgets.The completion step does not increase the committee beyond k.Source: §E.2 · p. 32

E.3. Value-EJR-1 via Quality-utility MES

Quality-utility MES provides a polynomial-time relaxation of value-EJR, while reciprocal proportionality axioms preserve the relationship pattern of their non-reciprocal counterparts. Reciprocal threshold-EJR, however, is not always satisfiable.

E.3. Value-EJR-1 via Quality-utility MES

  • Quality-utility MES runs in polynomial time and satisfies value-EJR-1 and PJR, but it fails value-JR with any completion method.It uses MES with unit costs and cardinal utilities ui(c) = hc; value-EJR-1 permits a one-candidate addition to meet the entitlement.Source: §E.3 · p. 33

F. Reciprocal Proportionality

F.1. Reciprocal Notions and Relations

  • Reciprocal threshold-EJR is weaker than threshold-EJR but remains not always satisfiable.In the example, representation at threshold 1 requires selecting c1, c2, and c3, while at threshold 2/3 the voters can reciprocally afford {d1, d2}, requiring one of those candidates.Source: §F.1 · p. 34

F.1.1. Threshold- and Value-JR Notions

This section analyzes reciprocal threshold-, value-, and basic JR notions, mapping their implications and incompatibilities and deriving party-list characterizations for reciprocal JR variants. It also characterizes reciprocal threshold-PJR+ and establishes quality guarantees for several reciprocal proportionality notions, with rules that achieve those guarantees through quality-greedy completions of reciprocally affordable sets.

F.1.1. Threshold- and Value-JR Notions

  • Reciprocal threshold-EJR and reciprocal value-EJR are incompatible, even on instances admitting reciprocal threshold-EJR committees; reciprocal value-EJR is also incompatible with reciprocal threshold-JR.Source: §F.1.1 · pp. 34, 36, 37
  • Reciprocal threshold-PJR implies reciprocal value-PJR, and reciprocal threshold-JR implies reciprocal value-JR.Source: §F.1.1 · p. 36

F.1.2. Threshold- and Basic JR Notions

  • Reciprocal threshold-JR notions imply their corresponding reciprocal JR notions, but reciprocal EJR is incompatible with reciprocal threshold-JR.Source: §F.1.2 · pp. 37–38

F.1.3. Value- and Basic JR Notions

  • Reciprocal value-EJR does not imply reciprocal PJR, although they are always simultaneously satisfiable; reciprocal value-JR implies reciprocal JR, and is incompatible with reciprocal EJR.Source: §F.1.3 · pp. 38–39

F.2. Reciprocal Axiomatics

  • Singleton reciprocal party-list representation, monotonicity, independence of losers, and robustness to fully satisfied voters together force refinement of reciprocal JR.Source: §F.2 · p. 39
  • Reciprocal total party-list representation characterizes reciprocal value-JR, while reciprocal best-in-slot party-list representation characterizes reciprocal threshold-JR, under shared regularity axioms.For both characterizations, the shared axioms are monotonicity, independence of losers, and robustness to fully satisfied voters; each corresponding JR notion also satisfies those axioms.Source: §F.2 · p. 39
  • Reciprocal threshold-PJR+ is characterized by reciprocal best-in-slot lower quota among rules satisfying independence of losers, robustness to fully satisfied voters and monotonicity.Under those three properties, best-in-slot lower quota implies refinement of reciprocal threshold-PJR+; reciprocal threshold-PJR+ itself satisfies all four axioms.Source: §F.2 · p. 40

G. Quality-Price of Representation

Hence any reciprocal JR committee has quality at most 1

G.1. The Quality-Price of Reciprocal EJR

The paper constructs reciprocal rules for EJR, threshold-PJR+, and value-EJR, with each achieving a quality-price of 4/3. The rules combine proportionality with quality-greedy completion of reciprocally affordable candidate sets.

G.1. The Quality-Price of Reciprocal EJR

  • 4/3 is the quality-price of reciprocal EJR, achieved by reciprocal MES, which satisfies reciprocal EJR and completes a reciprocally affordable set quality-greedily.Reciprocal MES adapts Method of Equal Shares to candidate costs of 1/h_c.Source: §G.1 · pp. 42–43

G.2. The Quality-Price of Reciprocal Threshold-PJR+

  • 4/3 is the quality-price of reciprocal threshold-PJR+, achieved by reciprocal EAR, whose completions satisfy reciprocal threshold-PJR+.Any completion of a reciprocal threshold-maximally affordable candidate set satisfies reciprocal threshold-PJR+.Source: §G.2 · pp. 43–44

G.3. The Quality-Price of Reciprocal Value-EJR

  • 4/3 is the quality-price of reciprocal value-EJR, achieved by reciprocal value-GCR, which satisfies reciprocal value-EJR and completes a reciprocally affordable set quality-greedily.The rule selects reciprocal value-EJR violation witnesses before adding further reciprocally affordable candidates.Source: §G.3 · pp. 44–45

H. Welfare-Price of Representation

The section compares how proportionality constrains summed candidate quality. Standard JR and threshold-JR can force low-welfare committees, while value-JR admits a bound depending on minimum quality and a polynomial-time construction.

H. Welfare-Price of Representation

  • Reciprocal JR retains a nontrivial welfare approximation bound, and the classical worst-case examples transfer to the quality-aware setting.When all candidate qualities equal 1, reciprocal JR reduces to JR and quality-based and standard welfare coincide.Source: H. Welfare-Price of Representation · p. 45
  • Standard JR admits a welfare approximation bound that also applies to value-JR, but that example requires minimum quality in O(1/k).The section contrasts this with threshold-JR, whose poor bound persists when the minimum quality is arbitrarily close to 1.Source: H. Welfare-Price of Representation · p. 45
  • Threshold-JR can retain a welfare ratio approaching 1/k even when the minimum candidate quality is 1−ε for arbitrarily small ε.In the example, k=n, with k unanimously approved candidates of quality 1−ε and one distinct quality-1 candidate per voter; threshold-JR forces the distinct candidates.Source: H. Welfare-Price of Representation · pp. 45–46
  • A value-JR committee with a welfare guarantee depending on minimum quality can be computed in polynomial time when k ≥ 4.The construction uses a greedy-JR procedure and candidates ranked by value h_c · |V[c]|.Source: H. Welfare-Price of Representation · p. 46

Related papers

Loading 2609.08830v1…