arXiv:2406.12413v2 宣告类型: 替换-交叉 摘要: 我们研究了一种将不可分割的商品集合分配给具有加性评价函数的代理集合的问题，目标是实现任意商品近似不嫉妒（$\alpha$-EFX）。关于该问题的最新结果包括：（a）当代理人数不超过三个时；（b）代理人的评价函数最多只能取两个值时；（c）代理人的评价函数可以用图表示时，存在精确的EFX分配。对于$\alpha$-EFX，已知当代理人的评价函数为加性时，存在0.618-EFX分配。在本文中，我们表明，在以下情况下存在$\frac{2}{3}$-EFX分配：（a）代理人数不超过七个；（b）代理人的评价函数最多只能取三个值；（c）代理人的评价函数可以用多重图表示。我们的结果可以从两个方面进行解释。首先，通过将EFX的概念放宽到$\frac{2}{3}$-EFX，我们得到了严格泛化已知存在精确EFX分配的设置的结果。其次，通过对设置施加限制，我们设法突破了0.618的障碍，实现了$\frac{2}{3}$的近似保证。因此，我们的结果推动了近似EFX分配存在性和计算性的边界，并为精确EFX分配的存在性问题提供了见解。