论文标题
通过匹配和本地搜索近似纳什社会福利
Approximating Nash Social Welfare by Matching and Local Search
论文作者
论文摘要
对于任何$ \ eps> 0 $，我们给出了一个简单，确定性的$（4+ \ eps）$ - 在superioluardular估值下的NASH社会福利（NSW）问题的近似算法。我们还考虑了该问题的不对称变体，其中目的是最大化代理估值的加权几何平均值，并给出$（ω + 2 + \ eps）\ ee $ - appproximation，如果最大的权重和平均权重之间的比率最多为$ω$。 我们还表明，$ \ nfrac12 $ -efx嫉妒属性可以通过恒定因子近似同时获得。更确切地说，我们可以在多项式时间内找到分配，既是$ \ nfrac12 $ -efx和$（8+ \ eps）$ - 在sublodoular估值下与对称的NSW问题的近似。
For any $\eps>0$, we give a simple, deterministic $(4+\eps)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents' valuations, and give an $(ω+ 2 + \eps) \ee$-approximation if the ratio between the largest weight and the average weight is at most $ω$. We also show that the $\nfrac12$-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both $\nfrac12$-EFX and a $(8+\eps)$-approximation to the symmetric NSW problem under submodular valuations.
