acceptodds
Under review as a conference paper at ICLR 2027

Strengthening Full Justified Representation in Approval-Based Committee Elections

Abstract

In approval-based committee elections, _proportional representation_ aims to give voter groups representation in proportion to their size. Full justified representation (FJR) provides a strong guarantee, but checking whether a committee satisfies it is computationally hard, even though such committees can be found efficiently. We introduce full justified representation+ (FJR+), which strengthens both FJR and extended justified representation+ (EJR+) and can always be achieved and verified in polynomial time. The key idea is to allow fractional weights when assessing underrepresentation, making violations detectable through linear programming. A greedy procedure based on equal voter budgets selects a partial committee that can be completed in any way while retaining FJR+. We use this flexibility to obtain two further guarantees. The final committee lies in the sub-core: no group can use its proportional share to give every member all their approved winners and an additional approved candidate. Whenever enough candidates receive approval to fill the committee, it is also priceable, which gives an equal-budget payment interpretation. Finally, we extend the approach to approval-based participatory budgeting with arbitrary project costs, retaining efficient verification and computation together with priceability and the sub-core.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
committee selection, multiwinner voting, proportional representation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_fjQUOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors propose FJR+, a new proportionality axiom for approval-based committee elections. The idea is to take the usual FJR violation (a group S, a candidate set T, a level l such that S is large enough to afford T, every member approves at least l candidates in T, and nobody in S gets l winners) and let everything be fractional: voter weights, candidate weights, and how much of each candidate is assigned to each voter. The one twist that makes this work is that the "assignment at most voter weight" constraint is only enforced for elected candidates. With 0/1 weights, you recover FJR exactly; with a weight on a single candidate, you recover EJR+. The relaxation is strictly stronger than FJR and EJR+ together (Prop 3.4 is a 5-voter example), and since it is an LP, you can check it in polynomial time, one LP per level.

On the algorithmic side, they analyze a budget-greedy rule, RBG, which is essentially the Frank-Peters rule with Ai's exact charging. Voters start with a unit budget; levels go from k down to 1; and a candidate is bought when its approvers, who are still below the current level, can jointly pay the quota, each contributing at most their remaining budget divided by the number of additional approved winners they need. The main theorem is that whatever RBG selects, any completion to size k satisfies FJR+, and this holds for any choice of candidate and any way of splitting the payment. They then use that freedom: finishing with sequential Phragmén from RBG's loads provides priceability (when enough candidates have approvers) and, hence, the sub-core. The last section redoes everything for participatory budgeting, with arbitrary costs approved by utilities.

The appendix includes the usual separation examples (FJR+ vs sub-core vs core), a proof that Core+ from the recent Becker-Greger-Peters paper implies FJR+, a counterexample showing that FJR+ is not monotone, and a party-list characterization (it is just a lower quota there).

No experiments. Everything is proofs and small worked examples. The coreset and LLM-summarization motivation from the intro is never revisited.

Critical strengths

The PB extension with arbitrary project costs (Section 6, Appendices E-F). For approval utilities, this gives, as far as I can tell, the first polynomial-time rule satisfying PB-FJR, and in fact the stronger PB-FJR+, together with priceability and the PB sub-core. Frank-Peters and Ai are committee-only, and the Greedy Cohesive Rule of Peters et al. is not known to be polynomial. This is the one result Becker et al. do not touch, and it is the reason I am at a reject rather than a strong reject. It is also buried, and the paper does not make the case for it.

The every-completion, every-payment robustness of RBG (Theorem 4.1). Being able to establish the representation guarantee on a partial committee and then spend the remaining seats on other properties (priceability, sub-core) is a useful design pattern, and the proof that it survives the lift from integral to fractional comparisons is tidy. I weigh this less than it might deserve because Appendix I concedes the same completion-robustness already holds for Ai’s rule at the FJR level, so what is new is the “+”, not the pattern.

