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