EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
复制标题
EFX：一种更简单的方法和通过 Rainbow Cycle Number 提供的（几乎）最佳保证
DOI：
10.1145/3580507.3597799
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Mehta, Ruta
中科院分区：
文献类型：
--
作者：
Akrami, Hannaneh;Alon, Noga;Chaudhury, Bhaskar Ray;Garg, Jugal;Mehlhorn, Kurt;Mehta, Ruta
在离散公平分配中，存在可达任何利益分配的无嫉妒性是一个基本的开放性问题。目标是确定在从其他代理的捆绑包中移除任何单一商品后，代理之间是否存在一组不可分割商品的分配，这些商品没有任何代理会嫉妒其他代理。由于一般问题一直难以捉摸，因此在两个方面取得了进展：(i)证明在很小的情况下存在，（ii）证明EFX松弛的存在。在本文中，我们用新技术改进和简化了这两个方面的最新结果。对于三个代理的情况，EFX的存在首先与可加性估值一起显示，然后扩展到良好的可取消估值。作为我们的第一个主要结果，我们通过证明当两个代理具有一般单调估值且一个代理具有最大份额(MMS) -可行估值（良好可取消估值函数的严格概括）时存在EFX分配来简化和改进该结果。我们的方法比之前的方法简单得多，它也避免了使用嫉妒图和冠军图的标准概念，并且可能在其他公平分配问题中找到用途。其次，我们考虑近似的EFX分配，很少有未分配的货物（慈善）。利用极值组合中的彩虹循环数（RCN）问题，建立了具有慈善性的efx分配的存在性。这是通过RCN后维的上限来完成的。他们推测RCN是。我们几乎通过改进上界来解决这个猜想，从而通过这种方法得到O ~ （(n/ λ)12）的（几乎）最优慈善。我们的技术比以前的方法简单得多，并且是基于概率方法的。本工作得到计算与通信基金会（B. R. Chaudhury， R. Mehta， J. Garg）[赠款CCF-1750436， CCF-1942321, CCF-2334461]，美国国家科学基金会（N. Alon）[赠款DMS-2154082]和美国-以色列两国科学基金会（N. Alon）[赠款2018267]的支持。
The existence of envy-freeness up to any good (EFX) allocations is a fundamental open problem in discrete fair division. The goal is to determine the existence of an allocation of a set of indivisible goods amongnagents for which no agent envies another, following the removal of any single good from the other agent’s bundle. Because the general problem has been elusive, progress is made on two fronts: (i) proving existence whennis small and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques. For the case of three agents, the existence of EFX was first shown with additive valuations and then extended to nice-cancelable valuations. As our first main result, we simplify and improve this result by showing the existence of EFX allocations when two of the agents have general monotone valuations and one has a maximin share (MMS)–feasible valuation (a strict generalization of nice-cancelable valuation functions). Our approach is significantly simpler than the previous ones, and it also avoids using the standard concepts of envy graph and champion graph and may find use in other fair-division problems. Second, we consider approximate EFX allocations with few unallocated goods (charity). Through a promising new method using a problem in extremal combinatorics called rainbow cycle number (RCN), the existence of-EFX allocation withcharity was established. This is done by upper bounding the RCN byind-dimension. They conjecture RCN to be. We almost settle this conjecture by improving the upper bound toand thereby get (almost) optimal charity of O˜((n/ϵ)12) that is possible through this method. Our technique is much simpler than the previous ones and is based on the probabilistic method.Funding:This work was supported by the Division of Computing and Communication Foundations (B. R. Chaudhury, R. Mehta, J. Garg) [Grants CCF-1750436, CCF-1942321, CCF-2334461], the National Science Foundation (N. Alon) [Grant DMS-2154082], and the United States–Israel Binational Science Foundation (N. Alon) [Grant 2018267].