Critical weaknesses
  1. The headline result is subsumed by Core+, and the paper's own appendix shows the stronger property is cheaper to verify. The question the paper sets itself (an axiom that strengthens FJR and EJR+, verifiable and achievable in polynomial time) is answered by Becker, Greger and Peters for every quota in (n/(k+1), n/k], with polynomial-time computation, and Prop G.2 here proves Core+ implies FJR+. As the authors themselves write Core+ in Appendix G.2, a violation has no level index, so it is decided by one LP rather than k. That leaves "we can decide FJR+ itself" with no stated reason anyone would want the weaker test at k times the cost. The paper lists what survives (every-completion robustness, Droop, PB), but Appendix I concedes the completion robustness already holds for Ai's rule, and Ai already gives Droop-FJR in polynomial time, so on the committee side only the "+" is new. What is left is an analytical unification of three cited papers, which is below the bar for this venue. This is the main reason for my score.

  2. The ML motivation is unevaluated and is contradicted by the paper's own negative result. The intro sells FJR+ through coreset selection and LLM opinion summarization, and the scenario of auditing a selection after it has been revised. There is no experiment of any kind, and the conclusion admits practical running times; the effect on training data or summaries is unknown. More to the point, Prop G.6 shows FJR+ fails monotonicity: adding approvals only for already-elected candidates can break it, which EJR+ never does. In the closest formal version of the paper's own "edit the selection" story, the new axiom is less robust than the one it claims to improve on, and this is disclosed only in Appendix G.3. For an ICLR paper, the ML framing is the venue case, and it does not hold up.

Questions for authors

Questions that could change my score

  1. Given Core+ (Becker et al.) is achievable in polynomial time at every quota in (n/(k+1), n/k] and, in your own Appendix G.2 formulation, is decided by a single LP: what is the concrete case for an auditor to run the k-LP FJR+ test instead? If there is a setting where FJR+ is the right target and Core+ is not (cost, interpretability, PB), say which and why.

  2. Appendix I concedes that Ai's rule already satisfies FJR for every size-k completion. Is there a committee result in the paper that does not reduce to "known rule, known argument, lifted to fractional weights"? I am asking what you claim as new on the committee side once Core+, Frank-Peters and Ai are taken as given.

  3. Does Droop-FJR+ strictly strengthen Droop-FJR together with Droop-EJR+? Prop 3.4 is Hare-only and its instance is already a Droop-FJR violation, so it does not separate at Droop.

  4. For participatory budgeting, does any version of PB-FJR+ survive under cost utilities (Brill et al. 2023), rather than counting approved projects regardless of cost? A positive answer would raise my view of Section 6 considerably.

Clarifications

  1. Your three threshold examples (Props 3.4, B.1, G.6) all sit at Z = q Y exactly. What exact-arithmetic LP procedure do you have in mind for Theorem 3.5, and what is its running time? "Khachiyan (1979)" is not an algorithm one would run.

  2. What is the intended reading of a fractional violation with voter weights above one (z = 3/2 in Prop 3.4), where no integral coalition affords the comparison set? Is FJR+ meant as a property with a normative story, or as a technical interpolant between FJR/EJR+ and Core+?

  3. Figure 1 has an arrow from Sub-core to FPJR. Kalayci et al. prove priceability and core imply FPJR; where is sub-core alone shown to imply it?

  4. Appendix J: please derive a <= 4q and b <= q+1 from the Munagala et al. reduction, or restate in terms of n and q.

Not affecting my score, for a future version

  1. A distributional study (Pabulib, PrefLib, or the two motivating pipelines) of how often FJR+, FJR together with EJR+, Core+ and the sub-core actually disagree, and what an exact FJR+ check costs end to end.

  2. The LP value max over levels of Z*(l)/q_H is a continuous degree-of-violation measure; reducing it to a Boolean discards what the revised-training-set story would actually need.

Reviewer_QieBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In approval-based committee voting (ABC), every voter indicates which candidates she approves, and a committee of a predetermined size is selected. The goal of proportional representation is for groups of voters to receive representation that reflects both their size and their approvals. Existing representation axioms express this by giving conditions for when a group is “underrepresented”: the group is large enough and sufficiently cohesive (overlapping) in its approvals to justify some representation, yet the selected committee leaves the group's members below that level.

The previously established axioms capture different kinds of claims. FJR asks whether a sufficiently large group could justify a small enough set of candidates that each member approves sufficiently many candidates from it, even if different members approve different candidates. However, checking whether a given committee satisfies FJR is computationally hard. EJR+ is efficiently checkable, but is limited in the anomalies it captures as it focuses on groups united by approval of a single unelected candidate. The paper notes that these approaches can miss simple cases where overlapping approvals within a group suggest underrepresentation.

The paper introduces FJR+, a fractional version of the representation condition. It captures every violation of either FJR or EJR+, and also detects some additional cases. The authors show that FJR+ can be checked in polynomial time and that a committee satisfying it can be computed in polynomial time. Their Residual-Budget Greedy (RBG) method selects a partial committee that preserves FJR+ under any completion.

