arXiv:2504.03951v1 声明类型: cross 摘要: 至少与任何其它物品相比更满意的分配 (envy-freeness up to any good, EFX) 是在分配不可分物品的公平分配中一个流行且重要的公平性属性，其在一般情况下的存在性仍是一个开放问题。在这项工作中，我们研究确定给定实例中达到EFX分配的最小数量的问题，认为这种方法可能会为EFX分配的存在性和计算提供有价值的见解。我们着重于商品数量略微超过参与者的实例，并将我们的分析扩展到加权EFX (WEFX) 以及一种针对一般单调估值的新颖EFX变体，称为EFX+。通过这种方式，我们确定了满足这些公平性观念的分配存在的过渡阈值。值得一提的是，我们通过证明在二进制可加估值下WEFX的多项式时间可计算性来解决关于WEFX的开放问题，并建立了第一个常数因子近似值，适用于两名参与者的情况。