论文标题
在2值实例中最大化NASH社会福利：划定障碍性
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
论文作者
论文摘要
我们研究了在\ emph {2-value添加剂估值}中分配一组不可分割的商品的问题。在此设置中，对于某些固定的共同数字$ p，q \ in \ nn $，每种商品的价值$ 1 $或$ \ sfrac {p} {q} $，因此$ 1 \ leq q <p $。我们的目标是找到最大化\ emph {nash社会福利}（\ nsw）的分配，即代理商的估值的几何平均值。在这项工作中，我们给出了\ nsw \最大化的多项式时间障碍的完整表征，该障碍仅取决于$ q $的值。 我们首先提供一个相当简单的多项式算法，以在估值函数为\ emph {Integral}时找到最大\ nsw \分配，也就是说，$ q = 1 $。然后，我们利用更多涉及的技术来获取算法，该算法为\ emph {famemph {Half-integral}情况产生最大\ nsw \分配，即，$ q = 2 $。最后，我们表明，每当$ q \ geq3 $时，计算最大\ nsw \分配是\ classNP-hard。
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either $1$ or $\sfrac{p}{q}$, for some fixed co-prime numbers $p,q\in \NN$ such that $1\leq q < p$. Our goal is to find an allocation maximizing the \emph{Nash social welfare} (\NSW), i.e., the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of \NSW\ maximization that solely depends on the values of $q$. We start by providing a rather simple polynomial-time algorithm to find a maximum \NSW\ allocation when the valuation functions are \emph{integral}, that is, $q=1$. We then exploit more involved techniques to get an algorithm producing a maximum \NSW\ allocation for the \emph{half-integral} case, that is, $q=2$. Finally, we show it is \classNP-hard to compute an allocation with maximum \NSW\ whenever $q\geq3$.