The paper further makes the case for its proposed FJR+. This includes the ability to guarantee FJR+ and “priceability,” which gives the committee an equal-voter-budget payment interpretation. It also allows for the “sub-core” guarantee that rules out a clear representation improvement: there is no sufficiently large group and alternative candidate set that would let every member keep all the elected candidates they approve and strictly more. Finally, the paper extends its approach to participatory budgeting, where projects have different costs, and establishes efficient verification and computation guarantees there as well.

Critical strengths
  1. The paper contributes a valuable strengthening of existing representation axioms that addresses an important gap in computational social choice: existing definitions can fail to detect some simple cases of underrepresentation.

  2. The paper makes a thorough and convincing case for its proposal, examining it from several angles and supporting it with sound theoretical analysis. The arguments are well grounded and clearly presented.

  3. The algorithms draw nicely on well-established ideas, including equal voter budgets and sequential Phragmén, giving the constructions a clear conceptual basis alongside their technical details and analysis of guarantees.

  4. The paper is very well organized and generally well and carefully written. In particular, it is very clear what each part contributes to the overall story.

Critical weaknesses
  1. My main concern is the paper's relevance to ICLR. The first paragraph of the Introduction motivates the work through machine-learning applications, including training-set selection and LLM-generated summaries. However, these examples do not develop into a substantive connection with learning. And indeed, no mention of learning remains after the first paragraph. It reads like a paper from a different field, artificially adapted for ICLR. The contributions concern core topics in computational social choice: representation axioms and their social and computational properties. The paper makes an important contribution to social choice and computational social choice, but I do not see a sufficiently strong connection to ICLR's focus. This concern weighs heavily in my assessment.

  2. While the paper provides formal justification for the FJR+ definition, I found the intuition for the fractional formulation unclear. From a modeling perspective, what does it mean to assign fractional weights to voters, candidates, and assignments? The paper explains what this formulation achieves analytically, but does not give enough intuition for why fractional comparisons provide any meaningful account of underrepresentation. What in real life corresponds to the numbers? The lack of an intuitive understanding of why fractions make sense is a concern about adopting the proposal. The presentation of some prior representation axioms could also be made more intuitive, though this is a secondary concern.

Questions for authors

(1) Please explain why ICLR is the proper venue for this paper (Weakness 1).

(2) Please explain whether you can improve the intuition behind the main definition (Weakness 2).

Reviewer_p3rAOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces full justified representation+ (FJR+), an axiom for approval-based multiwinner voting. The axiom strengthens both FJR and EJR+, and can be verified in polynomial time. Further, a residual budget greedy mechanism is proposed to obtain a FJR+ committee, incurring polynomial runtime.

Critical strengths
  1. FJR+ strengthens FJR, and achieves verifiability in polynomial time.
  2. The greedy mechanism in Sec 4 is elegant and flexible. The completion may satisfies some more axioms additionally.
  3. The proofs are correct as far as i checked.
Critical weaknesses
  1. Comparing with FJR, FJR+ only excludes the fractional violations. The definition is natural, but lack of justification. Why should these violations should be excluded? It remains unclear for me.
  2. The advantages of FJR+ over EJR+ also need to be justified, especially when it loses monotonicity (Prop G.6).
  3. Def 3.1 lack of intuition. Maybe it can be compacted, e.g., the following version

Given WW, ℓ\ell, a level-ℓ\ell fractional violation exists if and only if there are nonnegative candidate weights ycy_c and nonnegative voter weights ziz_i that ∑i∈N,∣Ai∩W∣<ℓzi>0\sum_{i \in N,|A_i \cap W| < \ell} z_i > 0, satisfying

  • Proportional affordability: ∑c∈Cyc≤kn⋅∑i∈N,∣Ai∩W∣<ℓzi\sum_{c\in C} y_c \le \frac{k}{n}\cdot \sum_{i \in N,|A_i \cap W| < \ell} z_i;
  • Sufficient weight: for every i∈Ni \in N with ∣Ai∩W∣<ℓ|A_i \cap W| < \ell, ∑c∈Ai∖Wyc+∑w∈Ai∩Wmin⁡(yw,zi)≥ℓzi\sum_{c\in A_i\setminus W} y_c+\sum_{w\in A_i\cap W}\min(y_w,z_i) \ge \ell z_i.
  1. The algorithmic contribution seems to be incremental. The RBG mechanism combines two techniques by Frank&Peters and Ai. And the central per-voter payment bound is already presented.
Questions for authors

Please address my weakness 1 and 2 above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.