The Core of the Participatory Budgeting Problem
The Core of the Participatory Budgeting Problem
复制标题
参与式预算问题的核心
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kamesh Munagala
中科院分区：
文献类型：
--
作者：
Brandon Fain;Ashish Goel;Kamesh Munagala
在参与式预算中，社区共同决定为当地公共项目分配公共税金。在这项工作中，我们考虑了确定资金分配项目的相当汇总偏好的问题。我们认为，经典的游戏理论观念核心在环境中捕捉了公平。为了计算核心，我们首先开发出一种称为lindahl平衡的公共物品市场平衡的新颖表征。然后，我们提供了第一种多项式时间算法，用于计算这种平衡以用于广泛的实用程序函数。我们从经验上表明，可以有效地计算出核心功能，这些功能自然地对实际参与预算实例进行了模拟数据，并检查核心与福利目标的关系。最后，我们通过开发一种基于差异隐私的指数机制建立的随机近似策略的真实机制来解决激励措施和机制设计的关注。
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.