A Framework for Participatory Budgeting with Resource Pooling

1 Introduction

The form of direct democracy known as participatory budgeting (PB) was first implemented by the Workers' Party in Porto Alegre, Brazil [Cabannes, 2004], and has since spread globally. In a PB process, citizens vote how to collectively spend some pre-determined budget. There has been much computational research on PB in the recent past [Aziz and Shah, 2021], focusing on incentives [Goel et al., 2019], proportionality [Aziz et al., 2017], and stability [Fain et al., 2016], amongst other desiderata.

All PB implementations we are aware of rely upon a central authority to determine and provide a budget to fund projects. In practice, this requirement excludes some groups from initiating a PB process. For example, neighbouring municipalities may wish to collaborate on funding projects which can benefit residents from multiple communities simultaneously. On a smaller scale, a group of flatmates may need to decide which furnishings and appliances to buy. In each of these cases, while PB seems a natural process of arriving at a mutually beneficial outcome, existing PB models are insufficient because they focus on project selection and not efficient resource pooling. The goal of our research is to define a framework which captures both of these components simultaneously, and using this framework, to devise mechanisms which circumvent the institutional requirements of traditional PB.

2 Contributions

In this section, we will briefly introduce our framework, point out its unique ingredients, and identify some key criteria we would like a solution to satisfy. We will then describe our results related to those criteria and give a few future directions we plan to explore within this framework.

2.1 PB with Resource Pooling

We consider a flexible and general framework which we term PB with Resource Pooling. In our framework, agents can have their own individual budgets, and there need not be any central budget. As mentioned, it is typical in the PB literature to assume that agents' utilities depend only on their valuations for the set of projects selected and that agents are indifferent toward the amount of the budget used. While this is appropriate in that setting because the agents do not necessarily believe leftover budget will benefit them, this is not the case with individual budgets since agents can use their leftover funds directly. For this reason, we model agents with utilities dependent upon the amount they pay to the mechanism (i.e. quasi-linear utilities).

While there are several frameworks for funding indivisible projects where agents bring their own funds [Brandl et al., 2021; Hershkowitz et al., 2021], ours is the only to employ the quasi-linear utility assumption. We also point out that our framework captures the classical indivisible PB model.

Our paper [Aziz et al., 2022], which is currently under submission, devises mechanisms within this framework with a particular focus on outcomes which are efficient while ensuring each agent is incentivized to participate in the process. Towards this, we study the possibility of achieving optimal utilitarian welfare alongside a very basic participation notion, namely weak participation (WP), that guarantees positive utility to all agents involved. Our motivation for requiring a participation incentive is simple - a mechanism in which agents may regret participating is unlikely to be adopted.

2.2 AGeneral Inapproximability

In our paper, we look for algorithms which approximate the welfare optimal outcome subject to WP. However, we find that there is in fact no polynomially bounded approximation algorithm for welfare maximization subject to WP, under the assumption that P ̸= NP. Indeed, this strong inapproximability holds even if we restrict ourselves to the setting with only two agents with additive valuations (i.e. valuations of a project bundle are equal to the sum of the valuations of the projects that make it up). The inapproximability also holds if we consider the setting with additive valuations and unit costs (i.e. each project has the same cost). This inapproximability is striking: the problem of welfare maximization admits a fully-polynomial approximation scheme (FPTAS), 1 but after imposing the seemingly weak requirement of WP, the same problem does not admit any polynomial approximation guarantees. Furthermore, though our paper's focus is on utilitarian welfare, we also show that this inapproximability holds for other commonly studied social welfare functions, namely Nash welfare and egalitarian welfare.

2.3 Restricted Settings

Given the strong inapproximability of welfare maximization subject to WP in various settings with additive valuations, it is natural to explore setting restrictions which bypass this inapproximability and admit bounded approximation algorithms. In our work, we have investigated two such restrictions.

The first restricted setting we consider is that in which each agent derives non-zero value from a project bundle if and only if the bundle contains the set of projects desired by that agent, which we refer to as the agent's demand set. We refer to this as the setting with single-minded valuations, following the precedent of single-minded bidders in the combinatorial auctions literature [Chen et al., 2004]. In contrast to the additive setting, the single-minded setting captures project complementarities in agent valuations. We show that welfare maximization subject to WP admits an FPTAS when the demand sets constitute a laminar set family.

We also study the setting with symmetric valuations, where agent valuations depend only on the number of projects selected. In this setting, we give an exact algorithm for welfare maximization subject to WP which runs in polynomial time. The computational complexity of welfare maximization subject to WP remains open for general single-minded valuations, a problem which we plan to further explore. An interesting research direction is to identify other tractable instances, or more broadly, to identify the sufficient conditions for our inapproximability to be bypassed.

3 Conclusion and FutureWork

In this paper, we motivated and introduced a general PB framework which captures resource pooling. We focused on welfare maximization subject to a minimal participation axiom that agents would expect the mechanism to satisfy. We noted inapproximability results with respect to this objective and identified two natural classes of instances which admit a tractable, exact algorithm or an FPTAS.

Because the proof of our inapproximability result proceeds by constructing a pathological instance with a single agent with very high valuations, a natural next step is to study restricted instances in which agents' valuations are normalized. Another direction we plan to explore is whether randomization can help us devise viable mechanisms within our framework. Analogies can be drawn between randomized PB and the divisible PB setting, in which a stability property called core - which is much stronger than WP and may not exist in the indivisible setting - has been proven to exist [Fain et al., 2016]. While this may serve as an encouraging sign, randomization differs from the divisible setting in that a randomized outcome may not fractionally fund a project ex-post. Though an approach of randomizing over indivisible outcomes has been taken with respect to multi-winner voting [Cheng et al., 2020], no research has applied this approach to PB, and we consider this a promising direction.

1 An algorithm which approximates the optimal solution by a factor of at least 1 - ϵ in time polynomial in the instance size and 1/ϵ for any ϵ > 0.

Furthermore, future work could investigate outcomes which are welfare optimal subject to other notions of fairness, for instance individual rationality (IR) which guarantees that every agent receive at least as much utility as they could get on their own. The first step after formulating a new objective would be to check whether our inapproximability result still holds. We hope our framework provides a useful starting point for further exploration of PB with resource pooling.