Best-of-Both-Worlds Fair-Share Allocations
Best-of-Both-Worlds Fair-Share Allocations
复制标题
两全其美的公平份额分配
DOI：
10.1007/978-3-031-22832-2_14
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
Moshe Babaioff;Tomer Ezra;U. Feige
本文研究了具有附加价值的$n$代理之间不可分割物品的公平分配问题，当代理对物品具有相等的权利且不存在转移时。两全其美（best -of- worlds, BoBW）公平机制旨在为所有代理提供事前保证（例如获得预期中的比例份额）和事后保证。先前的BoBW结果集中在基于“最多一项”范式的事后保证上，例如不嫉妒最多一项（EF1）。在这项工作中，我们试图给每个代理一个高价值的事后，特别是，他的最大份额（MMS）的恒定部分。最多一项的范式不能提供这样的保证，并且不难提出一些例子，在这些例子中，以前的BoBW机制只给代理提供其MMS的$\frac{1}{n}$的一小部分。我们的主要结果是一个确定性多项式时间算法，该算法计算分配的分布是事前比例的，事后，每个分配至少给每个代理一个项目的比例份额，更重要的是，至少一半的MMS。此外，最后一种事后担保甚至适用于本文中引入的更苛刻的股份概念，我们称之为截断比例股份（TPS）。我们的保证几乎是最好的，从某种意义上说，一个人不能保证代理事前超过其比例份额，一个人不能保证代理事后超过其TPS的$\frac{n}{2n-1}$的一小部分。
We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness mechanisms aim to give all agents both an ex-ante guarantee (such as getting the proportional share in expectation) and an ex-post guarantee. Prior BoBW results have focused on ex-post guarantees that are based on the"up to one item"paradigm, such as envy-free up to one item (EF1). In this work we attempt to give every agent a high value ex-post, and specifically, a constant fraction of his maximin share (MMS). The up to one item paradigm fails to give such a guarantee, and it is not difficult to present examples in which previous BoBW mechanisms give agents only a $\frac{1}{n}$ fraction of their MMS. Our main result is a deterministic polynomial time algorithm that computes a distribution over allocations that is ex-ante proportional, and ex-post, every allocation gives every agent at least his proportional share up to one item, and more importantly, at least half of his MMS. Moreover, this last ex-post guarantee holds even with respect to a more demanding notion of a share, introduced in this paper, that we refer to as the truncated proportional share (TPS). Our guarantees are nearly best possible, in the sense that one cannot guarantee agents more than their proportional share ex-ante, and one cannot guarantee agents more than a $\frac{n}{2n-1}$ fraction of their TPS ex-post.
DOI：
10.1145/3391403.3399526
发表时间：
2019-02
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Garg;Setareh Taki
通讯作者：
J. Garg;Setareh Taki
二元估值的公平除法：一条规则来统治它们
DOI：
--
发表时间：
2020
期刊：
WINE
影响因子：
--
作者：
Halpern, Daniel;Shah, Nisarg;Psomas, Alexandros;Procaccia, Ariel D.
通讯作者：
Procaccia, Ariel D.
无偿真实分配机制：特征及其对公平性的影响
DOI：
10.48550/arxiv.1705.10706
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G