Fair Allocation of Indivisible Public Goods
Fair Allocation of Indivisible Public Goods
复制标题
不可分割公共物品的公平分配
DOI：
10.1145/3219166.3219174
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shah, N.
中科院分区：
文献类型：
--
作者：
Fain, B;Munagala, K;Shah, N.
我们考虑公平分配不可分割的公共产品的问题。我们将公共产品建模为元素，对可以选择的元素子集进行可行性约束，并假设代理人在元素之间具有相加效用。我们的模型概括了现有的框架，如公平的公共决策和参与式预算。我们研究了一个分组公平的概念称为核心，它概括了研究充分的比例和帕累托效率的概念，并要求代理的每个子集必须收到一个结果，是公平的相对于其大小。与可分割的公共产品（允许部分分配）的情况相反，在分配不可分割的公共产品时，不能保证核心存在。我们的主要贡献是一个添加剂近似的核心（一个微小的乘法损失）的概念，和多项式时间算法，实现一个小的添加剂近似，其中的添加剂因子是相对于一个元素的代理的最大效用。如果可行性约束定义了一个拟阵，我们证明了一个加法近似为2。当可行性约束定义匹配时，类似的方法产生恒定的加性边界。对于可行性约束定义一个任意包装多面体与温和的限制，我们展示了一个添加剂的保证，是对数的宽度的多面体。我们的算法基于最大化纳什社会福利的凸规划，但在使用方式上与以前的工作有显着不同。据我们所知，我们的工作是第一个在不可分割的环境中接近核心的工作。
We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. For feasibility constraints defining an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. As far as we are aware, our work is the first to approximate the core in indivisible settings.
登录
查看更多内容
Eisenberg-Gale 市场：算法和结构特性
DOI：
--
发表时间：
2007
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
K. Jain;V. Vazirani
通讯作者：
V. Vazirani
公平理论中的两个问题
DOI：
--
发表时间：
1976
期刊：
影响因子：
--
作者：
H. Varian
通讯作者：
H. Varian
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
J. Schummer
通讯作者：
J. Schummer
公正的税收——一个积极的解决方案
DOI：
--
发表时间：
1958
期刊：
影响因子：
--
作者：
E. Lindahl
通讯作者：
E. Lindahl
DOI：
--
发表时间：
2016
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
Brandon Fain;Ashish Goel;Kamesh Munagala
通讯作者：
Kamesh Munagala