EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number
提出一种更简单的方法，证明当三个代理人中至少一人具有可加估值时，存在EFX分配，并几乎解决了关于彩虹圈数的猜想，从而得到通过该方法可实现近似EFX分配所需未分配物品数的（几乎）紧界。
A Simpler Approach to the EFX Problem Envy-freeness up to any item (EFX) has emerged as a compelling fairness notion in discrete fair division. However, its existence remains one of the biggest open problems in the field. In a breakthrough, Chaudhury et al. (2020) establish the existence of EFX allocations for three agents with additive valuations through intricate case analysis. The paper “EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number” by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta offers a simpler approach for improving the EFX guarantee. They demonstrate the existence of EFX allocations for three agents when at least one has additive valuations (whereas the other two have general monotone valuations). Additionally, they nearly resolve a conjecture regarding the rainbow cycle number, leading to an (almost) tight bound for the existence of approximate EFX allocations with few unallocated items achievable through this approach.