Full Justified Representation under Hare and Droop Quotas in Polynomial Time

Yizhou Ai

Full Justified Representation under Hare and Droop Quotas in Polynomial Time

T0 review · 0 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single descending-budget algorithm now computes exact justified representation in polynomial time.

desk verdict This is the real thing: a polynomial-time algorithm for Hare- and Droop-FJR, and the proofs survive a close read. read the letter →

arxiv 2608.05417 v1 pith:I753YN3C submitted 2026-08-05 cs.GT

Yizhou Ai This is my paper · ORCID

classification cs.GT MSC 91B1291B14

keywords approval-basedmultiwinnerelectionsFullJustifiedRepresentationHarequotaDroopproportionalbudget-basedalgorithmpolynomial-timeconstruction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper presents a single deterministic algorithm for approval-based multiwinner elections and proves that it satisfies Full Justified Representation (FJR), the strongest standard proportionality guarantee in this setting. With candidate price n/k it outputs a Hare-FJR committee, and with candidate price n/(k+1) it outputs a committee satisfying the stricter Droop-FJR axiom; both runs use O(kmn) rational operations. The result matters because efficient rules previously guaranteed only weaker axioms such as EJR, while the known FJR constructions were not known to run in polynomial time. The proof rules out every possible FJR violation by a double-counting argument anchored on one invariant about voters' payments.

What carries the argument

Gap-normalized offers $\alpha$^(t)_{i,h} = r^(t)_i / (h - u_i(P^(t))) together with the historical-payment invariant carry the argument. The invariant says that whenever a voter is active at a decision snapshot, her current offer is at least every payment she made for an earlier selected candidate; this allows past payments on candidates outside a potential witness set to be replaced by current offers, so each active voter assigns mixed cost at least 1 to any approved set of size h. The same invariant and row-column accounting give both FJR theorems, with the Droop proof adding only the full-seat residual-budget lemma.

What would settle it

Exhaustively enumerate all approval profiles with small parameters (for instance n up to 7, m up to 7, k up to 4) together with all voter and candidate orders; for each run of the algorithm, brute-force check every triple (S,T,l) for a Hare- or Droop-FJR violation. A single violating committee would refute the theorem; finding none in the full enumeration would strongly support it but would not prove it.

Watch

Extended reading notes

Core claim

At each representation target h, the algorithm treats every voter who approves at least h candidates but currently has fewer than h winners as active; her offer to each unselected approved candidate is her remaining budget divided by the number of additional winners she still needs. A candidate is purchased when the offers of active approvers reach the common price. The paper's central claim is that this process cannot output an FJR-violating committee: at the terminal snapshot of the witness level, each witness voter has mixed cost at least 1 on her approved part of the witness set, while the same costs summed by candidate fall strictly below the quota-scaled size of the witness set, contradicting the definition. For the Droop price, the case where all k seats are purchased before the witness phase ends is handled by a separate residual-budget lemma showing the witness voters would need to retain more than the exact leftover total n/(k+1).

Load-bearing premise

The entire result rests on the invariant that a voter who is still short of the current representation target never offers less for her next seat than she paid for any earlier seat; if that invariant could fail on some valid run, both FJR theorems would collapse.

Editorial extensions

If this is right

Every explicitly represented approval-based election admits a size-k Hare-FJR committee, and the algorithm constructs one deterministically in O(kmn) rational operations once voter and candidate orders are fixed.
Every such election also admits a Droop-FJR committee, so the stronger Droop-quota version of FJR is constructible in polynomial time, not just known to exist.
Because FJR implies EJR, PJR, and JR, every output committee satisfies the full classical justified-representation hierarchy from EJR downward.
The Droop-price output automatically satisfies Hare-FJR, so the same algorithm covers both quota conventions with only a one-line price change.
All arithmetic is exact rational arithmetic with denominators of bounded bit length, so the polynomial bound holds in the binary input model, not merely in a value-based model.

Reading between the lines

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

The same gap-normalized idea should transfer to additive-utility participatory budgeting, where the representation gap is a real-valued utility shortfall rather than an integer approval count; such a transfer would need a new proof of the analogue of the historical-payment invariant.
A likely route to anonymity and neutrality is to replace the fixed candidate order with any tie-breaking rule that preserves the invariant, since the proof does not otherwise use the order.
Because FJR verification is coNP-complete, the algorithm's output cannot be certified by direct search; in practice, a proof certificate would have to encode the invariant chain itself, pointing toward machine-checkable verification of the double-counting argument.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this paper closes the polynomial-time FJR construction problem, and the proof is solid. I went through the key lemmas the way you would, and they hold. The gap-normalized offer is the right new ingredient; without it, MES-style budgets don't track how far a voter is from the current threshold. The descending phase order plus the historical-payment invariant (Lemma 5.2) is what makes the double counting work, and the Droop full-seat case is a genuinely separate argument, not a rehash of the Hare one.

