Strengthening Proportionality in Participatory Budgeting with Additive Utilities

1 Introduction

• Strong NP-hardness of finding an FJR outcome for general additive utilities leaves polynomial-time proportionality guarantees as the central open challenge.Baharav et al. also rule out FJR for a class of sequential rules, while checking FJR for approval committees is coNP-complete [Kalayci et al., 2025].Source: §1 · p. 2
• The paper asks whether FJR up to one project can extend additive EJR's relaxation while permitting polynomial-time computation and verification.The strict relaxation requires a member either to meet the target or to exceed it after adding a project from the group's proposed set.Source: §1 · p. 2

1.1 Our Contributions

• FJR up to one project is computable in polynomial time for nonnegative additive utilities and arbitrary project costs, and the stronger FJR1+ axiom is polynomial-time verifiable.FJR1+ specializes exactly to approval FJR+ [Teh, 2026a].Source: §1.1 · p. 2
• Every feasible completion of the algorithm's selected set preserves FJR1+, including a completion that is priceable at the original budget.The algorithm extends Residual-Budget Greedy (RBG) [Teh, 2026a].Source: §1.1 · p. 2
• For unit-cost projects, the guarantee strengthens from the Hare quota n/k to the strict Droop quota n/(k + 1), with priceability when at least k projects have positive value to some voter.Sequential Phragmén provides the priceable completion; on approval ballots the outcome satisfies Droop-FJR+ and priceability.Source: §1.1 · p. 2
• The additive extension caps offers to address projects worth more than a voter's remaining requirement and skips utility intervals to avoid iterating over many levels.Verification need only test target levels ui(W) + ui(c) for unselected positively valued projects; treating every positively valued project as approved does not suffice.Source: §1.1 · pp. 2–3

1.2 Related Work

• FJR1+ retains approval FJR+'s fractional basis but adds an additive utility equation and a one-project restriction on unselected projects.Its linear programs verify arbitrary proposed outcomes, unlike the AMES check, which depends on choices made by that algorithm.Source: §1.2 · p. 3
• The construction combines additive MES's capped utility-proportional payments with RBG's division by remaining representation requirement, supporting FJR1+ for every feasible completion.The paper contrasts this with MES, whose committees need not admit an exact-FJR completion [Frank and Peters, 2026].Source: §1.2 · p. 3

Model

• A PB instance has voters, projects with costs, a shared budget, and nonnegative additive voter utilities; each voter has a normalized equal budget share.A feasible outcome costs at most the budget, and a completion is any feasible superset of the selected set.Source: §2 · p. 4

Representation criteria

• FJR compares a group's affordable proposed set using each member's total utility for that set, unlike additive EJR's sum of project-by-project minimum utilities.FJR requires at least one group member to reach the target utility in the selected outcome.Source: §2 · p. 4

One-project relaxation

• FJR up to one project requires a group member to meet the target or exceed it by adding an unselected project from the group's proposed set.The added project is only a comparison device, need not yield a feasible expanded outcome, and must take utility strictly above the target.Source: §2 · p. 4

Approval utilities

• On approval ballots, FJR1 is equivalent to exact FJR, while EJR1 is implied by FJR1 and the implication is strict.For approval utilities, the target is integer-valued, so a single approved project cannot take a violating member strictly above the target.Source: §2 · p. 4

One-project relaxation

• If every proposed project is worth at most εβ to each group member, FJR1 guarantees a member utility above (1 −ε)β.Thus the one-project relaxation approaches exact FJR when the target is built from many individually small projects.Source: §2 · p. 4

Fractional FJR1+

• A fractional FJR1+ violation assigns weights to voters and projects so each weighted voter falls below the target yet receives enough counted utility from affordable projects.An unselected project can count for a voter only when adding it does not take that voter strictly above the target; this one-project restriction is necessary for the axiom to be satisfiable in general.Source: §3 · p. 5

Linear-program verification

• For a fixed outcome and target, the equivalent linear program assigns project utility to voters subject to voter-specific assignment bounds and project costs counted once.A project excluded as an unselected contribution for one voter may still be counted for another; rescaling shows a violation exists exactly when the program is feasible with optimum at most one.Source: §3 · pp. 5–6

