Democratic Fair Allocation of Indivisible Goods
Democratic Fair Allocation of Indivisible Goods
复制标题
不可分割物品的民主公平分配
DOI：
10.1016/j.artint.2019.103167
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Warut Suksompong
中科院分区：
文献类型：
--
作者：
Erel Segal;Warut Suksompong
研究了不可分割商品公平分配的问题。同一群体中的代理人共享同一套商品，尽管他们可能有不同的偏好。以前的工作集中在一致公平上，即每组中的所有代理都必须同意他们组的份额是公平的。在这种严格的要求下，公平分配只存在于小团体。我们引入了民主公平的概念，其目的是满足每个群体中一定比例的代理。这个概念更适合城市或国家这样的大群体。我们提出了在两个或多个任意大的具有单调、加性或二元估值的代理群体之间民主公平分配的协议。对于具有任意单调值的两组，我们给出了保证每组中至少1/2的代理的嫉妒自由度达到1 good的有效协议，并证明了1/2分数是最优的。我们还提出了其他协议，这些协议对每组中更多的代理或更多的组做出较弱的公平保证。我们的协议结合了不同领域的技术，包括组合博弈论、切蛋糕和投票。
We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused onunanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept ofdemocratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least 1/2 of the agents in each group, and prove that the 1/2 fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
DOI：
10.1145/2764468.2764490
发表时间：
2015-06
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
通讯作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah