论文标题
几乎嫉妒，嫉妒和纳什的社会福利比赛
Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings
论文作者
论文摘要
对于不可分割的物品而言，无嫉妒的无效（EF1）和无嫉妒的无效（EFX）是嫉妒的两个众所周知的嫉妒。结果表明，对于具有次要估值的代理商，可以保证EF1。相比之下，即使对于四个代理和添加剂估值，尚不清楚EFX分配是否总是存在。此外，Amanitidis等人的EFX的最佳近似保证为$（ϕ-1）\ simeq 0.61 $。 为了找到一个弥合这一差距的中间立场，在本文中，我们建议另一个公平标准，即嫉妒的柔性，直至随机的商品或EFR，它比EFX弱，但比EF1强。对于此概念，我们提供多项式时间$ 0.73 $ - 附件分配算法。对于我们的算法，我们介绍了NASH的社会福利匹配，这与Nash社会福利和嫉妒的Freeness之间建立了联系。我们认为，纳什社会福利匹配将在未来的工作中找到其应用。
Envy-free up to one good (EF1) and envy-free up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations. In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is $(ϕ-1) \simeq 0.61$ by Amanitidis et al.. In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envy-freeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time $0.73$-approximation allocation algorithm. For our algorithm, we introduce Nash Social Welfare Matching which makes a connection between Nash Social Welfare and envy freeness. We believe Nash Social Welfare Matching will find its applications in future work.
