A Note on Approximating Weighted Nash Social Welfare with Additive Valuations ¹¹1The preliminary version of the paper appeared in the Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024).

In this note, we give the first $O(1)$-approximation algorithm for the weighted Nash Social Welfare problem with additive valuations:

Our approximation ratio of $e^{1/e}+\epsilon$ matches the best ratio for the unweighted case due to Barman et al. [3]. In contrast, the ratio given by Brown et al. [6] is $5\cdot\exp(2\cdot D_{\text{KL}}(w||\frac{\vec{1}}{n}))$, which could be polynomial in $n$.

Our algorithm is based on a natural configuration LP for the problem, which has not been studied before to the best of our knowledge. The configuration LP contains a $y_{i,S}$ variable for every agent $i$ and subset $S$ of items, indicating if the set of items $i$ gets is $S$ or not. We show that the configuration LP can be solved in polynomial time to any precision, despite having exponential number of variables. Once we obtain the LP solution, we define $x_{ij}$ for every $i\in{\mathcal{A}}$ and $j\in{\mathcal{G}}$ to be the fraction of $j$ assigned to $i$.

We use a randomized version of the Shmoys-Tardos rounding algorithm [30] developed for unrelated machine scheduling problems, to round $x$ into an integral solution. For every agent $i$, we break the fractional items assigned to $i$ into groups from the most valuable to the least, each containing 1 fractional item. The rounding algorithm maintains marginal probabilities, and the requirement that $i$ gets exactly one item from each group (except for the last one, from which $i$ gets at most one item). In the analysis for each agent $i$, we construct an instance of the unweighted Nash Social Welfare problem with identical additive valuations, that involves many copies of the agent $i$, along with two alloations ${\mathcal{S}}$ and ${\mathcal{S}}^{\prime}$ to the instance. ${\mathcal{S}}$ corresponds to the LP solution, and ${\mathcal{S}}^{\prime}$ corresponds to the randomized solution given by the rounding algorithm. Thanks to the condition that every group contains one item, the solution ${\mathcal{S}}^{\prime}$ is envy-free up to one item (EF1). Using the result of [3] about EF1 allocations, we show that the Nash social welfare of ${\mathcal{S}}^{\prime}$ is at least $e^{-1/e}$ times that of ${\mathcal{S}}$, which eventually leads to our $(e^{1/e}+\epsilon)$-approximation.

We believe the configuration LP could be used in many other settings. We leave as an immediate open problem whether it can give an $O(1)$-approximation for the weighted Nash Social Welfare problem with submodular valuations.

For convenience, for any value function $v:{\mathcal{G}}\to{\mathbb{R}}_{\geq 0}$, we define $v(S):=\sum_{j\in S}v_{j}$ for every $S\subseteq{\mathcal{G}}$ to be the total value of items in $S$ according to the value funciton $v$. In the integer program correspondent to the configuration LP, for every $i\in\cal A$ and $S\subseteq{\mathcal{G}}$, we have a variable $y_{i,S}\in\{0,1\}$ indicating if the set of items assigned to $i$ is $S$ or not. We relax the integer constraint to obtain the following configuration LP:

It is convenient for us to consider the natural logarithm of the Nash social welfare function as the objective, which is $\sum_{i\in{\mathcal{A}}}w_{i}\cdot\ln v_{i}(\sigma^{-1}(i))$. This leads to the objective in (Conf-LP). (1) requires that every item $j$ is assigned to at most one agent, and (2) requires that every agent $i$ is assigned one set of items.

The configuration LP has exponential number of variables, but it can be solved within an additive error of $\ln(1+\epsilon)$ for any $\epsilon>0$, in time polynomial in the size of the instance and $\frac{1}{\epsilon}$. We defer the details to Appendix A. Notice that we are considering the logarithm of Nash social welfare, and the typical $(1+\epsilon)$-multiplicative factor becomes an additive error of $\ln(1+\epsilon)$.

From now on, we assume we have obtained a vector $y$ from solving the LP, described using a list of non-zero coordinates; the value of $y$ to (Conf-LP) is at least the optimum value minus $\ln(1+\epsilon)$. We can assume (1) holds with equalities: $\sum_{i\in{\mathcal{A}},S\ni j}y_{i,S}=1$ for every $j\in{\mathcal{G}}$. Then we let $x_{ij}=\sum_{S\ni j}y_{i,S}$ for every $i\in{\mathcal{A}}$ and $j\in{\mathcal{G}}$. So $\sum_{i\in{\mathcal{A}}}x_{ij}=1$ for every $j\in{\mathcal{G}}$.