What's new: both a Hare-FJR and a Droop-FJR construction in O(kmn) rational operations, deterministic given fixed orders. The proofs are by contradiction from invariants, not by assuming the conclusion. The row-column accounting is standard in spirit, but the mixed cost (historical payments for selected, current offers for unselected) is clever, and Lemma 5.5 is the moment where everything clicks.

Soft spots are minor. The algorithm is not neutral or anonymous; the paper says so. The bit-complexity bound is polynomial but the exponent depends on k^2 log k; that's fine for a theory result but could matter in practice, not that anyone would run this on large instances. The related-work section includes a hierarchy of SJR/AJR that isn't used later; it's a bit of a detour but not wrong. There's no code, but for a computational social choice theory paper that's not a red flag. The self-citation [AT26] is only for terminology, so no issue.

The paper deserves a serious referee. If I were the editor, I'd send it out. The central claim is important and the proof looks correct; the only things a referee might quibble with are presentation-level. I'd also bring it to the reading group.

Referee Report

0 major / 4 minor

Summary. The paper presents a deterministic polynomial-time algorithm, termed the descending-budget algorithm, that constructs committees satisfying Full Justified Representation (FJR) under both Hare and Droop quota conventions. For any approval-based multiwinner election and fixed voter/candidate orders, the algorithm with candidate price λH = n/k returns a Hare-FJR committee, while with price λD = n/(k+1) it returns a committee satisfying the more demanding Droop-FJR axiom of Casey and Elkind. The algorithm maintains a virtual budget per voter, computes gap-normalized offers, and uses capped charging; the proof relies on a historical-payment invariant and a row–column double-counting argument. The paper also establishes an O(kmn) rational-operation bound with polynomial bit complexity.

Significance. If the result holds, it resolves an open problem: FJR committees were previously known to exist via the non-polynomial Greedy Cohesive Rule, and no polynomial-time construction was known for either Hare-FJR or Droop-FJR. The proof is self-contained and the key invariant (Lemma 5.2) is verified carefully; the double-counting arguments are elegant and the Droop full-seat lemma is a neat use of residual budgets. The algorithm is deterministic and parameter-free, and the runtime is polynomial in the input size. These strengths make the paper a substantial contribution to the justified-representation literature. I verified the core lemmas (5.2, 5.5, 5.7, 5.9) independently and found no gap.

minor comments (4)

[Abstract] The first sentence of the abstract reads 'I studyFull Justified Representation'; a space is missing between 'study' and 'Full'. This is the only typographical issue I found in the abstract.
[Algorithm 2 (Section 3.4)] The two 'break' statements inside the for-loop of Algorithm 2 exit only the inner 'while' loop. After the paid construction reaches t = k, the outer 'for' loop continues through the remaining phases, each with an empty while iteration. Consider restructuring the control flow or adding a comment so that readers do not mistakenly think the entire algorithm halts at that point.
[Section 5.1, Lemma 5.2] In the same-phase case of the proof, the equality a' - a = (a - x)/(d-1) uses r = a d; spelling out this substitution would improve readability.
[Section 1.2] The implication chain 'Core Stability =⇒ FJR' is mentioned without a formal definition of core stability. Since the paper does not rely on core stability, a one-sentence informal definition or a pointer to the references would be enough for readers outside the subfield.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: FJR guarantees are proved from algorithm invariants and quota definitions.

full rationale

