论文标题
NASH社会福利最大化的添加剂近似方案，并具有相同的添加估值
An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations
论文作者
论文摘要
我们研究了在商品中具有相同和加性估值的代理商中有效，公平地分配一组不可分割的商品的问题。目的是最大化纳什社会福利，这是代理人估值的几何平均值。虽然最大化纳什的社会福利是NP-Hard，但Nguyen和Rothe提出了这个问题的PTA。本文的主要贡献是为此问题设计第一个添加剂PTA，也就是说，我们给出了一种多项式时间算法，该算法最大化添加剂错误$ \ varepsilon v _ {\ rm max} $，在$ \ varepsilon $中，$ v v _ iS $ v _ _ max} $ rm crm c rm max rm max rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm rm max rm rm max rm max {我们的算法的近似性能优于PTA。我们算法的想法很简单；我们应用预处理，然后利用Buchem等人最近给出的目标负荷平衡问题的加性PTA。但是，需要进行非平凡的工作来评估输出的加成误差。
We study the problem of efficiently and fairly allocating a set of indivisible goods among agents with identical and additive valuations for the goods. The objective is to maximize the Nash social welfare, which is the geometric mean of the agents' valuations. While maximizing the Nash social welfare is NP-hard, a PTAS for this problem is presented by Nguyen and Rothe. The main contribution of this paper is to design a first additive PTAS for this problem, that is, we give a polynomial-time algorithm that maximizes the Nash social welfare within an additive error $\varepsilon v_{\rm max}$, where $\varepsilon$ is an arbitrary positive number and $v_{\rm max}$ is the maximum utility of a good. The approximation performance of our algorithm is better than that of a PTAS. The idea of our algorithm is simple; we apply a preprocessing and then utilize an additive PTAS for the target load balancing problem given recently by Buchem et al. However, a nontrivial amount of work is required to evaluate the additive error of the output.