In this paragraph, we fix an agent $i$ and break the fractional items assigned to $i$ into a set $G_{i}$ of groups, each containing 1 fractional item. They are created in non-increasing order of values, as in the Shmoys-Tardos algorithm for unrelated machine scheduling problems. That is, the first group contains the 1 fractional most valuable items assigned to $i$, the second group contains the 1 fractional most valuable items assigned to $i$ after removing the first group, and so on. Formally, we sort the items in ${\mathcal{G}}$ in non-increasing order of $v_{ij}$ values, breaking ties arbitrarily. Let $p_{i}={\lceil\sum_{j\in{\mathcal{G}}}x_{ij}\rceil}$. Then we can find vectors $g^{1},g^{2},\cdots,g^{p_{i}}\in[0,1]^{{\mathcal{G}}}$ satisfying the following properties:

1. (P1)

   For every $t\in[1,p_{i}-1]$, we have $|g^{t}|_{1}=1$; for $t=p_{i}$, we have $|g^{t}|_{1}=\sum_{j\in{\mathcal{G}}}x_{ij}-(p_{i}-1)\in(0,1]$.

2. (P2)

   $\sum_{t=1}^{p_{i}}g^{t}_{j}=x_{ij}$ for every $j\in{\mathcal{G}}$.

3. (P3)

   For every $1\leq t<t^{\prime}\leq p_{i}$, and two items $j,j^{\prime}$ such that $j$ appears before $j^{\prime}$ in the ordering, it can not happen that $g^{t}_{j^{\prime}}>0$ and $g^{t^{\prime}}_{j}>0$.

It is easy to see that $g^{1},g^{2},\cdots,g^{p_{i}}$ are uniquely decided by the three conditions. We say each $g^{t}$ is a group. Let $G_{i}=\{g^{1},g^{2},\cdots,g^{p_{i}}\}$ be the set of all groups constructed for this agent $i$.

Now we take all agents $i$ into consideration and let $G=\uplus_{i\in{\mathcal{A}}}G_{i}$ be the set of all groups constructed.²²2It is possible that two groups from different sets $G_{i}$ and $G_{i^{\prime}}$ have the same vector representation. So we treat $G$ as a multiset and we assume we know which set $G_{i}$ each group $g\in G$ belongs to. The representations of groups give a fractional matching between the groups $G$ and items ${\mathcal{G}}$: an item $j$ is matched to a group $g\in[0,1]^{{\mathcal{G}}}$ with a fraction of $g_{j}$. Then each item is matched to an extent of 1, and every group $g$ is matched to an extent of $|g|_{1}$. So a group is matched to an extent of 1 if it is not the last group for an agent, and at most 1 otherwise. Therefore, we can efficiently output a randomized (partial-)matching between the groups $G$ and items ${\mathcal{G}}$ so that the marginal probabilities are maintained:

1. ($\star$)

   For every group $g\in G$ and item $j\in{\mathcal{G}}$, we have $\Pr[j\text{ is matched to }g]=g_{j}$.

($\star$) implies that an item $j\in{\mathcal{G}}$ is matched with probability 1. If a group $g$ has $|g|_{1}=1$, then it is matched with probability 1.

The matching naturally gives us an allocation of items to agents: If an item $j\in{\mathcal{G}}$ is matched to some group $g\in G_{i}$, then we assign $j$ to $i$. By ($\star$) we know that the probability that $j$ is assigned to $i$ is precisely $x_{ij}$. Let $S_{i}$ be the set of items assigned to $i$ in the algorithm; notice that it is random. This finishes the description of the randomized rounding algorithm.

To analyze our rounding algorithm, we first formally define an EF1 allocation.

We use the following result from [3]:

With the theorem, we prove the following key lemma:

Applying the lemma for every $i\in{\mathcal{A}}$ and using linearity of expectation, we have

We used that $\sum_{i\in{\mathcal{A}}}w_{i}=1$.

By the convexity of exponential function, we have

where opt is the Nash Social Welfare of the optimum allocation, and the second inequality used that the value of our solution $y$ to (Conf-LP) is at least its optimum value minus $\ln(1+\epsilon)$. By scaling $\epsilon$ down by an absolute constant at the beginning, we can make the right side to be at least $\frac{\text{opt}}{e^{1/e}+\epsilon}$. This finishes the proof of Theorem 1.1.

It is easy to derandomize our algorithm, as we only need the constructed random matching between the groups $G$ and the items ${\mathcal{G}}$ to satisfy marginal probabilities. Therefore, we can decompose the fractional matching into a convex combination of polynomial number of matchings, and output the best matching in the combination.