No circular step is present. The central results (Theorems 5.8 and 5.10) are established by direct contradiction proofs from algorithm-specific facts: budget conservation (Lemma 5.1), the historical-payment invariant (Lemma 5.2), and the row/column accounting bounds (Lemmas 5.5 and 5.6). These lemmas are derived from the algorithm's own definitions—gap-normalized offers, capped charging, and normal terminal snapshots—rather than assumed from the FJR axiom or from external work. The price λH = n/k and λD = n/(k+1) is fixed by the quota definitions and is not fitted to data or to the axiom; the same algorithm with different prices yields the two guarantees. The only self-citation, [AT26], appears in related-work terminology and Figure 1 and is not used anywhere in the construction or proofs. The Droop full-seat lemma (Lemma 5.9) supplies an independent residual-budget argument specific to the Droop price. The noted limitations—deterministic order-dependence and open optimization questions—are explicitly stated in Section 6 and do not undermine the claimed derivation. The derivation is self-contained.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on the standard election model, the prior definitions of Hare-FJR and Droop-FJR, and elementary arithmetic. The algorithm introduces no free parameters: the candidate price lambda is fixed by the quota convention (lambda_H = n/k or lambda_D = n/(k+1)), and the voter/candidate orders are arbitrary deterministic tie-breakers that do not affect the guarantees. No new entities are postulated.

assumptions (3)

domain assumption Standard approval-based multiwinner election model with additive approval utilities and unit voter budgets
Section 2, Definitions 2.1 and 2.3. This is the standard model in the cited literature; the algorithm's guarantees are relative to this model.
domain assumption Hare-FJR and Droop-FJR definitions as given by PPS21 and CE26, including the strict Droop threshold |S| > n|T|/(k+1)
Section 2, Definitions 2.4 and 2.5. The paper follows prior definitions rather than introducing new ones; the Droop convention follows Casey and Elkind.
standard math Exact rational arithmetic with bounded denominator growth
Section 4. The bit-length analysis relies on standard facts about least common multiples and reduced fractions; the bound log L = O(k log k) is elementary.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Full Justified Representation under Hare and Droop Quotas in Polynomial Time." pith.science (2026). https://pith.science/paper/I753YN3C

@misc{pith2026260805417,
  author       = {Pith},
  title        = {Pith review of: Full Justified Representation under Hare and Droop Quotas in Polynomial Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I753YN3C}},
  note         = {Machine review of arXiv:2608.05417}
}

abstract

I study Full Justified Representation (FJR) in approval-based multiwinner elections under both the Hare and Droop quota conventions. I introduce a descending-budget algorithm in which voters distribute their remaining budgets across their current representation gaps and candidates are purchased whenever the resulting offers cover a common price. With candidate price $\lambda_H=n/k$, the algorithm returns a Hare-FJR committee; with candidate price $\lambda_D=n/(k+1)$, it returns a committee satisfying the more demanding Droop-FJR axiom of Casey and Elkind. The two guarantees share a historical-payment invariant and a terminal row--column accounting argument, while the Droop proof requires a new residual-budget argument when all $k$ paid seats are filled. Both variants are deterministic once the voter and candidate orders are fixed and use $O(kmn)$ rational operations.

Figures

Figures reproduced from arXiv: 2608.05417 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Strengthening Full Justified Representation: Efficient Verification and Computation
cs.GT 2026-08 accept novelty 7.0 of 10

A new verifiable proportionality axiom, FJR+, dominates both FJR and EJR+, is checked by linear programming, is achieved by a greedy rule, and admits a priceable completion.

Reference graph

Works this paper leans on

53 extracted references · 49 canonical work pages · cited by 1 Pith paper

[1]

Social Choice and Welfare , volume =

Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh , title =. Social Choice and Welfare , volume =
[2]

Proportional justified representation , journal =

Luis Sánchez-Fernández and Edith Elkind and Martin Lackner and Fern. Proportional justified representation , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.artint.2026.104503 , url =

work page arXiv 2026
[3]

Theoretical Computer Science , volume=

Justifying groups in multiwinner approval voting , author=. Theoretical Computer Science , volume=. 2023 , publisher=

work page 2023
[4]

Proceedings of the 22nd

Lirong Xia , title =. Proceedings of the 22nd

work page
[5]

Martin Lackner and Piotr Skowron , title =
[6]

Proceedings of the Thirty-First

Markus Brill and Rupert Freeman and Svante Janson and Martin Lackner , title =. Proceedings of the Thirty-First

work page
[7]

Brill, Markus and Freeman, Rupert and Janson, Svante and Lackner, Martin , journal=. Phragm. 2024 , publisher=

2024
[8]

The Complexity of Proportionality Degree in Committee Elections , booktitle =

Janeczko,. The Complexity of Proportionality Degree in Committee Elections , booktitle =

work page

Show all 53 references

[9]

Thirty-Sixth

Markus Brill and Jonas Israel and Evi Micha and Jannik Peters , title =. Thirty-Sixth
[10]

Social Choice and Welfare , volume=

