Hybrid Participatory Budgeting: Divisible, Indivisible, and Beyond

Participatory budgeting (PB) has been receiving significant attention lately both in theory and practice. PB is broadly classified into two categories: divisible PB and indivisible PB. Divisible PB imposes no constraint on the amount allocated to each project, whereas the indivisible PB assumes that each project is associated with a cost and the project must either be funded in full or not funded. In this work, we propose a rich PB model that encompasses many settings of PB as special cases. Some of such settings include the case where some projects are divisible and some are indivisible and the case where the cost of each project may belong to a continuum range of values. We propose various welfare and fairness objectives and verify the computational complexity of each of them. We prove experimentally that even the computationally hard objectives become tractable in practice. Also, we propose greedy approximation algorithms for such objectives and prove that our algorithms achieve nearly optimal solutions on real world PB datasets.