PaperlayerView exact revision on arXiv

Source-linked AI summary

Proportional Participatory Budgeting with Additive Utilities

Dominik Peters, Grzegorz Pierczyński, Piotr Skowron

arXiv:2008.13276v2cs.GTecon.TH

TL;DR

The paper asks how participatory budgeting can represent cohesive groups proportionally when projects have arbitrary costs and voters have additive valuations. It formalizes EJR, develops the Method of Equal Shares, and examines stronger proportionality requirements. Equal Shares satisfies EJR for approval utilities, satisfies EJR up to one project for additive valuations, and outperforms separate district elections on reported utility distributions; FJR is satisfiable only through a more expensive, less natural rule.

  • Problem

    Participatory budgeting lacks a convincing city-wide proportional voting rule for arbitrary project costs and diverse voter interests.

  • Method

    The paper formulates EJR and FJR and develops the Method of Equal Shares, including an adaptation for general additive valuations and ordinal ballots.

  • Results

    Equal Shares satisfies EJR for approval-based PB, satisfies EJR up to one project for additive valuations, and globally produces more equal voter utility than separate district elections.

  • Takeaways & Limitations

    Global rules such as Equal Shares provide a proportional PB alternative to separate district elections, while FJR remains achievable through a less natural and more expensive rule.

  • Takeaways & Limitations

    The paper notes that GCR is custom-engineered for FJR and may be deficient in other dimensions, with examples where Equal Shares selects better outcomes.

Abstract

from arXiv · show

We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate an axiom (Extended Justified Representation, EJR) that guarantees proportional representation to groups of voters with common interests. We propose a simple and attractive voting rule called the Method of Equal Shares that satisfies this axiom for arbitrary costs and approval utilities, and that satisfies the axiom up to one project for arbitrary additive valuations. This method can be computed in polynomial time. In contrast, we show that the standard method for achieving proportionality in committee elections, Proportional Approval Voting (PAV), cannot be extended to work with arbitrary costs. Finally, we introduce a strengthened axiom (Full Justified Representation, FJR) and show that it is also satisfiable, though by a computationally more expensive and less natural voting rule.

1 Introduction

The paper identifies proportionality failures in participatory budgeting and introduces EJR together with the Method of Equal Shares to address them across costs and valuation models.

  • The problem: Plurality-based PB can let the largest minority consume the entire budget, leaving other cohesive districts unrepresented.In Circleville, Northside projects receive all funding while 280k residents elsewhere receive none.
  • The problem: Separate district elections avoid concentrated spending but mishandle boundary projects and prevent city-wide proportional allocation.Projects involving multiple districts must be assigned to one district, excluding supportive residents elsewhere.
  • The proposed framework: EJR formalizes proportionality by requiring that groups of voters with common interests are not underserved.The paper presents EJR as a missing formalization for proportional representation in PB.
  • Limits of PAV: PAV fails proportionality beyond unit costs because identical preferences and feasibility can require different proportional outcomes when project costs differ.The Onetown and Twotown construction forces preference-and-feasibility-based rules to select the same outcome despite differing costs.
  • The proposed framework: The Method of Equal Shares satisfies EJR for approval-based PB and satisfies it up to one project for general additive valuations.For additive valuations, payments are proportional to voters’ utilities, and the up-to-one guarantee is computationally tractable.
  • FJR: FJR strengthens EJR by relaxing unanimity to popularity within a group, and a greedy rule satisfies it for arbitrary costs but is computationally expensive and less natural.Both PAV and Equal Shares fail FJR, while the proposed greedy procedure is not polynomial-time.

2 Preliminaries

The general PB model selects a feasible set of projects from voters’ utilities, allowing arbitrary project costs and additive valuations, with approval-based committees as a special case.

  • An election consists of voters, projects, a budget, project costs, and additive voter utility functions.
  • Project-set cost and voter utility are additive across selected projects, with every project receiving positive utility from at least one voter.
  • A feasible outcome is a project subset whose total cost does not exceed the budget, and an aggregation rule selects one such outcome.
  • Special cases: Committee elections arise when the budget is an integer and every candidate costs one, so feasible outcomes contain at most the committee size.
  • Special cases: With approval utilities, each voter assigns utility 0 or 1 to each project and approves the projects assigned utility 1.
  • Special cases: Approval-based committee elections combine the unit-cost and approval-utility special cases.

3 The Method of Equal Shares

