Full Justified Representation under Hare and Droop Quotas in Polynomial Time

2026/08/05 by Yizhou Ai
Computer Science · #cs.GT

paper · pdf

26 pages, 1 figure

arxiv created 2026/08/05 · arxiv updated 2026/08/07

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 λ_H=n/k, the algorithm returns a Hare-FJR committee; with candidate price λ_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.

Citations

• Core Existence in Approval-Based Committee Elections with up to Five Voter Types
• On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting
• Likelihood of the Existence of Average Justified Representation
• Justified Representation: From Hare to Droop
• The Core of Approval-Based Committee Elections with Few Seats
• Full Proportional Justified Representation
• Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting
• An Adaptive and Verifiably Proportional Method for Participatory Budgeting
• Best-of-Both-Worlds Fairness in Committee Voting
• Proportionality in Approval-Based Participatory Budgeting
• Robust and Verifiable Proportionality Axioms for Multiwinner Voting
• The Complexity of Proportionality Degree in Committee Elections
• Individual Representation in Approval-Based Committee Voting
• Approximate Core for Committee Selection via Multilinear Extension and Market Clearing
• Core-Stable Committees under Restricted Domains
• Proportional Participatory Budgeting with Additive Utilities
• Multi-Winner Voting with Approval Preferences
• Proportionality and the Limits of Welfarism
• Proportionality and the Limits of Welfarism
• Approximately Stable Committee Selection
• Group Fairness in Committee Selection
• Phragmén's Voting Methods and Justified Representation
• Proportional Justified Representation
• Justified Representation in Approval-Based Committee Voting