problem  Input: Output:

# An Additive Approximation Scheme for the Nash Social Welfare Maximization
with Identical Additive Valuations††thanks: This work is partly supported by
JSPS, KAKENHI grant numbers JP18H05291, JP19H05485, and JP20K11692, Japan.

Asei Inoue Kyoto University, Japan. Yusuke Kobayashi Kyoto University, Japan.
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

###  1.1 Nash Social Welfare Maximization

We study the problem of efficiently and fairly allocating a set of indivisible
goods among agents with identical and additive valuations for the goods. There
are many ways to measure the quality of the allocation in the literature, and
in this paper, we aim to maximize the Nash social welfare [14], which is the
geometric mean of the agents’ valuations in the allocation.

Suppose we are given a set of agents $\mathcal{A}=\\{1,2,\dots,n\\}$ and a set
of goods $\mathcal{G}=\\{1,2,\dots,m\\}$ with a utility $v_{j}>0$ for each
$j\in\mathcal{G}$. An allocation is a partition $\pi=(\pi_{1},\dots,\pi_{n})$
of $\mathcal{G}$ where $\pi_{i}\subseteq\mathcal{G}$ is a set of goods
assigned to agent $i$. For an allocation $\pi=(\pi_{1},\dots,\pi_{n})$, let
$v(\pi_{i})$ be the valuation of $i$ that is defined as the sum of the utility
of the goods assigned to $i$, i.e., $v(\pi_{i})=\sum_{j\in\pi_{i}}v_{j}$. The
goal is to find an allocation $\pi$ that maximizes the function

$f(\pi)=\left(\prod_{i\in\mathcal{A}}v(\pi_{i})\right)^{1/n},$

which is called the Nash social welfare [4, 21]. In this paper, we refer to
this problem as Identical Additive NSW.

The Nash social welfare can be defined in a more general setting where the
valuation of each agent $i$ is determined by a set function $v_{i}\colon
2^{\mathcal{G}}\to{\mathbb{R}}_{\geq 0}$. In such a case, the Nash social
welfare of an allocation $\pi=(\pi_{1},\dots,\pi_{n})$ is defined as
$\left(\prod_{i\in\mathcal{A}}v_{i}(\pi_{i})\right)^{1/n}$. In Identical
Additive NSW, we focus on the case where the valuation function is additive
and independent of the agent. Note that, by removing goods with zero utility,
we can assume that $v_{j}>0$ without loss of generality.

The Nash social welfare was named after John Nash, who introduced and studied
the Nash social welfare in the context of bargaining in the 1950s [20]. Later,
the same concept was independently studied in the context of competitive
equilibria with equal incomes [22] and proportional fairness in networking
[15]. It has traditionally been studied in the economics literature for
divisible goods [19]. For divisible goods, an allocation maximizing the Nash
social welfare can be computed in polynomial time when the valuation functions
are additive [10].

In the context of goods allocation, the Nash social welfare is a measure that
captures efficiency and fairness at the same time. To see this, for a
parameter $q\in{\mathbb{R}}$ and for an allocation $\pi$, one can define the
generalized mean of the valuation of each agent as
$f_{q}(\pi)=\left(\frac{1}{n}\sum_{i=1}^{n}v_{i}(\pi_{i})^{q}\right)^{1/q}$.
The generalized mean can be a variety of mean functions depending on the value
of $q$. When $q=1$, $f_{q}(\pi)$ is the average valuation of the agents, and
hence maximizing $f_{q}(\pi)$ is equivalent to maximizing the social welfare.
In this case, $f_{q}(\pi)$ is a measure of the efficiency of an allocation.
When $q\to-\infty$, $f_{q}(\pi)$ is the minimum value of $v_{i}(\pi_{i})$,
namely the valuation of the least satisfied agent. In this case, an allocation
maximizing $f_{q}(\pi)$ can be considered fair in a sense. It is known that in
the limit as $q\to 0$, $f_{q}(\pi)$ coincides with the geometric mean, which
is the Nash social welfare (see [7]). Therefore, maximizing the Nash social
welfare (i.e., $q\to 0$) can be viewed as a compromise between Maximum Social
Welfare (i.e., $q=1$) and Max-Min Welfare (i.e., $q\to-\infty$).

The Nash social welfare is closely related to other concepts EF1 and Pareto
optimality that describe fairness and efficiency, respectively, which also
supports the importance of the Nash social welfare. An allocation is said to
be EF1 (envy-free up to at most one good) if each agent prefers its own bundle
over the bundle of any other agent up to the removal of one good. An
allocation is called Pareto optimal if no one else’s valuation can be
increased without sacrificing someone else’s valuation. Caragiannis et al. [8]
showed that an allocation that maximizes the Nash social welfare is both EF1
and Pareto optimal when agents have additive valuations for the goods. This
motivates studying the problem of finding an allocation that maximizes the
Nash social welfare.

###  1.2 Our Contribution: Approximation Algorithm

The topic of this paper is the approximability of the Nash social welfare
maximization. By an easy reduction from the Subset Sum problem, we can see
that maximizing the Nash social welfare is NP-hard even in the case of two
agents with identical additive valuations. That is, Identical Additive NSW is
NP-hard even when $n=2$. Furthermore, maximizing the Nash social welfare is
APX-hard for multiple agents with non-identical valuations even when the
valuations are additive [16].

On a positive side, several approximation algorithms are proposed for
maximizing the Nash social welfare, and the difficulty of the problem depends
on the class of valuations $v_{i}$. Under the assumption that the valuation
set function is monotone and submodular, Li and Vondrák [17] recently proposed
a constant factor approximation algorithm based on an algorithm for Rado
valuations [12]. Better constant factor approximation algorithms are known for
subclasses of submodular functions [18, 2, 9, 11]. When the valuation function
is additive, a $1.45$-approximation algorithm is known [3], and this is the
current best approximation ratio. When the valuation functions are additive
and identical, the situation is much more tractable. Indeed, for Identical
Additive NSW, it is known that a polynomial-time approximation scheme (PTAS)
exists [21] and a simple fast greedy algorithm achieves a
$1.061$-approximation guarantee [4].

For Identical Additive NSW, the above results show the limit of the
approximability and so no further improvement seems to be possible in terms of
the approximation ratio. Nevertheless, a better approximation algorithm may
exist if we evaluate the approximation performance in a fine-grained way. The
main contribution of this paper is to show that this is indeed the case if we
evaluate the approximation performance by using the additive error. Formally,
our result is stated as follows.

######  Theorem 1.