The Method of Equal Shares divides the budget equally among voters, funds affordable projects sequentially, and charges supporters according to utility. It provides strong proportionality guarantees, while revealing computational and design trade-offs around EJR, core approximation, priceability, and exhaustiveness.

  • Equal Shares gives every voter b/n initially, then sequentially selects affordable candidates and charges voters according to their utility for each funded project.The rule stops when no candidate is affordable; the cost per utility unit is ρ, and ρ increases throughout execution.
  • The first selected project is affordable to its supporters and, among such projects, maximizes approvers divided by cost.This follows from selecting the project with minimum ρ in the approval-utility case.
  • 3.1 Extended Justified Representation (EJR): Equal Shares satisfies EJR for approval-based participatory budgeting, but general participatory budgeting makes exact EJR computationally difficult.No strongly polynomial-time aggregation rule can satisfy EJR unless P = NP, and Equal Shares therefore fails exact EJR in the general model.
  • 3.1 Extended Justified Representation (EJR): For arbitrary additive valuations, Equal Shares satisfies EJR up to one project, with the extra project required to belong to the justified project set.The result applies in the general participatory-budgeting model and is presented as a strong proportionality guarantee under arbitrary costs and additive utilities.
  • 3.2 Approximating the Core: Equal Shares yields an α-core guarantee with α = 4 log(2 · umax/umin), and this bound is asymptotically tight.The paper also notes that the core can be empty for some elections, even with unit costs, so the guarantee is an approximation rather than full core membership.
  • 3.4 Exhaustiveness: Equal Shares is priceable and exhaustive when every voter assigns positive utility to every project, but exhaustiveness is generally incompatible with priceability.Whether non-exhaustiveness is desirable depends on whether unspent budget can be reused; varying the budget can preserve priceability while completing the outcome.

4 Greedy Cohesive Rule

The Greedy Cohesive Rule strengthens EJR to cover partially cohesive groups and satisfies the resulting FJR axiom. It is computationally more expensive and less natural than Equal Shares, with additional limitations concerning priceability, exhaustiveness, and laminar proportionality.

  • 4.1 Full Justified Representation (FJR): FJR strengthens EJR by guaranteeing representation to groups that are only partially cohesive.
  • 4.1 Full Justified Representation (FJR): FJR requires at least one voter in every weakly cohesive group S to receive utility at least β.
  • 4.1 Full Justified Representation (FJR): FJR implies EJR in the general participatory-budgeting model.
  • 4.1 Full Justified Representation (FJR): The Greedy Cohesive Rule satisfies FJR, although it is computationally expensive and somewhat artificial.
  • 4.1 Full Justified Representation (FJR): GCR satisfies FJR for all monotone utilities, whereas EJR relies on additive utilities.
  • 4.2 Priceability and Exhaustiveness of GCR: GCR outcomes can be completed to priceable and exhaustive outcomes, but GCR itself satisfies neither property.
  • 4.3 Some Drawbacks of the Greedy Cohesive Rule: GCR can return committees that violate laminar proportionality, although whether it can always satisfy that axiom remains open.

5 Equal Shares and GCR for Ordinal Ballots

For ordinal ballots, Equal Shares converts rankings into additive valuations and can use lexicographic utilities to satisfy PSC. GCR can be adapted similarly, but it may fail PSC, and PSC is logically incomparable with EJR and FJR.

  • 5 Equal Shares and GCR for Ordinal Ballots: Ordinal rankings are converted into additive valuations using positional scoring rules before applying Equal Shares or GCR.
  • 5.2 Equal Shares and PSC: PSC requires a sufficiently large group of voters sharing top-ranked candidates to receive at least min(ℓ, |T|) selected candidates from that set.
  • 5 Equal Shares and GCR for Ordinal Ballots: Lexicographic utilities treat higher-ranked candidates as infinitely more valuable than lower-ranked candidates in the Equal Shares analysis.
  • 5 Equal Shares and GCR for Ordinal Ballots: The Method of Equal Shares for lexicographic utilities satisfies Proportionality for Solid Coalitions.
  • 5.2 Equal Shares and PSC: PSC is logically incomparable with both EJR and FJR: neither axiom implies PSC, and PSC implies neither of them.
  • 5.3 GCR for Lexicographic Utilities: With lexicographic utilities, GCR can select c1, c6, c7, and c8 even though PSC requires two candidates from c1, c2, and c3.

6 Conclusion

The paper formulates EJR and FJR for participatory budgeting and develops Equal Shares as a simple, natural, polynomial-time rule satisfying key proportionality guarantees. FJR is satisfiable through a less natural rule, while experiments report an advantage for global rules such as Equal Shares over separate district elections.

  • 6 Conclusion: The paper formulates EJR and FJR as proportionality axioms for participatory budgeting.
  • 6 Conclusion: Equal Shares is a simple and natural polynomial-time rule that satisfies EJR and other proportionality-related properties.
  • 6 Conclusion: FJR is satisfiable by a different voting rule that is arguably less natural.
  • 6 Conclusion: Experiments show a visible advantage for global rules such as Equal Shares over separate district elections.
Loading 2008.13276v2…