Fairness-Efficiency Tradeoffs in Dynamic Fair Division
Fairness-Efficiency Tradeoffs in Dynamic Fair Division
复制标题
动态公平划分中的公平与效率权衡
DOI：
10.1145/3391403.3399467
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alexandros Psomas
中科院分区：
文献类型：
--
作者：
David Zeng;Alexandros Psomas
一组T件不可分割的商品必须以公平有效的方式分配给n个具有附加效用的代理人。标准的公平概念是嫉妒自由，它要求每个代理更喜欢自己的分配，而不是其他代理的分配。尽管在这种情况下嫉妒显然是不可避免的——考虑一个不可分割的商品和两个代理人的情况——提供几乎没有嫉妒的解决方案是可能的[3,6]。具体来说，如果对于每一对代理i和j， i对j的任何嫉妒都可以通过从j的捆绑包中移除最多一件商品来消除，那么分配是无嫉妒的（EF1）。最近，Caragiannis et al.[3]表明，使代理人效用乘积最大化的分配（根据具有正效用的代理人数量打破束缚）是EF1和帕累托有效的。到目前为止，大多数文献都集中在项目对算法可用的情况下。然而，在许多感兴趣的情况下，物品是在线到达的。一个典型的例子是食品银行[1,5]。世界各地的食品银行收到他们必须分配的食品捐赠；这些捐赠品往往容易腐烂，因此必须迅速做出分配决定，而捐赠品通常是剩菜剩菜，导致未来物品到达的不确定性。Benadè等人[2]研究了这个问题，但只关注公平性。他们证明了存在一种嫉妒消失的确定性算法，即当代理i对第T项的值vit归一化为[0,1]时，最大成对嫉妒（在所有T项都分配完之后）在T中是次线性的。具体地说，嫉妒保证最多为O(√p T logT /n)，并且这种保证严格依赖于多对数因子。同样的保证也可以通过简单的随机算法来实现，该算法将每个项目分配给均匀随机的代理。这些结果甚至适用于在看到前1 - 1项的分配后选择值vit的自适应对手。另一方面，如果我们只关注效率，我们的任务就容易得多。例如，我们可以简单地将每个项目分配给具有最高价值的代理。但是，这就引出了我们的兴趣所在，问题仍然存在：我们应该如何在网上做出分配决定，既对捐赠接受者公平，又尽可能高效？
A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a way that is fair and efficient. A standard fairness concept is envy-freeness, which requires that each agent prefers her own allocation over the allocation of any other agent. Even though envy is clearly unavoidable in this context - consider the case of a single indivisible good and two agents - providing approximately envy-free solutions is possible [3, 6]. Specifically, an allocation is envy-free up to one item (EF1) if for every pair of agents i and j, any envy i has for j can be eliminated by removing at most one good from j's bundle. Recently, Caragiannis et al. [3] show that the allocation that maximizes the product of the agents' utilities (with ties broken based on the number of agents with positive utility) is EF1 and Pareto efficient. The majority of the literature to date has focused on the case where the items are available to the algorithm upfront. In many situations of interest, however, items arrive online. A paradigmatic example is that of food banks [1, 5]. Food banks across the world receive food donations they must allocate; these donations are often perishable, and thus allocation decisions must be made quickly, and donations are typically leftovers, leading to uncertainty about items that will arrive in the future. Benadè et al. [2] study this problem, but focus only on fairness. They show that there exists a deterministic algorithm with vanishing envy, that is, the maximum pairwise envy (after all T items have been allocated) is sublinear in T , when the value vit of agent i for the t-th item is normalized to be in [0, 1]. Specifically, the envy is guaranteed to be at most O(√p T logT /n), and this guarantee is tight up to polylogarithmic factors. The same guarantee can also be achieved by the simple randomized algorithm that allocates each item to a uniformly random agent. These results hold even against an adaptive adversary that selects the value vit after seeing the allocation of the first t - 1 items. On the other hand, if we focus only on efficiency, our task is much easier. For example, we could simply allocate each item to the agent with the highest value. But, and this brings us to our interest here, the question remains: How should we make allocation decisions online in a way that is fair to the donation recipients, but also as efficient as possible?
登录
查看更多内容
DOI：
10.1145/3219166.3219179
发表时间：
2018-06
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
DOI：
10.1145/3313276.3316340
发表时间：
2018-09
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
J. Garg;László A. Végh
通讯作者：
J. Garg;László A. Végh
论不可分割物品的公平分割
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Cheung, Yun Kuen;Garg, Jugal;Garg, Naveen;Hoefer, Martin;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt
通过改变过去实现更公平的未来
DOI：
--
发表时间：
2019
期刊：
IJCAI'19
影响因子：
--
作者：
Procaccia, AD;Psomas, C-A;Zeng, D
通讯作者：
Zeng, D