For an instance of Identical Additive NSW, let
$v_{\max}=\max_{j\in\mathcal{G}}v_{j}$ and let $\mathrm{OPT}$ be the optimal
value. For any ${\varepsilon}>0$, there is an algorithm $A_{{\varepsilon}}$
for Identical Additive NSW that runs in
$(nm/{\varepsilon})^{O(1/{\varepsilon})}$ time and returns an allocation $\pi$
such that $f(\pi)\geq\mathrm{OPT}-{\varepsilon}v_{\max}$.

Recall that a PTAS for Identical Additive NSW is an algorithm that returns an
allocation $\pi$ with $f(\pi)\geq\frac{\mathrm{OPT}}{1+{\varepsilon}}$. Since
$\frac{\mathrm{OPT}}{1+{\varepsilon}}\approx(1-{\varepsilon})\mathrm{OPT}$,
the additive error of a PTAS is roughly ${\varepsilon}\mathrm{OPT}$, which can
be much greater than ${\varepsilon}v_{\max}$. Furthermore, as we will see in
Proposition 11, our algorithm given in the proof of Theorem 1 is also a PTAS.
In this sense, we can say that our algorithm is better than a PTAS if we
evaluate the approximation performance in a fine-grained way.

We also note that there is no polynomial-time algorithm for finding an
allocation $\pi$ with $f(\pi)\geq\mathrm{OPT}-{\varepsilon}$ unless ${\rm
P}={\rm NP}$. This is because the additive error can be arbitrarily large by
scaling the utility unless we obtain an optimal solution. Therefore, parameter
$v_{\max}$ is necessary to make the condition scale-invariant.

###  1.3 Related Work: Additive PTAS

The algorithm in Theorem 1 is called an additive PTAS with parameter
$v_{\max}$, and so our result has a meaning in a sense that it provides a new
example of a problem for which an additive PTAS exists. In this subsection, we
describe known results on additive PTASs, some of which are used in our
argument later.

An additive PTAS is a framework for approximation guarantees that was recently
introduced by Buchem et al. [5, 6]. For any ${\varepsilon}>0$, an additive
PTAS returns a solution whose additive error is at most ${\varepsilon}$ times
a certain parameter.

######  Definition 2.

For an optimization problem, an additive PTAS is a family of polynomial-time
algorithms $\\{A_{\varepsilon}\mid{\varepsilon}>0\\}$ with the following
condition: for any instance $I$ and for every ${\varepsilon}>0$,
$A_{\varepsilon}$ finds a solution with value $A_{{\varepsilon}}(I)$
satisfying $\left\lvert
A_{{\varepsilon}}(I)-\mathrm{OPT}(I)\right\rvert\leq{\varepsilon}h$, where $h$
is a suitably chosen parameter of instance $I$ and $\mathrm{OPT}(I)$ is the
optimal value.

In some cases, an additive PTAS is immediately derived from an already known
algorithm. For example, by setting the error factor appropriately, a fully
polynomial-time approximation scheme (FPTAS) for the knapsack problem [13] is
also an additive PTAS where the parameter is the maximum utility of a good.
However, evaluating the additive error is difficult in general, and so
additive PTASs are known for only a few problems. In the pioneering paper on
additive PTASs by Buchem et al. [5, 6], an additive PTAS was proposed for the
completion time minimization scheduling problem, the Santa Claus problem, and
the envy minimization problem. In order to derive these additive PTASs, they
introduced the target load balancing problem and showed that it is possible to
determine whether a solution exists by only slightly violating the
constraints.

In the target load balancing problem, we are given a set of jobs $\mathcal{J}$
with a processing time $v_{j}>0$ for each $j\in\mathcal{J}$ and a set of
machines $\mathcal{M}$ with real values $l_{i}$ and $u_{i}$ for each
$i\in\mathcal{M}$. The goal is to assign each job $j\in\mathcal{J}$ to a
machine $i\in\mathcal{M}$ such that for each machine $i\in\mathcal{M}$ the
load of $i$ (i.e., the sum of the processing times of the jobs assigned to
$i$) is in the interval $[l_{i},u_{i}]$. In a similar way to Identical
Additive NSW, an assignment is represented by a partition
$\pi=(\pi_{i})_{i\in\mathcal{M}}$ of $\mathcal{J}$. Let
$v_{\max}=\max_{j\in\mathcal{J}}v_{j}$ and let $K$ denote the number of types
of machines, that is, $K=|\\{(l_{i},u_{i})\mid i\in\mathcal{M}\\}|$. While the
target load balancing problem is NP-hard, Buchem et al. [5, 6] showed that it
can be solved in polynomial time if we allow a small additive error and $K$ is
a constant.

######  Theorem 3 (Buchem et al. [5, Theorem 12]).

For the target load balancing problem and for any ${\varepsilon}>0$, there is
an algorithm (called LoadBalancing) that either

  1. 1.

concludes that there is no feasible solution for a given instance, or

  2. 2.

returns an assignment $\pi=(\pi_{i})_{i\in\mathcal{M}}$ such that the total
load $\sum_{j\in\pi_{i}}v_{j}$ is in
$[l_{i}-{\varepsilon}v_{\max},u_{i}+{\varepsilon}v_{\max}]$ for each
$i\in\mathcal{M}$

in
$|\mathcal{M}|^{K+1}(\frac{|\mathcal{J}|}{{\varepsilon}})^{O(1/{\varepsilon})}$
time.

Note that the algorithm in this theorem is used as a subroutine in our
additive PTAS for Identical Additive NSW. Note also that the term “assignment”
is used in this theorem by following the convention, but it just means a
partition of the jobs. Therefore, we do not distinguish “assignment” and
“allocation” in what follows in this paper.

###  1.4 Technical Highlights

In this subsection, we describe the outline of our algorithm for Identical
Additive NSW and explain two technical issues that are peculiar to additive
errors.

The basic strategy of our algorithm is simple; we guess the valuation
$v(\pi^{*}_{i})$ of each agent $i$ in an optimal solution $\pi^{*}$, and then
seek for an allocation $\pi$ such that
$|v(\pi_{i})-v(\pi^{*}_{i})|\leq{\varepsilon}v_{\max}$ for each
$i\in\mathcal{A}$ by using LoadBalancing in Theorem 3.

The first technical issue is that even if the additive error of $v(\pi_{i})$
is at most ${\varepsilon}v_{\max}$ for each $i\in\mathcal{A}$, the additive
error of $f(\pi)$ is not easily bounded by ${\varepsilon}v_{\max}$. This is in
contrast to the case of the multiplicative error (i.e., if $v(\pi_{i})\geq
v(\pi^{*}_{i})/(1+{\varepsilon})$ for each $i\in\mathcal{A}$, then $f(\pi)\geq
f(\pi^{*})/(1+{\varepsilon})$). The first technical ingredient in our proof is
to bound the additive error of $f(\pi)$ under the assumption that $v_{\max}$
is at most the average valuation of the agents; see Lemma 9 for a formal
statement. In order to apply this argument, we modify a given instance so that
$v_{\max}$ is at most the average valuation of the agents by a naive
preprocessing. In the preprocessing, we assign a good $j$ with high utility to
an arbitrary agent $i$ and remove $i$ and $j$ from the instance, repeatedly
(see Section 2.1 for details).

The second technical issue is that the preprocessing might affect the additive
error of the output, whereas it does not affect the optimal solutions of the
instance (see Lemma 4). Suppose that an instance $I$ is converted to an
instance $I^{\prime}$ by the preprocessing, and suppose also that we obtain an
allocation $\pi^{\prime}$ for $I^{\prime}$. Then, by recovering the agents and
the goods removed in the preprocessing, we obtain an allocation $\pi$ for $I$
from $\pi^{\prime}$. The issue is that the additive error of the objective
function value might be amplified by this recovering process, which makes the
evaluation of the additive error of $f(\pi)$ hard. Nevertheless, we show that
the additive error of $f(\pi)$ is bounded by $O({\varepsilon}v_{\max})$ with
the aid of the mean-value theorem for differentiable functions (see
Proposition 12), which is the second technical ingredient in our proof. It is
worth noting that the differential calculus plays a crucial role in the proof,
whereas the problem setting is purely combinatorial.

The remaining of this paper is organized as follows. In Section 2, we describe
our algorithm for Identical Additive NSW. Then, in Section 3, we show its
approximation guarantee and prove Theorem 1.

##  2 Description of the Algorithm

As we mentioned in Section 1.4, in our algorithm, we first apply a
preprocessing so that $v_{\max}$ is at most the average valuation of the
agents. Then, we guess the valuation of each agent in an optimal solution, and
then seek for an allocation that is close to the optimal solution by using
LoadBalancing, which is the main procedure. We describe the preprocessing and
the main procedure in Sections 2.1 and 2.2, respectively.

###  2.1 Preprocessing

Consider an instance $I=(\mathcal{A},\mathcal{G},\mathbf{v})$ of Identical
Additive NSW where $\mathbf{v}=(v_{1},\dots,v_{m})$. If
$|\mathcal{A}|>|\mathcal{G}|$, then the optimal value is zero, and hence any
allocation is optimal. Therefore, we may assume that
$|\mathcal{A}|\leq|\mathcal{G}|$, which implies that the optimal value is
positive. Let $\mu(I)$ be the average valuation of agents, that is,
$\mu(I)=\frac{1}{|\mathcal{A}|}\sum_{j\in\mathcal{G}}v_{j}$. When $I$ is
obvious, we simply write $\mu$ for $\mu(I)$. The objective of the
preprocessing is to modify a given instance so that $v_{j}<\mu$ for any
$j\in\mathcal{G}$.

Our preprocessing immediately follows from the fact that an agent who receives
a valuable good does not receive other goods in an optimal solution. Although
similar observations were shown in previous papers (see e.g. [1, 21]), we give
a proof for completeness.

######  Lemma 4.

Let $j\in\mathcal{G}$ be an item with $v_{j}\geq\mu$. In an optimal solution
$\pi^{*}$, an agent who receives $j$ cannot receive any goods other than $j$.

###### Proof.

Assume to the contrary that $\pi^{*}$ is an optimal solution which assigns
goods $j$ and $l$ to the same agent $i\in\mathcal{A}$. This implies
$v(\pi^{*}_{i})>\mu$ and so there must be at least one agent $k\in\mathcal{A}$
such that $v(\pi^{*}_{k})<\mu$. Let $\pi^{\prime}$ be the new allocation
obtained from $\pi^{*}$ by reassigning good $l$ to agent $k$. Then, we obtain

$\displaystyle
v(\pi^{\prime}_{i})v(\pi^{\prime}_{k})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=(v(\pi^{*}_{i})-v_{l})(v(\pi^{*}_{k})+v_{l})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=v_{l}(v(\pi^{*}_{i})-v(\pi^{*}_{k})-v_{l})$ $\displaystyle\geq
v_{l}(v_{j}-v(\pi^{*}_{k}))$ $\displaystyle\geq v_{l}(\mu-v(\pi^{*}_{k}))$
$\displaystyle>0.$

This implies that $f(\pi^{\prime})>f(\pi^{*})$, which contradicts the
optimality of $\pi^{*}$. ∎

For $\mathcal{A}_{0}\subseteq\mathcal{A}$ and
$\mathcal{G}_{0}\subseteq\mathcal{G}$, let
$I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$ denote the instance obtained
from $I$ by removing $\mathcal{A}_{0}$ and $\mathcal{G}_{0}$, that is,
$I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})=(\mathcal{A}\setminus\mathcal{A}_{0},\mathcal{G}\setminus\mathcal{G}_{0},\mathbf{v}\setminus\mathcal{G}_{0})$,
where
$\mathbf{v}\setminus\mathcal{G}_{0}=(v_{j})_{j\in\mathcal{G}\setminus\mathcal{G}_{0}}$.
In the preprocessing, we assign a good $j\in\mathcal{G}$ with $v_{j}\geq\mu$
to some agent $i\in\mathcal{A}$ and remove $i$ and $j$ from the instance,
repeatedly. A formal description is shown in Algorithm 1.

Algorithm 1 Preprocessing

1:instance $I=(\mathcal{A},\mathcal{G},\mathbf{v})$ where
$\mathbf{v}=(v_{1},v_{2},\dots,v_{m})$

2:subsets $\mathcal{A}_{0}\subseteq\mathcal{A}$ and
$\mathcal{G}_{0}\subseteq\mathcal{G}$

3:Initialize $\mathcal{A}_{0}$ and $\mathcal{G}_{0}$ as
$\mathcal{A}_{0}=\mathcal{G}_{0}=\emptyset$.

4:while there exists a good $j\in\mathcal{G}\setminus\mathcal{G}_{0}$ with
$v_{j}\geq\mu(I\setminus(\mathcal{A}_{0},\mathcal{G}_{0}))$ do

5: $\mathcal{G}_{0}\leftarrow\mathcal{G}_{0}\cup\\{j\\}$

6: Choose $i\in\mathcal{A}\setminus\mathcal{A}_{0}$ arbitrarily and add it to
$\mathcal{A}_{0}$.

7:return $\mathcal{A}_{0}$, $\mathcal{G}_{0}$

Let $\mathcal{A}_{0}$ and $\mathcal{G}_{0}$ be the output of Preprocessing.
Lemma 4 shows that if we obtain an optimal solution for
$I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$, then we can immediately obtain
an optimal solution for $I$ by assigning each good in $\mathcal{G}_{0}$ to
each agent in $\mathcal{A}_{0}$. Note that the inequality
$v_{j}<\mu(I\setminus(\mathcal{A}_{0},\mathcal{G}_{0}))$ holds for all
$j\in\mathcal{G}\setminus\mathcal{G}_{0}$ after the preprocessing. Thus, the
maximum utility of a good is less than the average valuation of the agents in
the instance $I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$. Note also that,
since the number of while loop iterations is at most $|\mathcal{A}|$,
Preprocessing runs in polynomial time.

###  2.2 Main Procedure

We describe the main part of the algorithm, in which we guess the valuation of
each agent in an optimal solution and then apply LoadBalancing. In order to
obtain a polynomial-time algorithm, we have the following difficulties: the
number of guesses has to be bounded by a polynomial and the number of machine
types $K$ has to be a constant when we apply LoadBalancing. To overcome these
difficulties, we get good upper and lower bounds on the valuation of each
agent in an optimal solution, which is a key observation in our algorithm. We
prove the following lemma by tracing the proof of Lemma 4.

######  Lemma 5.

For any instance $I$ of Identical Additive NSW, let $\pi^{*}$ be an optimal
allocation of $I$. Then,

$\mu-v_{\max}<v(\pi^{*}_{i})<\mu+v_{\max}$

holds for any $i\in\mathcal{A}$.

###### Proof.

Assume that there is some agent $i\in\mathcal{A}$ with
$v(\pi^{*}_{i})\geq\mu+v_{\max}$. This implies that $v(\pi^{*}_{i})>\mu$ and
so there must be at least one agent $k\in\mathcal{A}$ such that
$v(\pi^{*}_{k})<\mu$. Let $j\in\mathcal{G}$ be a good assigned to $i$. By
reassigning $j$ to agent $k$, we get a new allocation $\pi^{\prime}$ from
$\pi^{*}$. Then, we obtain

$\displaystyle
v(\pi^{\prime}_{i})v(\pi^{\prime}_{k})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=(v(\pi^{*}_{i})-v_{j})(v(\pi^{*}_{k})+v_{j})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=v_{j}(v(\pi^{*}_{i})-v(\pi^{*}_{k})-v_{j})$
$\displaystyle>v_{j}(v(\pi^{*}_{i})-\mu-v_{\max})$ $\displaystyle\geq 0.$

This shows that $f(\pi^{\prime})>f(\pi^{*})$, which contradicts the optimality
of $\pi^{*}$.

Assume that there is some agent $i\in\mathcal{A}$ with $v(\pi^{*}_{i})\leq\mu-
v_{\max}$. This implies that $v(\pi^{*}_{i})<\mu$, and so there must be at
least one agent $k\in\mathcal{A}$ such that $v(\pi^{*}_{k})>\mu$. Let
$j\in\mathcal{G}$ be a good assigned to $k$. Then, it holds that

$v_{j}+v(\pi^{*}_{i})\leq v_{\max}+v(\pi^{*}_{i})\leq\mu<v(\pi^{*}_{k}).$

By reassigning $j$ to agent $i$, we get a new allocation $\pi^{\prime}$ from
$\pi^{*}$. Then, we obtain

$\displaystyle
v(\pi^{\prime}_{i})v(\pi^{\prime}_{k})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=(v(\pi^{*}_{i})+v_{j})(v(\pi^{*}_{k})-v_{j})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=v_{j}(v(\pi^{*}_{k})-v(\pi^{*}_{i})-v_{j})$ $\displaystyle>0.$

This shows that $f(\pi^{\prime})>f(\pi^{*})$, which contradicts the optimality
of $\pi^{*}$. ∎

We are now ready to describe our algorithm. Suppose we are given an instance
$I=(\mathcal{A},\mathcal{G},\mathbf{v})$ with $v_{\max}<\mu$. To simplify the
description, suppose that $1/{\varepsilon}$ is an integer.

Our idea is to guess $v(\pi^{*}_{i})$ with an additive error
${\varepsilon}v_{\max}$ for each $i\in\mathcal{A}$, where $\pi^{*}$ is an
optimal solution. By Lemma 5, we already know that the value of an optimal
solution is in the interval of width $2v_{\max}$. Let $L$ be the set of points
delimiting this interval with width ${\varepsilon}v_{\max}$, that is,

$L=\\{\mu-v_{\max}+i{\varepsilon}v_{\max}\mid
i\in\\{0,1,2,\dots,2/{\varepsilon}-1\\}\\}.$

Let $L^{\mathcal{A}}$ be the set of all the maps from $\mathcal{A}$ to $L$.
For $\tau,\tau^{\prime}\in L^{\mathcal{A}}$, we denote $\tau\sim\tau^{\prime}$
if $\tau^{\prime}$ is obtained from $\tau$ by changing the roles of the
agents, or equivalently
$|\\{i\in\mathcal{A}\mid\tau(i)=x\\}|=|\\{i\in\mathcal{A}\mid\tau^{\prime}(i)=x\\}|$
for each $x\in L$. In such a case, since each agent is identical, we can
identify $\tau$ and $\tau^{\prime}$. This motivates us to define
$D:=L^{\mathcal{A}}/\sim$, where $\sim$ is the equivalence relation defined as
above.

For each $\tau\in D$, we apply LoadBalancing in Theorem 3 to the following
instance of the target load balancing problem: $\mathcal{M}:=\mathcal{A}$,
$\mathcal{J}:=\mathcal{G}$, the processing time of $j\in\mathcal{J}$ is
$v_{j}$, and the target interval is $[\tau(i),\tau(i)+{\varepsilon}v_{\max}]$
for each $i\in\mathcal{M}$. Then, LoadBalancing either concludes that no
solution exists or returns an assignment (allocation) $\pi^{\tau}$ such that
$v(\pi^{\tau}_{i})\in[\tau(i)-{\varepsilon}v_{\max},\tau(i)+2{\varepsilon}v_{\max}]$
for each $i\in\mathcal{M}$.

Among all solutions $\pi^{\tau}$ returned by LoadBalancing, our algorithm
chooses an allocation with the largest objective function value. A pseudocode
of our algorithm is shown in Algorithm 2.

Algorithm 2 MainProcedure

1:instance $I=(\mathcal{A},\mathcal{G},\mathbf{v})$ such that $v_{\max}<\mu$

2:allocation $\pi$

3:Initialize $\pi$ as an arbitrary allocation.

4:for $\tau\in D$ do

5: Apply LoadBalancing with the target interval
$[\tau(i),\tau(i)+{\varepsilon}v_{\max}]$ for $i\in\mathcal{A}$.

6: if LoadBalancing returns an allocation $\pi^{\tau}$ then

7: if $f(\pi)<f(\pi^{\tau})$ then

8: $\pi\leftarrow\pi^{\tau}$

9:return $\pi$

######  Proposition 6.

The running time of MainProcedure is
$(nm/{\varepsilon})^{O(1/{\varepsilon})}$.

###### Proof.

To obtain an upper bound on the number of for loop iterations, we estimate the
number of elements in $D$. Since each $\tau\in D$ is determined by the number
of agents $i\in\mathcal{A}$ such that $\tau(i)=x$ for $x\in L$, we obtain
$|D|\leq|\\{0,1,\dots,n\\}|^{L}\leq(n+1)^{2/{\varepsilon}}=n^{O(1/{\varepsilon})}$.

We next estimate the running time of LoadBalancing. Since $|\mathcal{M}|=n$,
$|\mathcal{J}|=m$, and the number of machine types $K$ is at most
$|L|=2/{\varepsilon}$, the running time of LoadBalancing is
$n^{2/{\varepsilon}+1}(m/{\varepsilon})^{O(1/{\varepsilon})}$ by Theorem 3.

Thus, the total running time of MainProcedure is
$(nm/{\varepsilon})^{O(1/{\varepsilon})}$. ∎

The entire algorithm for Identical Additive NSW consists of the following
steps: apply Preprocessing, apply MainProcedure, and recover the removed sets.
A pseudocode of the entire algorithm is shown in Algorithm 3.

Algorithm 3 MaxNashWelfare

1:instance $I=(\mathcal{A},\mathcal{G},\mathbf{v})$

2:allocation $\pi^{\prime}$

3:Apply Preprocessing to $I$ and obtain $\mathcal{A}_{0}$ and
$\mathcal{G}_{0}$.

4:Apply MainProcedure to $I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$ and
obtain $\pi$.

5:Let ${\sigma}$ be a bijection from $\mathcal{A}_{0}$ to $\mathcal{G}_{0}$.

6:Set $\pi^{\prime}_{i}=\\{{\sigma}(i)\\}$ for $i\in\mathcal{A}_{0}$ and set
$\pi^{\prime}_{i}=\pi_{i}$ for $i\in\mathcal{A}\setminus\mathcal{A}_{0}$.

7:return $\pi^{\prime}$

Since the most time consuming part is MainProcedure, the running time of
MaxNashWelfare is $(nm/{\varepsilon})^{O(1/{\varepsilon})}$ by Proposition 6.

##  3 Analysis of Approximation Performance

In this section, we show that MaxNashWelfare returns a good approximate
solution for Identical Additive NSW and give a proof of Theorem 1. We first
analyze the performance of MainProcedure in Section 3.1, and then analyze the
effect of Preprocessing in Section 3.2.

###  3.1 Approximation Performance of MainProcedure

In this subsection, we consider an instance
$I=(\mathcal{A},\mathcal{G},\mathbf{v})$ of Identical Additive NSW such that
$v_{\max}<\mu$. The following lemma is easy, but useful in our analysis of
MainProcedure.

######  Lemma 7.

Assume that $v_{\max}<\mu$. Let $\pi$ be the allocation returned by
MainProcedure. For any optimal solution $\pi^{*}$, there exists an allocation
$\pi^{\tau}$ such that

  * •

$\left\lvert v(\pi^{\tau}_{i})-v(\pi^{*}_{i})\right\rvert\leq
2{\varepsilon}v_{\max}$ for each $i\in\mathcal{A}$, and

  * •

$f(\pi^{\tau})\leq f(\pi)$.

###### Proof.

Let $\pi^{*}$ be a given optimal solution. Take $\tau^{*}\in L^{\mathcal{A}}$
so that the valuation $v(\pi^{*}_{i})$ is in the interval
$[\tau^{*}(i),\tau^{*}(i)+{\varepsilon}v_{\max}]$ for each $i\in\mathcal{A}$.
Note that such $\tau^{*}$ always exists by Lemma 5. Since we apply
LoadBalancing with $l_{i}=\tau(i)$ and $u_{i}=\tau(i)+{\varepsilon}v_{\max}$
in MainProcedure for some $\tau$ with $\tau\sim\tau^{*}$, we obtain an
allocation $\pi^{\tau}$ that corresponds to $\tau$. Then, the inequality
$\left\lvert v(\pi^{\tau}_{i})-v(\pi^{*}_{i})\right\rvert\leq
2{\varepsilon}v_{\max}$ holds by reordering the agents appropriately. By the
choice of $\pi$ in MainProcedure, the inequality $f(\pi^{\tau})\leq f(\pi)$
holds. ∎

In preparation for the analysis, we show another bound on the valuation of an
agent in an optimal solution. Note that a similar result is shown by Alon et
al. [1] for a different problem, and our proof for the following lemma is
based on their argument.

######  Lemma 8.

Assume that $v_{\max}<\mu$. Let $\pi^{*}$ be an optimal allocation of goods.
Then,

$\frac{\mu}{2}<v(\pi^{*}_{i})<2\mu$

holds for any $i\in\mathcal{A}$.

###### Proof.

The upper bound is obvious because $v(\pi^{*}_{i})<\mu+v_{\max}<2\mu$ by Lemma
5. Assume that there is some agent $i\in\mathcal{A}$ with
$v(\pi^{*}_{i})\leq\mu/2$. This implies that $v(\pi^{*}_{i})<\mu$, and so
there must be at least one agent $k$ such that $v(\pi^{*}_{k})>\mu$. We treat
the following cases separately.

Assume that there is a good $j\in\pi^{*}_{k}$ that satisfies
$v_{j}<v(\pi^{*}_{k})-v(\pi^{*}_{i})$. We get a new allocation $\pi^{\prime}$
from $\pi^{*}$ by reassigning $j$ to $i$. Then, we obtain

$\displaystyle
v(\pi^{\prime}_{i})v(\pi^{\prime}_{k})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=(v(\pi^{*}_{i})+v_{j})(v(\pi^{*}_{k})-v_{j})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=v_{j}(v(\pi^{*}_{k})-v(\pi^{*}_{i})-v_{j})$ $\displaystyle>0,$

which contradicts the optimality of $\pi^{*}$.

Assume that for all $j\in\pi^{*}_{k}$ the inequality $v_{j}\geq
v(\pi^{*}_{k})-v(\pi^{*}_{i})$ holds. This implies that
$v_{j}>\mu-\mu/2=\mu/2\geq v(\pi^{*}_{i})$. We also see that $v_{j}\leq
v_{\max}<\mu<v(\pi^{*}_{k})$. We get a new allocation $\pi^{\prime}$ from
$\pi^{*}$ by reassigning whole $\pi^{*}_{i}$ to agent $k$, and a single good
$j\in\pi^{*}_{k}$ to agent $i$. Then, we obtain

$\displaystyle
v(\pi^{\prime}_{i})v(\pi^{\prime}_{k})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=v_{j}(v(\pi^{*}_{k})+v(\pi^{*}_{i})-v_{j})-v(\pi^{*}_{i})v(\pi^{*}_{k})$
$\displaystyle=(v_{j}-v(\pi^{*}_{i}))(v(\pi^{*}_{k})-v_{j})$
$\displaystyle>0,$

which contradicts the optimality of $\pi^{*}$. ∎

We are now ready to evaluate the performance of MainProcedure.

######  Lemma 9.

Assume that $v_{\max}<\mu$ and $0<{\varepsilon}\leq 1/5$. Let $\pi$ be the
allocation returned by MainProcedure and let $\mathrm{OPT}$ be the optimal
value. Then, it holds that

$f(\pi)\geq\mathrm{OPT}-48{\varepsilon}v_{\max}.$

###### Proof.

By Lemma 7, there exist an allocation $\pi^{\tau}$ and an optimal solution
$\pi^{*}$ such that

$\left\lvert v(\pi^{\tau}_{i})-v(\pi^{*}_{i})\right\rvert\leq
2{\varepsilon}v_{\max},$ (1)

and $f(\pi^{\tau})\leq f(\pi)$. Let $S=f(\pi^{\tau})$. Since $S\leq f(\pi)$,
in order to obtain $f(\pi)\geq\mathrm{OPT}-48{\varepsilon}v_{\max}$, it
suffices to show that $\mathrm{OPT}-S\leq 48{\varepsilon}v_{\max}$.

We first evaluate the ratio between $\mathrm{OPT}$ and $S$ as follows:

$\displaystyle\frac{\mathrm{OPT}}{S}$
$\displaystyle=\left(\prod_{i\in\mathcal{A}}\frac{v(\pi^{*}_{i})}{v(\pi_{i}^{\tau})}\right)^{1/n}$
$\displaystyle\leq\frac{1}{n}\sum_{i}\frac{v(\pi^{*}_{i})}{v(\pi_{i}^{\tau})}$
(by AM-GM inequality)
$\displaystyle\leq\frac{1}{n}\sum_{i}\left(1+\frac{2{\varepsilon}v_{\max}}{v(\pi_{i}^{\tau})}\right)$
(by (1))
$\displaystyle=1+\frac{2{\varepsilon}v_{\max}}{n}\sum_{i}\frac{1}{v(\pi_{i}^{\tau})},$
(2)

where we use the inequality of arithmetic and geometric means (AM-GM
inequality) in the first inequality. By using (3.1), the difference between
$\mathrm{OPT}$ and $S$ can be evaluated as follows:

$\displaystyle\mathrm{OPT}-S$
$\displaystyle=S\left(\frac{\mathrm{OPT}}{S}-1\right)$ $\displaystyle\leq
2{\varepsilon}v_{\max}\left(\frac{1}{n}\sum_{i}\frac{S}{v(\pi_{i}^{\tau})}\right)$
(by (3.1)) $\displaystyle=2{\varepsilon}v_{\max}\left(\frac{S}{H}\right),$ (3)

where we define $1/H=\frac{1}{n}\sum_{i}1/v(\pi_{i}^{\tau})$, that is, $H$ is
the harmonic mean of $v(\pi_{i}^{\tau})$. Therefore, to obtain an upper bound
on $\mathrm{OPT}-S$, it suffices to give upper bounds on $S$ and $1/H$.

We obtain an upper bound on $S$ as follows:

$\displaystyle S$
$\displaystyle=\left(\prod_{i}v(\pi_{i}^{\tau})\right)^{1/n}$
$\displaystyle\leq\left(\prod_{i}(v(\pi^{*}_{i})+2{\varepsilon}v_{\max})\right)^{1/n}$
(by (1))
$\displaystyle\leq\left(\prod_{i}(2\mu+2{\varepsilon}\mu)\right)^{1/n}$ (by
Lemma 8 and $v_{\max}<\mu$) $\displaystyle=2\mu(1+{\varepsilon}).$ (4)

Similarly, we obtain an upper bound on $1/H$ as follows:

$\displaystyle\frac{1}{H}$
$\displaystyle=\frac{1}{n}\sum_{i}\frac{1}{v(\pi_{i}^{\tau})}$
$\displaystyle\leq\frac{1}{n}\sum_{i}\frac{1}{v(\pi^{*}_{i})-2{\varepsilon}v_{\max}}$
(by (1))
$\displaystyle\leq\frac{1}{n}\sum_{i}\frac{1}{\mu/2-2{\varepsilon}\mu}$ (by
Lemma 8 and $v_{\max}<\mu$) $\displaystyle=\frac{2}{\mu(1-4{\varepsilon})},$
(5)

where we note that
$v(\pi^{*}_{i})-2{\varepsilon}v_{\max}\geq\mu/2-2{\varepsilon}\mu>0$ if
${\varepsilon}\leq 1/5$.

Therefore, for ${\varepsilon}\leq 1/5$, we obtain

$\frac{S}{H}\leq\frac{4(1+{\varepsilon})}{1-4{\varepsilon}}\leq 24$ (6)

by (3.1) and (3.1). Hence, it holds that $\mathrm{OPT}-S\leq
48{\varepsilon}v_{\max}$ by (3.1) and (6), which completes the proof. ∎

This lemma shows that MainProcedure is an additive PTAS for Identical Additive
NSW under the assumption that $v_{\max}<\mu$.

It is worth noting that MainProcedure is not only an additive PTAS, but also a
PTAS in the conventional sense.

######  Lemma 10.

Assume that $v_{\max}<\mu$ and $0<{\varepsilon}\leq 1/5$. Let $\pi$ be the
allocation returned by MainProcedure and let $\mathrm{OPT}$ be the optimal
value. Then, it holds that

$f(\pi)\geq\frac{\mathrm{OPT}}{1+20{\varepsilon}}.$

###### Proof.

Let $S=f(\pi^{\tau})$ be the value as in the proof of Lemma 9. According to
inequalities (3.1) and (3.1), we obtain

$\displaystyle\frac{\mathrm{OPT}}{S}$ $\displaystyle\leq
1+\frac{2{\varepsilon}v_{\max}}{H}$ (by (3.1)) $\displaystyle\leq
1+\frac{4{\varepsilon}v_{\max}}{\mu(1-4{\varepsilon})}$ (by (3.1))
$\displaystyle\leq 1+\frac{4{\varepsilon}}{1-4{\varepsilon}}$ (by
$v_{\max}<\mu$) $\displaystyle\leq 1+20{\varepsilon}.$ (by
$0<{\varepsilon}\leq 1/5$)

