Improving EFX Guarantees through Rainbow Cycle Number
Improving EFX Guarantees through Rainbow Cycle Number
复制标题
通过 Rainbow Cycle Number 改善 EFX 保证
DOI：
10.1145/3465456.3467605
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Misra, Pranabendu
中科院分区：
文献类型：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;Mehlhorn, Kurt;Mehta, Ruta;Misra, Pranabendu
我们研究了在 n 个具有附加估值的代理人之间公平分配一组不可分割的商品的问题。在这种情况下，无嫉妒（EFX）可以说是最引人注目的公平概念。然而，EFX分配的存在尚未得到解决，是公平分配中最重要的问题之一[5]。为了解决这个问题，许多令人印象深刻的结果表明了其松弛的存在。特别是，[1] 显示了 0.618-EFX 分配的存在，而 [4] 显示了如果我们不分配至多 n - 1 件商品，则 EFX 分配存在。最近，[2]中的三个代理的结果得到了改进，其中两个未分配的货物通过相关程序进行分配。减少任意数量的代理的未分配货物数量是解决这个大问题的系统方法。
We study the problem of fairly allocating a set of indivisible goods among n agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division [5]. Towards resolving this problem, many impressive results show the existence of its relaxations. In particular, [1] shows the existence of 0.618-EFX allocations, and [4] shows that EFX allocation exists if we do not allocate at most n - 1 goods. The latter result was recently improved for three agents in [2], in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for an arbitrary number of agents is a systematic way to settle the big question.
登录
查看更多内容
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G
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：
10.1137/20m1353381
发表时间：
2020
期刊：
ArXiv
影响因子：
--
作者：
Pasin Manurangsi;Warut Suksompong
通讯作者：
Warut Suksompong
一石多鸟：通过 Envy Cycle Elimination 击败 EFX 和 GMMS 的 1/2
DOI：
10.1609/aaai.v34i02.5545
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Georgios Amanatidis;Apostolos Ntokos;E. Markakis
通讯作者：
E. Markakis
影响因子：
22.7
作者：
Ariel D. Procaccia
通讯作者：
Ariel D. Procaccia