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.

翻译：我们研究的是,在对货物进行相同和添加性估价的代理商之间如何有效、公平地分配一套不可分割的商品的问题。目标是最大限度地增加纳什社会福利,这是纳什社会福利的几何平均值。在尽量扩大纳什社会福利是NP-硬体的同时,Nguyen和Rothe提出了解决这一问题的PTAS。本文的主要贡献是针对这一问题设计第一种添加式PTAS,即我们给出一个多元时间算法,将纳什社会福利最大化于一个添加式错误($\varepsilon v ⁇ rm max}$,其中,$varepsilon是任意的正数,$värm max}是一件好事的最大效用。我们的算法的近似性效果比PTAS要好。我们的算法概念很简单;我们采用了一种预处理方法,然后用一个添加式的PTASS来应对布切姆等人最近提出的目标负荷平衡问题。然而,评价产出的添加性错误需要非三倍的工作量。