Since $f(\pi)\geq S$, this shows that
$f(\pi)\geq\mathrm{OPT}/(1+20{\varepsilon})$. ∎

###  3.2 Approximation Performance of MaxNashWelfare

We have already seen in the previous subsection that MainProcedure is a PTAS
and an additive PTAS for Identical Additive NSW under the assumption that
$v_{\max}<\mu$. In this subsection, we analyze the effect of Preprocessing and
show that MaxNashWelfare is a PTAS and an additive PTAS. As a warm-up, we
first show that MaxNashWelfare is a PTAS in the conventional sense.

######  Proposition 11.

Let $I=(\mathcal{A},\mathcal{G},\mathbf{v})$ be an instance of Identical
Additive NSW and suppose that $0<{\varepsilon}\leq 1/5$. Let $\pi$ be the
allocation returned by MaxNashWelfare and let $\mathrm{OPT}$ be the optimal
value. Then, it holds that

$f(\pi)\geq\frac{\mathrm{OPT}}{1+20{\varepsilon}}.$

###### Proof.

Let $\pi^{*}$ be an optimal allocation. Let $\mathcal{A}_{0}$ and
$\mathcal{G}_{0}$ be the set of agents and goods removed in Preprocessing
respectively. Set $I^{\prime}=I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$. In
an optimal solution $\pi^{*}$, for each good $j\in\mathcal{G}_{0}$ there
exists an agent $i$ that satisfies $\pi^{*}_{i}=\\{j\\}$ by Lemma 4. By
rearranging the agents and the goods appropriately, we can assume that
$\pi^{*}_{i}=\pi_{i}$ for each $i\in\mathcal{A}_{0}$. Then the following
holds:

$\frac{\mathrm{OPT}}{f(\pi)}=\left(\prod_{i\in\mathcal{A}}\frac{v(\pi^{*}_{i})}{v(\pi_{i})}\right)^{1/n}=\left(\prod_{i\in\mathcal{A}\setminus\mathcal{A}_{0}}\frac{v(\pi^{*}_{i})}{v(\pi_{i})}\right)^{1/n}.$

Let $A(I^{\prime})$ be the objective function value of the solution returned
by MainProcedure for instance $I^{\prime}$, and let $\mathrm{OPT}(I^{\prime})$
be the optimal value of instance $I^{\prime}$. Set $k=|\mathcal{A}_{0}|$.
Then, we obtain

$\left(\prod_{i\in\mathcal{A}\setminus\mathcal{A}_{0}}\frac{v(\pi^{*}_{i})}{v(\pi_{i})}\right)^{1/n}=\left(\frac{\mathrm{OPT}(I^{\prime})}{A(I^{\prime})}\right)^{(n-k)/n}\leq(1+20{\varepsilon})^{(n-k)/n}\leq
1+20{\varepsilon}$

by Lemma 10, which completes the proof. ∎

The proof of Proposition 11 is easy, because the multiplicative error is not
amplified when we recover the agents and goods removed in Preprocessing, that
is, ${\mathrm{OPT}}/{f(\pi)}\leq{\mathrm{OPT}(I^{\prime})}/{A(I^{\prime})}$.
However, this property does not hold when we consider the additive error,
which makes the situation harder. Nevertheless, we show that the additive
error of $f(\pi)$ is bounded by $O({\varepsilon}v_{\max})$ with the aid of the
mean-value theorem for differentiable functions.

######  Proposition 12.

Let $I=(\mathcal{A},\mathcal{G},\mathbf{v})$ be an instance of Identical
Additive NSW and suppose that $0<{\varepsilon}\leq 1/192$. Let $\pi$ be the
allocation returned by MaxNashWelfare and let $\mathrm{OPT}$ be the optimal
value. Then, it holds that

$f(\pi)\geq\mathrm{OPT}-192{\varepsilon}v_{\max}.$

###### Proof.

Let $A=f(\pi)$ and let $\pi^{*}$ be an optimal allocation. Let
$\mathcal{A}_{0}$ and $\mathcal{G}_{0}$ be the set of agents and goods removed
in Preprocessing, respectively. Set $k=|\mathcal{A}_{0}|$. In an optimal
solution $\pi^{*}$, for each good $j\in\mathcal{G}_{0}$ there exists an agent
$i$ that satisfies $\pi^{*}_{i}=\\{j\\}$ by Lemma 4. By rearranging the agents
and the goods appropriately, we can assume that $\pi^{*}_{i}=\pi_{i}$ for each
$i\in\mathcal{A}_{0}$. Set
$I^{\prime}=I\setminus(\mathcal{A}_{0},\mathcal{G}_{0})$. Let $A(I^{\prime})$
be the objective function value of the solution returned by MainProcedure for
instance $I^{\prime}$, and let $\mathrm{OPT}(I^{\prime})$ be the optimal value
of instance $I^{\prime}$.

We define a function $g\colon{\mathbb{R}}\to{\mathbb{R}}$ as

$g(x)=\left(\prod_{j\in\mathcal{G}_{0}}v_{j}\right)^{1/n}x^{(n-k)/n}.$

By using $g$, the expression to be evaluated can be written as follows:

$\displaystyle\mathrm{OPT}-A=g(\mathrm{OPT}(I^{\prime}))-g(A(I^{\prime})).$
(7)

Since $g$ is differentiable, by the mean value theorem, there exists a real
number $c$ such that

$\displaystyle A(I^{\prime})\leq c\leq\mathrm{OPT}(I^{\prime}),$ (8)
$\displaystyle
g(\mathrm{OPT}(I^{\prime}))-g(A(I^{\prime}))=(\mathrm{OPT}(I^{\prime})-A(I^{\prime}))g^{\prime}(c).$
(9)

By (7), (9), and Lemma 9, we obtain

$\displaystyle\mathrm{OPT}-A\leq
48{\varepsilon}v_{\max}(I^{\prime})g^{\prime}(c),$ (10)

where
$v_{\max}(I^{\prime})=\max_{j\in\mathcal{G}\setminus\mathcal{G}_{0}}v_{j}$.
Therefore, all we need to do is to evaluate $g^{\prime}(c)$.

For this purpose, we first give a lower bound on $c$ as follows:

