Almost Full EFX Exists for Four Agents
Almost Full EFX Exists for Four Agents
复制标题
四名特工的 EFX 几乎已满
DOI：
10.1609/aaai.v36i5.20410
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Fiat
中科院分区：
文献类型：
--
作者：
Ben Berger;Avi Cohen;M. Feldman;A. Fiat
EFX商品分配的存在是公平分裂的一个主要开放问题，即使是为了增加估值。目前的最新状态是，众所周知EFX分配不可能，而存在结果仅是针对非常有限的设置而闻名的，例如：（i）具有相同估值的代理，（ii）2代理，以及（ iii）3个具有添加估值的代理商。还知道，如果可以将n-1项目留在n是代理数量的情况下，则存在EFX。
我们开发了新技术，使我们能够将神秘的EFX问题的边界推向这些已知结果，并（可以说）简化早期结果的证明。我们的主要结果是，每个具有4种添加剂代理的设置都允许EFX分配，最多将一项未分配的项目留下。除了我们的主要结果外，我们还引入了一种新的估值，称为可取消的不错的估值，其中包括添加剂，单位需求，预算添加和乘法估值等。使用我们的新技术，我们表明，添加估值的结果和以前的结果都扩展到了可取消的估值。
The existence of EFX allocations of goods is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and yet, existence results are known only for very restricted settings, such as: (i) agents with identical valuations, (ii) 2 agents, and (iii) 3 agents with additive valuations. It is also known that EFX exists if one can leave n-1 items unallocated, where n is the number of agents.
We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. Beyond our main result, we introduce a new class of valuations, termed nice cancelable, which includes additive, unit-demand, budget-additive and multiplicative valuations, among others. Using our new techniques, we show that both our results and previous results for additive valuations extend to nice cancelable valuations.
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G
通过 Rainbow Cycle Number 改善 EFX 保证
DOI：
10.1145/3465456.3467605
发表时间：
2021
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation (EC
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;Mehlhorn, Kurt;Mehta, Ruta;Misra, Pranabendu
通讯作者：
Misra, Pranabendu
EFX 存在三个代理
DOI：
10.1145/3391403.3399511
发表时间：
2020
期刊：
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
Chaudhury, Bhaskar R.;Garg, Jugal;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt