On the structure of EFX orientations on graphs

公平分配是将一组物品公平地分配给代理的问题。其中最受欢迎的公平概念之一是无嫉妒（EF），要求没有代理人会嫉妒另一个人的分配。当物品是不可分割的时，EF概念就不再存在，而EFX成为其最强的放宽条件之一。EFX分配的存在可以说是公平分配中最大的未解问题。最近，Christodoulou，Fiat，Koutsoupias和Sgouritsa（EC 2023）展示了在图形估值的情况下EFX分配的存在，其中实例由图形表示：节点是代理，边是物品，每个代理只评估其相邻边缘。另一方面，他们证明了检查每个边缘分配给其相邻顶点的EFX方向的存在的NP难度，并要求对展示EFX方向的图形进行表征，而不考虑分配的估值。在本文中，我们在回答他们的问题方面取得了重大进展。我们引入了强EFX可定向图的概念——无论代理人如何估值边缘，都具有EFX定向的图。我们展示了这个属性与图$G$的色数$\chi(G)$之间的惊人联系。特别地，我们展示了$\chi(G)\leq 2$的图形是强EFX可定向的，而$\chi(G)>3$的图形则不是强EFX可定向的。我们提供了$\chi(G)=3$的强EFX可定向和非强EFX可定向图的示例以证明其紧密性。最后，我们对二进制估值进行限制，给出了强EFX可定向性的完整表征。

研究图的染色数与EFX分配方案之间的关系，探索图的EFX方案的存在性和特征

引入了强EFX可定向图的概念，并发现与图的染色数有关，进而得出当图的染色数小于等于2时，必然存在强EFX可定向图的结论，当图的染色数大于3时，必然不存在强EFX可定向图的结论

论文提供了关于EFX分配方案的新思路，发现了图的染色数与EFX方案之间的关系，同时通过实例探究了EFX方案的存在性和特征，为解决EFX问题提供了新的启示

最近的相关研究包括Christodoulou等人在EC 2023上发表的研究，该研究展示了对于图形估值，存在EFX分配方案的存在性，同时也证明了检查EFX方向的存在性是NP难的，因此提出了对于图的特征进行研究的问题