This study explores a generalization of the standard approval-based model of participatory budgeting (PB). Voters provide approval ballots over a set of predefined projects, and in addition to a global budget limit, the projects are grouped with individual budget constraints. We investigate the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. The problem is generally intractable; however, we present efficient exact algorithms for special cases, including instances with few groups and those with a nearly hierarchical group structure, alongside efficient approximation algorithms. These findings could enable municipalities to conduct richer PB processes that are thematically and geographically inclusive.
Blogger's Review: This paper offers a fresh perspective on the complexity of participatory budgeting, particularly under multiple group budget constraints, showcasing the interplay between theory and practical application. The introduction of efficient algorithms promises more effective and equitable budgetary decisions in the future.