$\displaystyle c$ $\displaystyle\geq A(I^{\prime})$ $\displaystyle(\text{by
(\ref{eq:07})})$
$\displaystyle\geq\mathrm{OPT}(I^{\prime})-48{\varepsilon}v_{\max}(I^{\prime})$
(by Lemma 9)
$\displaystyle=\left(\prod_{i\in\mathcal{A}\setminus\mathcal{A}_{0}}v(\pi^{*}_{i})\right)^{1/(n-k)}-48{\varepsilon}v_{\max}(I^{\prime})$
$\displaystyle\geq\left(\prod_{i\in\mathcal{A}\setminus\mathcal{A}_{0}}\frac{\mu(I^{\prime})}{2}\right)^{1/(n-k)}-48{\varepsilon}v_{\max}(I^{\prime})$
(by Lemma 8)
$\displaystyle\geq\frac{\mu(I^{\prime})}{2}-48{\varepsilon}v_{\max}(I^{\prime})$
(by $|\mathcal{A}\setminus\mathcal{A}_{0}|=n-k$)
$\displaystyle\geq\left(\frac{1}{2}-48{\varepsilon}\right)v_{\max}(I^{\prime}).$
(by $\mu(I^{\prime})>v_{\max}(I^{\prime})$) (11)

By using this inequality, we obtain the following upper bound on
$g^{\prime}(c)$:

$\displaystyle g^{\prime}(c)$
$\displaystyle=\frac{n-k}{n}\left(\prod_{j\in\mathcal{G}_{0}}v_{j}\right)^{1/n}\left(\frac{1}{c}\right)^{k/n}$
$\displaystyle\leq\left(\frac{v_{\max}}{c}\right)^{k/n}$ (by
$|\mathcal{G}_{0}|=k$ and $v_{j}\leq v_{\max}$)
$\displaystyle\leq\left(\frac{v_{\max}}{(1/2-48{\varepsilon})v_{\max}(I^{\prime})}\right)^{k/n}$
(by (11))
$\displaystyle\leq\left(\frac{4v_{\max}}{v_{\max}(I^{\prime})}\right)^{k/n}$
(by $0<{\varepsilon}\leq 1/192$)
$\displaystyle\leq\frac{4v_{\max}}{v_{\max}(I^{\prime})}.$ (by $v_{\max}\geq
v_{\max}(I^{\prime})$) (12)

Hence, we obtain $\mathrm{OPT}-A\leq 192{\varepsilon}v_{\max}$ from (10) and
(3.2), which completes the proof. ∎

By setting ${\varepsilon}$ appropriately, Theorem 1 follows from Proposition
12.

###### Proof of Theorem 1.

Suppose that we are given an instance of Identical Additive NSW and a real
value ${\varepsilon}>0$. Define ${\varepsilon}^{\prime}$ as the largest value
subject to $1/{\varepsilon}^{\prime}$ is an integer and
${\varepsilon}^{\prime}\leq\min(1/192,\ {\varepsilon}/192)$. That is,
${\varepsilon}^{\prime}:=1/\lceil\max(192,192/{\varepsilon})\rceil$. Then,
apply MaxNashWelfare in which ${\varepsilon}$ is replaced with
${\varepsilon}^{\prime}$. Since $0<{\varepsilon}^{\prime}\leq 1/192$,
MaxNashWelfare returns an allocation $\pi$ such that
$f(\pi)\geq\mathrm{OPT}-192{\varepsilon}^{\prime}v_{\max}\geq\mathrm{OPT}-{\varepsilon}v_{\max}$
by Proposition 12. As described in Section 2, the running time of
MaxNashWelfare is $(nm/{\varepsilon}^{\prime})^{O(1/{\varepsilon}^{\prime})}$,
which can be rewritten as $(nm/{\varepsilon})^{O(1/{\varepsilon})}$. This
completes the proof of Theorem 1. ∎

## References

  * [1] Noga Alon, Yossi Azar, Gerhard J Woeginger, and Tal Yadid.  Approximation schemes for scheduling on parallel machines.  Journal of Scheduling, 1(1):55–66, 1998.
  * [2] Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V. Vazirani.  Nash social welfare for indivisible items under separable, piecewise-linear concave utilities.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2274–2290, 2018.
  * [3] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Finding fair and efficient allocations.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557–574, 2018.
  * [4] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish.  Greedy algorithms for maximizing Nash social welfare.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 7–13, 2018.
  * [5] Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese.  Additive approximation schemes for load balancing problems.  arXiv preprint arXiv:2007.09333, 2020.
  * [6] Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, and Andreas Wiese.  Additive approximation schemes for load balancing problems.  In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 42:1–42:17, 2021.
  * [7] Peter S Bullen.  Handbook of means and their inequalities, volume 560.  Springer Science & Business Media, 2013.
  * [8] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang.  The unreasonable fairness of maximum Nash welfare.  ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019.
  * [9] Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn.  On fair division for indivisible items.  In Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), pages 25:1–25:17, 2018.
  * [10] Edmund Eisenberg and David Gale.  Consensus of subjective probabilities: The pari-mutuel method.  The Annals of Mathematical Statistics, 30(1):165–168, 1959.
  * [11] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.  Approximating the Nash social welfare with budget-additive valuations.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2326–2340, 2018.
  * [12] Jugal Garg, Edin Husić, and László A. Végh.  Approximating Nash social welfare under Rado valuations.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), pages 1412–1425, 2021.
  * [13] Oscar H Ibarra and Chul E Kim.  Fast approximation algorithms for the knapsack and sum of subset problems.  Journal of the ACM, 22(4):463–468, 1975.
  * [14] Mamoru Kaneko and Kenjiro Nakamura.  The Nash social welfare function.  Econometrica, 47(2):423–435, 1979.
  * [15] Frank Kelly.  Charging and rate control for elastic traffic.  European Transactions on Telecommunications, 8(1):33–37, 1997.
  * [16] Euiwoong Lee.  APX-hardness of maximizing Nash social welfare with indivisible items.  Information Processing Letters, 122:17–20, 2017.
  * [17] Wenzheng Li and Jan Vondrák.  A constant-factor approximation algorithm for Nash social welfare with submodular valuations.  arXiv preprint arXiv:2103.10536, 2021.
  * [18] Wenzheng Li and Jan Vondrák.  Estimating the Nash social welfare for coverage and other submodular valuations.  In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1119–1130, 2021.
  * [19] Hervé Moulin.  Fair division and collective welfare.  MIT press, 2003.
  * [20] John F Nash.  The bargaining problem.  Econometrica, 18(2):155–162, 1950.
  * [21] Trung Thanh Nguyen and Jörg Rothe.  Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods.  Discrete Applied Mathematics, 179:54–68, 2014.
  * [22] Hal R Varian.  Equity, envy, and efficiency.  Journal of Economic Theory, 9(1):63–91, 1974.