Participatory Budgeting with Multiple Degrees of Projects and Ranged Approval Votes

Gogulapati SreedurgaIJCAI 2023 · DOI

TL;DR

This paper tackles the challenge of participatory budgeting (PB) where public projects can be funded at various levels of sophistication, not just as all-or-nothing choices. They introduce a new voting mechanism called "ranged approval votes" and analyze its computational complexity and axiomatic properties, extending existing PB research to this more realistic scenario.

What Problem Does This Paper Address?

Traditional participatory budgeting (PB) often assumes that each project has a single, fixed cost. However, in reality, projects can often be implemented at different levels of quality or sophistication, each corresponding to a different cost. For example, a park could be a simple green space or a fully equipped recreational facility. This paper addresses the gap in PB research by introducing a framework where projects can have multiple permissible costs, representing these different degrees of sophistication. Voters can express their preferences over these cost ranges, and the system must then select a subset of projects and assign a specific cost to each, all within a limited budget. This more nuanced approach to project funding and voter preference elicitation is crucial for more effective and democratic resource allocation.

Methods

The core of this paper lies in extending existing participatory budgeting models to handle projects with multiple cost options. They introduce ranged approval votes, where voters specify a lower and upper bound for the cost they deem appropriate for each project. This is a generalization of standard approval voting.

The authors then define four different utility functions to capture how voters' satisfaction translates into numerical values based on the assigned project costs and their reported ranges. These utility functions are then used to define corresponding utilitarian PB rules, which aim to maximize the total utility across all voters.

A significant portion of the paper is dedicated to analyzing the computational complexity of these new PB rules. They leverage dynamic programming to develop algorithms for finding optimal project selections and costs. Furthermore, they explore fixed-parameter tractability (FPT), investigating how the problem's complexity changes with specific parameters like the "scalable limit" (GCD of costs and budget) and the number of projects.

Finally, they introduce and analyze several budgeting axioms (e.g., shrink-resistant, range-abiding, degree-efficient) to evaluate the desirable properties of their proposed PB rules. This axiomatic analysis helps understand the fairness and robustness of different decision-making mechanisms.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Ranged Approval Votes are More Expressive: Allowing voters to specify cost ranges (lower and upper bounds) for projects provides a richer and more realistic way to capture their preferences compared to simple approval or all-or-nothing choices.
  • Extending Existing PB Frameworks is Feasible: The paper demonstrates that many positive computational and axiomatic results from simpler PB models can be successfully extended to this more complex setting with multiple project degrees.
  • New Utility Notions are Necessary: The authors introduce novel utility functions that are specifically designed for the multi-degree project setting, going beyond simple extensions of existing models.
  • Computational Complexity is Manageable (with caveats): While some rules are NP-hard, the paper shows that polynomial-time algorithms exist for certain utility functions (like cardinal utility), and parameterized algorithms offer efficient solutions for specific problem structures.
  • Axiomatic Analysis Reveals Trade-offs: No single rule satisfies all desirable axioms. The axiomatic analysis highlights the strengths and weaknesses of each rule, guiding the choice of mechanism based on specific democratic goals. For instance, the proposed R|| || rule (minimizing disutility) shows promise for its good axiomatic properties.

Key Results

  • Polynomial-time algorithms are developed for the R|s| rule (maximizing the number of projects within voter-approved cost ranges), even with multiple project degrees.
  • NP-hardness is established for the Rc(s) rule (maximizing the sum of costs within voter-approved ranges), but pseudo-polynomial time algorithms and FPTAS (Fully Polynomial-Time Approximation Schemes) are provided.
  • Fixed-parameter tractability results are shown for Rc(s) and R|| || with respect to parameters like the scalable limit and the number of projects.
  • The paper introduces and analyzes four new budgeting axioms, and demonstrates that different PB rules satisfy varying subsets of these axioms. For example, R|s| and R|| || are shown to be range-abiding, while Rc(s) and R(s) are not.

Limitations and Future Work

  • Generalization of Utility Functions: While the paper presents results for specific utility functions, it notes that computational results can be generalized to more complex utility functions with minor tweaks. However, a deeper exploration of these generalizations might be beneficial.
  • Practical Implementation: The paper focuses on theoretical analysis. Future work could involve empirical studies or simulations to test these models with real-world data and voter behavior.
  • Other Axioms: The authors introduce several axioms but acknowledge that other relevant axioms might exist for this setting. Further axiomatic investigations could lead to a more comprehensive understanding of PB rule properties.
  • Interactions between Projects: The current model assumes project costs are independent. Future research could explore scenarios where projects have interdependencies, which would add another layer of complexity.

Summary updated

BibTeX
@inproceedings{sreedurga2023participatory,
  author = {Gogulapati Sreedurga},
  title = {{Participatory Budgeting with Multiple Degrees of Projects and Ranged Approval Votes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/320},
}
Figure