Individual representation in approval-based committee voting , author=. Social Choice and Welfare , volume=. 2025 , publisher=

2025
[11]

Proceedings of the 21st

Dominik Peters and Piotr Skowron , title =. Proceedings of the 21st
[12]

Verifying Proportionality in Temporal Voting , booktitle =

Edith Elkind and Svetlana Obraztsova and Nicholas Teh , editor =. Verifying Proportionality in Temporal Voting , booktitle =
[13]

On the Complexity of Extended and Proportional Justified Representation , booktitle =

Haris Aziz and Edith Elkind and Shenwei Huang and Martin Lackner and Luis S. On the Complexity of Extended and Proportional Justified Representation , booktitle =
[14]

Market-Based Explanations of Collective Decisions , booktitle =

Dominik Peters and Grzegorz Pierczy. Market-Based Explanations of Collective Decisions , booktitle =
[15]

How to Sample Approval Elections? , booktitle =

Stanis. How to Sample Approval Elections? , booktitle =
[16]

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems,

The Degree of (Extended) Justified Representation and Its Optimization , author=. Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems,
[17]

Fair Multiwinner Elections with Allocation Constraints , booktitle =

Ivan. Fair Multiwinner Elections with Allocation Constraints , booktitle =
[18]

Proportional Representation: Apportionment Methods and Their Applications , pages=

Quota Methods of Apportionment: Divide and Rank , author=. Proportional Representation: Apportionment Methods and Their Applications , pages=. 2017 , publisher=

2017
[19]

Full Proportional Justified Representation , year =

Kalayc. Full Proportional Justified Representation , year =. Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems,
[20]

CoRR , volume =

Lirong Xia , title =. CoRR , volume =. 2025 , url =

2025
[21]

Advances in Neural Information Processing Systems , volume=

Proportional participatory budgeting with additive utilities , author=. Advances in Neural Information Processing Systems , volume=
[22]

Contributions to the Theory of Games , volume=

Solutions to general non-zero-sum games , author=. Contributions to the Theory of Games , volume=
[23]

Journal of Economic Theory , volume=

On market games , author=. Journal of Economic Theory , volume=. 1969 , publisher=

1969
[24]

, author=

An Experimental View on Committees Providing Justified Representation. , author=. IJCAI , pages=
[25]

Proceedings of the 19th Conference on Web and Internet Economics , pages =

Aziz, Haris and Lu, Xinhang and Suzuki, Mashbat and Vollen, Jeremy and Walsh, Toby , title =. Proceedings of the 19th Conference on Web and Internet Economics , pages =
[26]

Proceedings of the 24th ACM Conference on Economics and Computation , pages=

Robust and Verifiable Proportionality Axioms for Multiwinner Voting , author=. Proceedings of the 24th ACM Conference on Economics and Computation , pages=. 2023 , doi=

2023
[27]

Proceedings of the 26th ACM Conference on Economics and Computation , pages=

Computing Lindahl Equilibrium for Public Goods with and without Funding Caps , author=. Proceedings of the 26th ACM Conference on Economics and Computation , pages=
[28]

Econometrica: Journal of the Econometric Society , pages=

Lindahl's Solution and the Core of an Economy with Public Goods , author=. Econometrica: Journal of the Econometric Society , pages=. 1970 , publisher=

1970
[29]

International conference on web and internet economics , pages=

The core of the participatory budgeting problem , author=. International conference on web and internet economics , pages=. 2016 , organization=

2016
[30]

Proceedings of the 21st ACM Conference on Economics and Computation , pages=

Best of both worlds: Ex-ante and ex-post fairness in resource allocation , author=. Proceedings of the 21st ACM Conference on Economics and Computation , pages=
[31]

Proceedings of the 25th ACM Conference on Economics and Computation , pages=

Maximum flow is fair: A network flow approach to committee voting , author=. Proceedings of the 25th ACM Conference on Economics and Computation , pages=
[32]

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Likelihood of the Existence of Average Justified Representation , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

2026
[33]

Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

Fair mixing: the case of dichotomous preferences , author=. Proceedings of the 2019 ACM Conference on Economics and Computation , pages=

2019
[34]

Proceedings of the AAAI Conference on Artificial Intelligence , volume=

On the edge of core (non-) emptiness: An automated reasoning approach to approval-based multi-winner voting , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
[35]

, title =

Thiele, Thorvald N. , title =. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger , year =
[36]

ACM Transactions on Economics and Computation , volume =