Relationship to FJR1

• FJR1+ implies FJR1 for additive utilities and coincides with approval FJR+ on approval utilities.On approval ballots, the one-project restriction is automatic at integer target levels, leaving the constraints of approval FJR+ [Teh, 2026a].Source: §3 · pp. 6–7

Verification

• At most n(m −|W|) linear programs, each with O(nm) variables and constraints, suffice to verify FJR1+ in polynomial time.The tested target levels are of the form ui(W) + ui(c) for an unselected project c.Source: §3 · p. 7
• The polynomial-time verification result is for FJR1+, not an exact test for ordinary FJR1, although it applies to arbitrary proposed outcomes.An outcome satisfying FJR on approval utilities need not satisfy the stronger FJR1+ axiom.Source: §3 · p. 7

4 Efficient Computation of the Stronger Guarantee

• The additive-utility algorithm extends the approval Residual-Budget Greedy rule.Zero-cost projects are selected initially and count toward voters’ utility without reducing budgets.Source: §4 · p. 7
• At level h, a voter below that level offers the same fraction of her remaining budget as the project supplies of her remaining utility requirement, capped at her budget.Voters already at the level do not contribute.Source: §4 · p. 7
• Every feasible completion of the algorithm’s selected set satisfies FJR1+, and the algorithm has a polynomial-time implementation.The guarantee does not depend on project order or the choice of payments within offers.Source: §4 · pp. 7, 9
• A utility-weighted budget inequality preserves a nonnegative invariant through purchases at levels at least β, while no affordable project at β would force it negative.This contradiction establishes the representation guarantee for feasible completions.Source: §4 · p. 9
• The descending-level search is polynomial: affordability can be located by binary search within at most n + 1 intervals, with at most m purchases.Intervals without an affordable project are skipped.Source: §4 · p. 9

5 Priceability at the Original Budget

• Priceability requires selected projects to be paid from equal voter budgets by voters who value them positively, with no unselected project affordable from its interested voters’ remaining budgets.At the original budget, the total available budget is not increased for either the representation guarantee or payments.Source: §5 · pp. 9–10
• A polynomial-time completion gives an outcome satisfying FJR1+ and priceability at the original budget; for approval utilities, it also satisfies the cost-based sub-core.FJR1+ holds because every feasible completion preserves the representation guarantee.Source: §5 · p. 10
• The completion adds projects while interested voters’ remaining budgets can cover their normalized cost, charging only voters who value each selected project positively.The process selects at most m projects and does not let budgets become negative.Source: §5 · p. 10
• With arbitrary costs, an exhaustive completion and a priceable completion cannot in general both be guaranteed.Alternatively, adding any feasible project until none fits preserves FJR1+, but may not preserve priceability.Source: §5 · p. 10

6 Droop Representation and Priceability for Unit Costs

• The standard Droop quota uses fixed committee size k, with k + 1 corresponding to one additional project in the unit-cost model.For arbitrary costs, the standard condition is not directly defined because a cost-based analogue would depend on cost units.Source: §6 · p. 11
• Droop-FJR1+ implies Droop-FJR1 and the Hare version, and on approval utilities it is exactly Droop-FJR+.The condition that at least k projects receive positive utility is necessary for a size-k outcome with priceability.Source: §6 · pp. 11–12
• For unit costs and budget B = k, a size-k outcome satisfying Droop-FJR1+ can be computed and verified in polynomial time.If at least k projects are positively valued by some voter, the outcome can also be priceable.Source: §6 · p. 11
• The construction runs RBG with project price n/(k + 1), stops at k projects, and uses the invariant to show every size-k completion retains Droop-FJR1+.If the relevant level ends first, the affordability argument applies; if k projects are selected first, the one-project condition bounds the invariant’s first sum by its second.Source: §6 · p. 11
• For priceability, the construction completes RBG loads using sequential Phragmén, starting from the RBG loads.The unit-cost completion uses the usual priceability definition, which allows B′ > k.Source: §6 · pp. 11–12

7 Discussion

