The Core of the Participatory Budgeting Problem

By Brandon Fain, Ashish Goel, Kamesh Munagala. 2016

128 citations recorded by the source corpus.

In participatory budgeting, communities collectively decide on the allocation of public tax dollars for local public projects. In this work, we consider the question of fairly aggregating preferences to determine an allocation of funds to projects. We argue that the classic game theoretic notion of core captures fairness in the setting. To compute the core, we first develop a novel characterization of a public goods market equilibrium called the Lindahl equilibrium. We then provide the first polynomial time algorithm for computing such an equilibrium for a broad set of utility functions. We empirically show that the core can be efficiently computed for utility functions that naturally model data from real participatory budgeting instances, and examine the relation of the core with the welfare objective. Finally, we address concerns of incentives and mechanism design by developing a randomized approximately dominant-strategy truthful mechanism building on the Exponential Mechanism from differential privacy.

Subfields: Economics and Econometrics, Management Science and Operations Research, Safety Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

1. Nisarg Shah
2. Kamesh Munagala
3. Brandon Fain
4. Vincent Conitzer

In Management Science and Operations Research

1. Nisarg Shah
2. Kamesh Munagala
3. Brandon Fain
4. Vincent Conitzer

In Safety Research

1. Nisarg Shah
2. Kamesh Munagala
3. Brandon Fain
4. Vincent Conitzer

Citations in the corpus

• Proportionally Fair Clustering (2019, background): “The core has been adapted as a natural generalization to groups of the idea of fairness as proportionality (Fain et al., 2016; 2018), similar to other group fairness concepts for public goods that explicitly consider shared resources (Conitzer et al.”
• Fair Allocation of Indivisible Public Goods (2018, methodology): “We define the notion of core outcomes, which has been well studied (in similar forms) as a notion of stability in economics [13, 25, 33] and computer science [10, 22] in the context of randomized or fractional allocations.”
• Fair Public Decision Making (2016, background): “Recently, researchers in computational social choice have addressed this problem from an axiomatic viewpoint [20], including fairness considerations [17], and from the viewpoint of implicit utilitarian voting [5].”