Group Fairness in Committee Selection , author =. ACM Transactions on Economics and Computation , volume =. 2020 , doi =

2020
[37]

Proceedings of the AAAI Conference on Artificial Intelligence , volume =

Fair Lotteries for Participatory Budgeting , author =. Proceedings of the AAAI Conference on Artificial Intelligence , volume =. 2024 , doi =

2024
[38]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =

Approximately Stable Committee Selection , author =. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2020 , doi =

2020
[39]

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

Approximate Core for Committee Selection via Multilinear Extension and Market Clearing , author =. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2022 , organization =

2022
[40]

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , pages =

The Core of Approval-Based Committee Elections with Few Seats , author =. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence , pages =. 2025 , doi =

2025
[41]

2026 , eprint =

Core Existence in Approval-Based Committee Elections with up to Five Voter Types , author =. 2026 , eprint =

2026
[42]

Proceedings of the 22nd ACM Conference on Economics and Computation , pages =

Proportionality Degree of Multiwinner Rules , author =. Proceedings of the 22nd ACM Conference on Economics and Computation , pages =. 2021 , doi =

2021
[43]

2026 , eprint =

Ai, Yizhou and Tao, Biaoshuai , title =. 2026 , eprint =

2026
[44]

Proceedings of the 18th International Conference on Web and Internet Economics , pages =

Core-Stable Committees under Restricted Domains , author =. Proceedings of the 18th International Conference on Web and Internet Economics , pages =. 2022 , publisher =

2022
[45]

2025 , eprint =

Computation of Approximately Stable Committees in Approval-Based Elections , author =. 2025 , eprint =

2025
[46]

Proceedings of the 2018 ACM Conference on Economics and Computation , pages =

Fair Allocation of Indivisible Public Goods , author =. Proceedings of the 2018 ACM Conference on Economics and Computation , pages =. 2018 , doi =

2018
[47]

2026 , howpublished =

Fractional Pareto-Optimality in Multiwinner Voting , author =. 2026 , howpublished =

2026
[48]

International Conference on Web and Internet Economics , pages=

An adaptive and verifiably proportional method for participatory budgeting , author=. International Conference on Web and Internet Economics , pages=. 2023 , organization=

2023
[49]

Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , volume=

Completing priceable committees: utilitarian and representation guarantees for proportional multiwinner voting , author=. Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI) , volume=. 2024 , organization=

2024
[50]

arXiv preprint arXiv:2605.04612 , year=

An Axiomatic Analysis of Proportionality Notions in Approval-Based Multiwinner Voting , author=. arXiv preprint arXiv:2605.04612 , year=

arXiv
[51]

Proceedings of the AAAI Conference on Artificial Intelligence , volume=

Proportionality in approval-based participatory budgeting , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
[52]

Proceedings of the AAAI Conference on Artificial Intelligence , volume=

Utilitarian guarantees for the method of equal shares , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=
[53]

and Elkind, Edith , title =

Casey, Matthew M. and Elkind, Edith , title =. Web and Internet Economics , series =. 2026 , doi =

2026

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Social Choice and Welfare , volume =

Haris Aziz and Markus Brill and Vincent Conitzer and Edith Elkind and Rupert Freeman and Toby Walsh , title =. Social Choice and Welfare , volume =

[2] [2]

Proportional justified representation , journal =

Luis Sánchez-Fernández and Edith Elkind and Martin Lackner and Fern. Proportional justified representation , journal =. 2026 , issn =. doi:https://doi.org/10.1016/j.artint.2026.104503 , url =

work page arXiv 2026

[3] [3]

Theoretical Computer Science , volume=

Justifying groups in multiwinner approval voting , author=. Theoretical Computer Science , volume=. 2023 , publisher=

work page 2023

[4] [4]

Proceedings of the 22nd

Lirong Xia , title =. Proceedings of the 22nd

work page

[5] [5]

Martin Lackner and Piotr Skowron , title =

[6] [6]

Proceedings of the Thirty-First

Markus Brill and Rupert Freeman and Svante Janson and Martin Lackner , title =. Proceedings of the Thirty-First

work page

[7] [7]

Brill, Markus and Freeman, Rupert and Janson, Svante and Lackner, Martin , journal=. Phragm. 2024 , publisher=

2024

[8] [8]

The Complexity of Proportionality Degree in Committee Elections , booktitle =

Janeczko,. The Complexity of Proportionality Degree in Committee Elections , booktitle =

work page