- 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
-
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.
-
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
-
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.
-
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.
-
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.
-
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
-
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.
-
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+?
-
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?
-
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
-
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.
-
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.