• The approach represents weakly cohesive additive-utility groups efficiently while allowing a loss of less than one of their own projects.Its guarantee is exact on approval ballots and approaches exact FJR when individual projects are small relative to a group's utility requirement.Source: §7 · p. 12
• Extending analogous guarantees to temporal participatory budgeting remains open; the fractional approach would need to account for one alternative per round.The paper notes that finding FJR outcomes in temporal voting with known approval preferences remains open even though such outcomes always exist.Source: §7 · p. 12

Declaration of generative AI use

• The authors used GPT-6 to explore proof ideas and revise exposition, checked the mathematical arguments, and accept responsibility for the paper.Source: Declaration of generative AI use · p. 12

• When U = 0, no fractional violation is possible and the algorithm returns its initial zero-cost projects.Source: A Polynomial-Time Implementation · p. 14
• Inspecting utility-level intervals in decreasing order and searching only where projects are affordable reproduces the full descending execution's choices.Within each interval, the contributing voters stay fixed and affordability at a level implies affordability at smaller levels.Source: A Polynomial-Time Implementation · p. 14
• The implementation runs in polynomial time, with at most m purchases and one final search, and uses arithmetic numbers of polynomial bit length.Searches consider at most n+1 intervals; the bit lengths remain polynomial after utility scaling and payment updates.Source: A Polynomial-Time Implementation · p. 14

• The unit-cost construction runs with project price q = n/(k + 1), yielding relevant integer levels 1 through k and the Droop quota.Source: B Proof of the Theorem 6.1 · p. 15
• Every size-k completion of the selected set satisfies Droop-FJR1+, and the axiom specializes to Droop-FJR+ for approval utilities.The proof applies the fractional representation argument to the selected set before considering its completion.Source: B Proof of the Theorem 6.1 · p. 15
• Fractional Droop violations can be checked by solving at most one linear program per level and testing whether its optimum is below one.The verification examines levels h and minimizes the weighted project cost subject to the fractional constraints.Source: B Proof of the Theorem 6.1 · p. 15
• Under the sequential-Phragmén completion, every unselected project's remaining-budget condition holds, including when the maximum load is created during completion.When M = (k + 1)/n, total residual budget is one; otherwise, threshold monotonicity bounds the load increase for each remaining project.Source: B Proof of the Theorem 6.1 · p. 16
• A sequential-Phragmén completion is priceable at budget B′ = nM while preserving the selected set and its representation guarantee.The completion assumes at least k positively valued projects and assigns loads until k projects are selected.Source: B Proof of the Theorem 6.1 · pp. 15–16
• For approval utilities, the argument also excludes strict-inclusion deviations by groups larger than n|T|/(k + 1).Source: B Proof of the Theorem 6.1 · p. 16

C.3

• EJR and priceability do not ensure FJR1: all three voters can afford {a, b, c} and each values that set at two, yet adding one proposed project does not take a member strictly above the target.The outcome {d1, d2, d3} is EJR and priceable, but fails FJR1.Source: C Examples Clarifying the Guarantees · p. 16

Example C.2 (Why condition (2f) is needed)

• Dropping the one-project restriction can make the fractional property infeasible even when an outcome satisfies exact FJR.For the example, every feasible outcome violates the resulting property, while {b, c} satisfies exact FJR; condition (2f) excludes the displayed assignments.Source: C Examples Clarifying the Guarantees · p. 17

Example C.1 (EJR and priceability do not imply FJR1)

• An outcome can satisfy exact FJR yet violate FJR1+, showing that the fractional verification requirement is stronger than FJR1.In the example, the outcome {d1, d2, d3} satisfies FJR, but a fractional assignment has voter weight 3/2 exceeding normalized cost 4/3.Source: C Examples Clarifying the Guarantees · p. 17

Example C.4 (Priceable Hare-FJR+ need not be Droop-FJR+)

• A priceable outcome satisfying Hare-FJR+ can still violate Droop-FJR+, so the simultaneous Droop guarantee and priceability is strictly stronger.The example's level-two assignment has voter weight 3/2, above the Droop price 4/3, while no Hare violation occurs.Source: C Examples Clarifying the Guarantees · pp. 17–18