TL;DR
This paper introduces "Participatory Budgeting with Resource Pooling" (PBRP), a novel framework that extends traditional participatory budgeting by allowing participants to pool their own resources, not just select projects from a pre-defined budget. This addresses limitations in existing PB models, enabling collaborative funding for projects that benefit multiple communities or groups.
What Problem Does This Paper Address?
Traditional Participatory Budgeting (PB) is a democratic process where citizens collectively decide how to spend a pre-determined public budget. While effective for local government initiatives, it falls short when groups with their own resources want to collaborate on projects. Imagine neighboring towns wanting to fund a shared park, or a group of flatmates deciding on shared appliances – these scenarios require pooling individual funds, something current PB models don't handle. This paper tackles this gap by proposing a framework that accommodates individual resource contributions and project selection simultaneously, moving beyond the constraint of a single, central budget.
Methods
The core of this paper is the introduction of the "PB with Resource Pooling" (PBRP) framework. Unlike traditional PB where agents are indifferent to the budget used (as it's not their own), PBRP models agents with quasi-linear utilities. This means their satisfaction depends on both the projects they get and the amount they contribute. The authors then explore mechanisms within this framework, focusing on achieving efficient outcomes while ensuring agents are incentivized to participate. They introduce a "weak participation" (WP) notion, guaranteeing agents a non-negative utility, and investigate how to achieve optimal utilitarian welfare under this constraint.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Beyond Central Budgets: The most significant insight is the realization that PB can be extended beyond centrally funded projects to scenarios where individuals or groups pool their own resources. This opens up PB to a much wider range of collaborative decision-making.
- Quasi-Linear Utilities are Key: Modeling agents with quasi-linear utilities is crucial for PBRP. This captures the reality that individuals contributing their own money will care about how much they spend, not just the projects selected.
- The Trade-off Between Efficiency and Participation: The paper highlights a fundamental tension: achieving maximum social welfare (utilitarian outcome) is significantly harder when agents must be guaranteed a positive utility (weak participation).
- Strong Inapproximability Results: Even with simple settings (two agents, additive valuations, unit costs), achieving optimal welfare under weak participation is proven to be computationally very difficult, even for approximate solutions. This suggests that practical mechanisms will likely involve trade-offs.
- Restricted Settings Offer Tractability: The paper identifies specific scenarios (single-minded valuations with laminar demand sets, or symmetric valuations) where efficient welfare maximization under weak participation becomes computationally feasible, offering pathways to practical solutions.
Key Results
The paper establishes a strong theoretical result: under the assumption that P ≠ NP, there is no polynomial-time approximation algorithm for welfare maximization subject to weak participation, even in very restricted settings. This inapproximability holds for utilitarian, Nash, and egalitarian welfare. However, for specific restricted settings, they demonstrate that either an exact algorithm or a Fully-Polynomial Time Approximation Scheme (FPTAS) can be achieved.
Limitations and Future Work
The authors acknowledge that their inapproximability result stems from pathological instances with agents having extremely high valuations. A natural next step is to study settings where agent valuations are normalized. They also propose exploring randomization as a technique to devise viable mechanisms, drawing parallels with randomized approaches in other areas of computational social choice. Future work will also investigate other notions of fairness, such as individual rationality (IR), and check if the inapproximability results still hold under these alternative criteria.
Summary updated