The core of the participatory budgeting problem
Conference Paper
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 dominantstrategy truthful mechanism building on the Exponential Mechanism from differential privacy.
Full Text
Duke Authors
Cited Authors
- Fain, B; Goel, A; Munagala, K
Published Date
- January 1, 2016
Published In
Volume / Issue
- 10123 LNCS /
Start / End Page
- 384 - 399
Electronic International Standard Serial Number (EISSN)
- 1611-3349
International Standard Serial Number (ISSN)
- 0302-9743
International Standard Book Number 13 (ISBN-13)
- 9783662541098
Digital Object Identifier (DOI)
- 10.1007/978-3-662-54110-4_27
Citation Source
- Scopus