Participatory Budgeting with Project Groups: Complexity and Algorithms

This study enhances the traditional approval-based framework of participatory budgeting (PB) by incorporating project groups, each assigned a specific budget cap, alongside an overarching budget. The researchers examine the computational challenges involved in choosing project combinations that optimize voter satisfaction while adhering to all budgetary limitations. They demonstrate that the problem is typically intractable but offer efficient exact algorithms for particular scenarios, including those with limited groups or hierarchical structures, along with approximation algorithms. The goal of this research is to foster more inclusive PB processes that cater to diverse themes and regions within municipalities.