A constant factor approximation for Nash social welfare with subadditive valuations

Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák Weizmann Institute of ScienceStanford UniversityStanford UniversityStanford University

Abstract

We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a template for NSW optimization by solving a configuration-type LP and using a rounding procedure for (utilitarian) social welfare as a blackbox, which could be applicable to other variants of the problem.

1 Introduction

We consider the problem of allocating a set $\mathcal{I}$ of $m$ indivisible items to a set $\mathcal{A}$ of $n$ agents, where each agent $i\in\mathcal{A}$ has a valuation function $v_{i}:2^{\mathcal{I}}\to{\mathbb{R}}_{\geq 0}$ . The Nash social welfare (NSW) problem is to find an allocation ${\mathcal{S}}=(S_{i})_{i\in\mathcal{A}}$ that maximizes the geometric mean of the agents’ valuations,

\mbox{\sf NSW}({\mathcal{S}})=\left(\prod_{i\in\mathcal{A}}v_{i}(S_{i})\right)^{1/|\mathcal{A}|}.

For $\alpha\geq 1$ , an $\alpha$ -approximate solution to the NSW problem is an allocation $\mathcal{S}$ with $\mbox{\sf NSW}(\mathcal{S})\geq\mathrm{OPT}/\alpha$ , where $\mathrm{OPT}$ denotes the optimum value of the NSW-maximization problem.

Allocating resources to agents in a fair and efficient manner is a fundamental problem in computer science, economics, and social choice theory, with substantial prior work [Bar05, BT96, BCE⁺16, Mou04, RW98, Rot16, You95]. A common measure of efficiency is utilitarian social welfare, i.e., the sum of the utilities $\sum_{i\in\mathcal{A}}v_{i}(S_{i})$ for an allocation $(S_{i})_{i\in\mathcal{A}}$ . This objective does not take fairness into account, as all items could be allocated to one agent whose valuation function dominates the others. In order to incorporate fairness, various notions have been considered, ranging from envy-freeness, proportional fairness to various modifications of the objective function. At the end of the spectrum opposite to utilitarian social welfare, one can consider the max-min objective, $\min_{i\in\mathcal{A}}v_{i}(S_{i})$ , also known as the Santa Claus problem [BS06]. This objective is somewhat extreme in considering only the happiness of the least happy agent.

Nash social welfare provides a balanced tradeoff between the requirements of fairness and efficiency. It has been introduced independently in several contexts: as a discrete variant of the Nash bargaining game [KN79, Nas50]; as a notion of competitive equilibrium with equal incomes in economics [Var74]; and also as a proportional fairness notion in networking [Kel97]. Nash social welfare has several desirable features, for example invariance under scaling of the valuation functions $v_{i}$ by independent factors $\lambda_{i}$ , i.e., each agent can express their preference in a “different currency” without changing the optimization problem (see [Mou04] for additional characteristics).

1.1 Preliminaries

The difficulty of optimizing Nash social welfare depends naturally on the class of valuation functions that we want to deal with, and how they are accessible. Various classes of valuations have been considered in the literature. For the sake of this paper, let us introduce three basic classes of valuations, and two oracle models.

Classes of valuation functions

A set function $v:\,2^{\mathcal{I}}\to{\mathbb{R}}$ is monotone if $v(S)\leq v(T)$ whenever $S\subseteq T$ . A monotone set function with $v(\emptyset)=0$ is also called a valuation function or simply valuation.

A valuation $v:\,2^{\mathcal{I}}\to{\mathbb{R}}$ is additive if $v(S)=\sum_{j\in S}w_{j}$ for nonnegative weights $w_{j}$ .

A valuation $v:\,2^{\mathcal{I}}\to{\mathbb{R}}$ is submodular if $v(S)+v(T)\geq v(S\cap T)+v(S\cup T)\,\quad\forall S,T\subseteq\mathcal{I}$ .

A valuation $v:\,2^{\mathcal{I}}\to{\mathbb{R}}$ is fractionally subadditive (or XOS) if $v(S)=\max_{i\in\mathcal{I}}\sum_{j\in S}w_{ij}$ for nonnegative weights $w_{ij}$ .

A valuation $v:\,2^{\mathcal{I}}\to{\mathbb{R}}$ is subadditive if $v(S)+v(T)\geq v(S\cup T)\,\quad\forall S,T\subseteq\mathcal{I}$ .

We remark that these classes form a chain of inclusions: additive valuations are submodular, submodular valuations are XOS, and XOS valuations are subadditive.

Oracle access.

Note that additive valuations can be presented explicitly on the input. However, for more general classes of valuations, we need to resort to oracle access, since presenting a valuation explicitly would take an exponential amount of space. Three types of oracles to access valuation functions have been commonly considered in the literature.

•

Value oracle: Given a set $S\subseteq\mathcal{I}$ , return the value $v(S)$ .
•

Demand oracle: Given prices $(p_{j}:j\in\mathcal{I})$ , return a set $S$ maximizing $v(S)-\sum_{j\in S}p_{j}$ .
•

XOS oracle (for an XOS valuation $v$ ): Given a set $S$ , return an additive function $a$ from the XOS representation of $v$ such that $v(S)=a(S)$ .

1.2 Prior work

The Nash social welfare problem is NP-hard already in the case of two agents with identical additive valuations, by a reduction from the Subset-Sum problem. For multiple agents, it is NP-hard to approximate within a factor better than $0.936$ for additive valuations [GHM17], and better than $1-1/e\simeq 0.632$ for submodular valuations [GKK20].

The first constant-factor approximation algorithm for additive valuations, with the factor of $1/(2e^{1/e})\approx 0.346$ , was given by Cole and Gkatzelis [CG15] using a continuous relaxation based on a particular market equilibrium concept. Later, [CDG⁺17] improved the analysis of this algorithm to achieve the factor of $1/2$ . Anari, Oveis Gharan, Saberi, and Singh [AGSS17] used a convex relaxation that relies on properties of real stable polynomials, to give an elegant analysis of an algorithm that gives a factor of $1/e$ . The current best factor is $1/e^{1/e}-\epsilon\simeq 0.692$ by Barman, Krishnamurthy, and Vaish [BKV18]; the algorithm uses a different market equilibrium based approach. Note also that this factor is above $1-1/e$ , hence separating the additive and submodular settings.

Constant-factor approximations have been extended to some classes beyond additive functions: capped-additive [GHM18], separable piecewise-linear concave (SPLC) [AMGV18], and their common generalization, capped-SPLC [CCG⁺18] valuations; the approximation factor for capped-SPLC valuations matches the $1/e^{1/e}-\varepsilon$ factor for additive valuations. All these valuations are special classes of submodular ones. Subsequently, Li and Vondrák [LV21b] designed an algorithm that estimates the optimal value within a factor of $\frac{(e-1)^{2}}{e^{3}}\simeq 0.147$ for a broad class of submodular valuations, such as coverage and summations of matroid rank functions, by extending the techniques of [AGSS17] using real stable polynomials. However, this algorithm only estimates the optimum value but does not find a corresponding allocation in polynomial time.

An important concenptual advance was presented in [GHV20], where a relaxation combining ideas from matching theory and convex optimization was shown to give a constant factor for the class of “Rado valuations” (containing weighted matroid rank functions and some related valuations). A crucial property of this approach is that it is quite modular and ended up leadin to multiple further advances. In [LV21a], this approach was extended to provide a constant factor approximation algorithm for general submodular valuations, by replacing the concave extension of a valuation by the multilinear extension. The initial factor was rather small ( $1/380$ ). Recently, a much simpler algorithm combining matching and local search was presented to give a $(1/4-\epsilon)$ -approximation for submodular valuations [GHL⁺23].

For the more general classes of XOS and subadditive valuations [BBKS20, CGM21, GKK20], however, only polynomial approximation factors were known until now, and this is the best one can hope for in the value oracle model [BBKS20], for the same reasons that this is a barrier for the utilitarian social welfare problem [DNS10]. The best known approximation factors up to now have been $O(1/n)$ for subadditive valuations, and $O(1/n^{53/54})$ for XOS valuations if we are given access to both demand and XOS oracles [BKKN21]. Constant factors for XOS valuations seemed quite out of reach prior to this work, and obtaining any sublinear factor for subadditive valuations was stated as an open problem in [BKKN21].

1.3 Our results and techniques

Our main result is the following.

Theorem.

(informal) There is an algorithm, with polynomial time and demand queries to agents’ valuations, that provides a constant factor approximation for the Nash Social Welfare with subadditive valuations.

As a special case, this also gives a constant-factor approximation for XOS valuations accessible via demand queries. (The algorithm for XOS valuations is somewhat simpler, as we discuss later in this section.) This completes the picture in the sense that now we have a constant factor approximation for Nash social welfare in the main settings where one is known for utilitarian social welfare: for submodular valuations with value queries, and for subadditive valuations with demand queries. (It is known that a stronger oracle than a value oracle is required for XOS and subadditive valuations, even for utilitarian social welfare.)

The basis of our approach is the matching+relaxation paradigm which gave a constant-factor approximation for submodular valuations [GHV20, LV21a]. Considering that the only constant-factor approximation for social welfare with subadditive valuations [Fei08] is based on the "Configuration LP", which can be solved using demand queries, it is a natural idea to use a relaxation similar to the Configuration LP. A natural variant for Nash social welfare is the Eisenberg-Gale relaxation, using the logarithm of the concave extension of each agent’s valuation. We apply this relaxation on top of an initial matching, as in [GHV20].

The main obstacle with this approach is that natural rounding procedures for the Configuration LP do not satisfy any concentration properties. At a high level, without concentration some agents have higher value but some have lower value - leading to poor Nash social welfare even if we can maintain the expected utilitarian social welfare. More specifically, the first challenge is that, given a fractional solution $x_{i,S}$ , we would ideally like to round it to an integral allocation by allocating set $S$ to agent $i$ with probability $x_{i,S}$ . Even though this ideal rounding preserves each agent’s expected value, the variance can be arbitrary, depending on the fractional solution $x_{i,S}$ . Our first technical contribution is a procedure (see Lemma 3) for finding a new feasible solution to the Configuration LP that, for each agent, has only high value subsets in its support (with the exception of agents who get most of their value from a single item — this case is handled separately with the matching procedure). This procedure is rather simple in hindsight. At a high level, we can think of the fractional solution as a distribution of allocations for each agent. We want to discard the part of the distribution that corresponds to low value subsets; but this leaves uncovered probability mass. We re-cover this remaining mass by splitting high value subsets to “stretch” over more probability mass, while allocating each item with to agent $i$ with the same total probability.

The next obstacle in rounding the Configuration LP is resolving “contentions”: aka under the ideal rounding procedure described above, we may be trying to allocate the same item to multiple agents (even though in expectation it is only allocated to one agent). For XOS valuations, a simple independent randomized contention resolution scheme guarantees a constant factor approximation and also enjoys good concentration. However the situation is more complicated for subadditive valuations. The only known constant-factor approximation for social welfare with subadditive valuations is a rather intricate rounding procedure of Feige [Fei08], which does not seem to satisfy any useful concentration properties. In any rounded solution, there might be agents who receive very low value, which hurts Nash social welfare, and hence we cannot use it directly.

Our solution is an iterated rounding procedure, where in each stage a certain fraction of agents is “satisfied” in the sense that they receive value comparable to their fractional value. We allocate the respective items to them, subject to random filtering which ensures that enough items are still left for the remaining agents. Then we recurse on the remaining agents and remaining items. Still, some agents may receive a relatively small value, but we guarantee that the fraction of agents who receive low values is proportionally small, which means that the Nash social welfare overall is guaranteed to be good. As an example: if $OPT=(V_{1}\cdots V_{n})^{1/n}$ , it suffices to solve for an allocation where $\frac{n}{2}$ agents receive value at least $\frac{1}{2}V_{i}$ , $\frac{n}{4}$ agents receive value at least $\frac{1}{4}V_{i}$ , $\frac{n}{8}$ agents receive value at least $\frac{1}{8}V_{i}$ , and so on. Then the approximation factor in terms of Nash Social Welfare turns out to be

(1/2)^{1/2}(1/4)^{1/4}(1/8)^{1/8}(1/16)^{1/16}\cdots

and this infinite product converges to $1/4$ (we leave this as an exercise for the reader).

In order to guarantee the success of this rounding procedure, we need a concentration inequality (as in previous works). Concentration properties of subadditive functions are somewhat weaker and more difficult to prove that for submodular or XOS functions. Here we appeal to a powerful subadditive concentration inequality presented by Schechtman [Sch03], which is based on the “ $q$ -point control inequality” of Talagrand [Tal89, Tal95].

Reducing Nash Welfare to Rounding of Configuration LP

Technically, we prove a reduction theorem (Theorem 1) which shows that to achieve a constant factor approximation for Nash social welfare, is it sufficient to implement efficient subroutines for two subproblems: (1) finding a solution of the Configuration LP satisfying a certain additional property (which happens to be satisfied for example by an optimal solution of the Eisenberg-Gale relaxation [GHV20], or the continuous greedy algorithm for the log-multilinear relaxation [LV21a]), and (2) rounding a fractional solution of the Configuration LP while losing only a constant factor with respect to utilitarian social welfare. The latter problem is relatively easy for XOS valuations, but non-trivial for subadditive valuations. Fortunately, a factor $1/2$ rounding procedure is known due to Feige’s work on welfare maximization with subadditive bidders [Fei08], which we use here as a blackbox.

We remark that the constant factors lost in various stages of our proof are rather large and lead to a final approximation factor of $\sim 1/375,000$ for the Nash social welfare problem with subadditive valuations. One may hope that as in the case of submodular valuations, an initially large constant factor can be eventually improved to a “practical one”.

Paper organization.

In Section 2, we present the main technical result, which is a reduction of Nash social welfare to a certain relaxation solver and a rounding procedure for the Configuration LP. In Section 3, we show how this implies a constant factor approximation algorithm for Nash social welfare with subadditive valuations.

We defer some components of the algorithm which are similar to earlier work to the appendices: Solving the relaxation and proving the required guarantees (Appendix A), the rematching lemmas (Appendix B), and concentration of subadditive functions (Appendix C).

2 Optimizing NSW via relaxation and rounding for social welfare

Here we describe our general approach which allows us to derive algorithms for NSW optimization in several settings. At a high-level, we reduce the NSW optimization to finding a certain solution for the "Configuration LP" (for social welfare optimization), and having a rounding procedure for the Configuration LP, again with respect to social welfare.

Let us define the Configuration LP:

$\displaystyle\max\quad$	$\displaystyle\sum_{i\in\mathcal{A}}\sum_{S\subseteq\mathcal{I}}v_{i}(S)x_{i,S}$		(Configuration LP)
	$\displaystyle\quad\sum_{i\in\mathcal{A}}\sum_{S\subseteq\mathcal{I}:j\in S}x_{i,S}\leq 1$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\quad\sum_{S\subseteq\mathcal{I}}x_{i,S}=1$	$\displaystyle\forall i\in\mathcal{A}$
	$\displaystyle\quad x_{i,S}\geq 0$	$\displaystyle\forall i\in\mathcal{A},S\subseteq\mathcal{I}$

Equivalently, this can be written as

$\displaystyle\max\quad$	$\displaystyle\sum_{i\in\mathcal{A}}v_{i}^{+}(\mathbf{x}_{i})$
	$\displaystyle\quad\sum_{i\in\mathcal{A}}x_{ij}\leq 1$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\quad x_{ij}\geq 0$	$\displaystyle\forall i\in\mathcal{A},j\in\mathcal{I}$

where as before,

$\displaystyle v_{i}^{+}(\mathbf{x}_{i})=$	$\displaystyle\max\sum_{S\subset\mathcal{I}}v_{i}(S)x_{i,S}:$		(Concave Extension)
	$\displaystyle\sum_{S\subset\mathcal{I}:j\in S}x_{i,S}\leq x_{ij}$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\ \ \sum_{S\subset\mathcal{I}}x_{i,S}=1$
	$\displaystyle\ \ x_{i,S}\geq 0$	$\displaystyle\forall S\subset\mathcal{I}$

The following is our main reduction theorem, which provides an algorithm for Nash social welfare, given two procedure that we call the Relaxation Solver and Rounding Procedure. Note that assumption on the Relaxation Solver is somewhat unusual: It is not that $(x_{i,S})$ is an optimal or near-optimal solution of (Configuration LP), but a different condition that the optimum social welfare with valuations by $w_{i}(S)=v_{i}(S)/V_{i}=v_{i}(S)/\sum_{S^{\prime}}v_{i}(S^{\prime})x_{i,S^{\prime}}$ is upper-bounded by $c|\mathcal{A}|$ . (The social welfare of $x_{i,S}$ itself with valuations $w_{i}$ is exactly $|\mathcal{A}|$ , so as a consequence $(x_{i,S})$ is $c$ -approximate optimum with respect to the valuations $w_{i}$ .) This condition is required primarily for the later “rematching” step (Lemma 8). Fortunately, this condition is satisfied by natural approaches to solve the “Gale-Eisenberg” relaxation, which replaces the continuous valuation extensions by their logarithms. We discuss this further in Section 3.

Theorem 1.

Suppose that for a certain class of instances of Nash social welfare, with subadditive valuations, we have the following procedures available, with parameters $c,d\geq 1$ :

•

Relaxation Solver: Given valuations $(v_{i}:i\in\mathcal{A})$ on a set of items $\mathcal{I}$ , we can find a feasible solution $(x_{i,S})$ of (Configuration LP) such that the social welfare optimum with valuations

$w_{i}(S)=\frac{1}{V_{i}}v_{i}(S),\ \ \ \ \ V_{i}=\sum_{S\subseteq\mathcal{I}}v_{i}(S)x_{i,S}$

is at most $c|\mathcal{A}|$ .
•

Rounding Procedure: Given a feasible solution $(x_{i,S})$ of (Configuration LP), we can find an allocation $(S_{1},\ldots,S_{n})$ where each $S_{i}$ is a subset of some set $S^{\prime}_{i}$ such that $x_{i,S^{\prime}_{i}}>0$ and

$\sum_{i\in\mathcal{A}}w_{i}(S_{i})=\sum_{i\in\mathcal{A}}\frac{1}{V_{i}}v_{i}(S_{i})\geq\frac{1}{d}|\mathcal{A}|.$

(As above, $V_{i}=\sum_{S\subseteq\mathcal{I}}v_{i}(S)x_{i,S}$ .)

Then there is an algorithm which provides an $O(cd^{2})$ -approximation in Nash social welfare for the same class of instances, using $1$ call to the Relaxation Solver and a logarithmic number of calls to the Rounding Procedure. The running time is polynomial in $|\mathcal{A}|,|\mathcal{I}|$ and the support of the fractional solution $(x_{i,S})$ .

In the following, we prove this theorem by presenting an algorithm with several phases. These phases are similar to recent matching-based algorithms for Nash social welfare [GHV20, GHV21, LV21a, GHL⁺23] with the exception of two phases which are new (phases 3,4 below). The high-level outline is as follows.

NSW Algorithm Template.

1.

We find an initial matching $\tau:\mathcal{A}\to\mathcal{I}$ , maximizing $\prod_{i\in\mathcal{A}}v_{i}(\{\tau(i)\})$ . Let $\mathcal{H}=\tau[\mathcal{A}]$ denote the matching items and $\mathcal{I}^{\prime}=\mathcal{I}\setminus\mathcal{H}$ the remaining items. Let also $\mathcal{A}^{\prime}=\{i\in\mathcal{A}:v_{i}(\mathcal{I}^{\prime})>0\}$ .
2.

We apply the Relaxation Solver to obtain a fractional solution $(x_{i,S})_{i\in\mathcal{A}^{\prime},S\subseteq\mathcal{I}^{\prime}}$ and values $V_{i}=\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x_{i,S}$ . We can view these values as “targets” for different agents to achieve.
3.

Let $\nu_{i}=\max_{i\in\mathcal{I}^{\prime}}v_{i}(j)$ and $\mathcal{A}^{\prime\prime}=\{i\in\mathcal{A}^{\prime}:V_{i}\geq 6\nu_{i}\}$ . We preprocess the fractional solution $(x_{i,S})$ for $i\in\mathcal{A}^{\prime\prime}$ , removing sets of low value and partitioning sets of high value, so that for every set in the support of the new fractional solution $x^{\prime}_{i,S}$ for agent $i$ , we have $v_{i}(S)=\Theta(V_{i})$ .
4.

We apply the Rounding Procedure to $x^{\prime}_{i,S}$ to find an allocation $(S_{i}\in\mathcal{A}^{\prime\prime})$ satisfying

$\sum_{i\in\mathcal{A}}\frac{1}{V_{i}}v_{i}(S_{i})=\Omega\left(\frac{1}{d}|\mathcal{A}|\right).$

Since each $S_{i}$ has value at most $V_{i}$ (due to our preprocessing), it must be the case that a $\Theta(\frac{1}{d}$ )-fraction of agents receive value at least $\Theta(\frac{1}{d}V_{i})$ . We allocate a random $\Theta(\frac{1}{d})$ -fraction of items to this $\Theta(\frac{1}{d})$ -fraction of agents (each item from their respective sets independently with probability $\Theta(\frac{1}{d})$ ); call the resulting set $T_{i}$ for agent $i$ . We repeat this phase for the remaining items and agents, until there are no agents left. For agents $i\in\mathcal{A}\setminus\mathcal{A}^{\prime\prime}$ , we define $T_{i}=\emptyset$ .
5.

We recompute the initial matching to obtain a new matching $\sigma:\mathcal{A}\to\mathcal{H}$ , which maximizes $\prod_{i\in\mathcal{A}}v_{i}(T_{i}+\sigma(i))$ . We allocate $T_{i}+\sigma(i)$ to agent $i$ .

Now we proceed to analyze the phases of this algorithm more rigorously.

2.1 Initial Matching

There is nothing new in this phase. We can find a matching $\tau:\mathcal{A}\to\mathcal{I}$ maximizing $\prod_{i\in\mathcal{A}}v_{i}(\tau(i))$ by solving a max-weight matching problem with edges $(i,j)$ where $v_{i}(j)>0$ , and weights $w_{ij}=\log v_{i}(j)$ .

We denote by $\mathcal{H}=\tau[\mathcal{A}]$ the matched items, by $\mathcal{I}^{\prime}=\mathcal{I}\setminus\mathcal{H}$ the remaining items, and by $\mathcal{A}^{\prime}=\{i\in\mathcal{A}:v_{i}(\mathcal{I}^{\prime})>0\}$ the agents who get positive value from $\mathcal{I}^{\prime}$ .

A property we need in the following is the following.

Lemma 2.

If $\tau:\mathcal{A}\to\mathcal{I}$ is a matching maximizing $\prod_{i\in\mathcal{A}}v_{i}(\tau(i))$ then for any $j\in\mathcal{I}^{\prime}=\mathcal{I}\setminus\tau[\mathcal{A}]$ , $v_{i}(j)\leq v_{i}(\tau(i))$ .

Proof.

If there is $j\in\mathcal{I}^{\prime}$ , $v_{i}(j)>v_{i}(\tau(i))$ , then we can swap $\tau(i)$ for $j$ in the matching and increase its value. ∎

For subadditive valuations, we also get $v_{i}(S+j)-v_{i}(S)\leq v_{i}(\tau(i))$ for any $S\subset\mathcal{I}^{\prime},j\in\mathcal{I}^{\prime}\setminus S$ (since $v_{i}(S+j)\leq v_{i}(S)+v_{i}(j)$ ).

2.2 Relaxation Solver

Here we assume that the Relaxation Solver is available as a black-box. We return to its implementations in specific settings in Section 3.

We apply the Relaxation Solver to the residual instance on items $\mathcal{I}^{\prime}=\mathcal{I}\setminus\mathcal{H}$ and agents $\mathcal{A}^{\prime}$ who have nonzero value for some items in $\mathcal{I}^{\prime}$ . The important property of the obtained solution $(x_{i,S})$ is that after scaling the valuations as follows,

w_{i}(S)=\frac{1}{V_{i}}v_{i}(S),\ \ \ \ \ V_{i}=\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x_{i,S}

the social welfare optimum for $w_{1},\ldots,w_{n}$ is at most $c|\mathcal{A}^{\prime}|$ . In other words, for any feasible allocation $(T^{*}_{1},\ldots,T^{*}_{n})$ of $\mathcal{I}^{\prime}$ , we have

\sum_{i\in\mathcal{A}^{\prime}}\frac{v_{i}(T^{*}_{i})}{V_{i}}\leq c|\mathcal{A}^{\prime}|.

2.3 Set Splitting

Here we describe Phase 3, preprocessing of the fractional solution. We will work only with agents who get significant value from the fractional solution: Let $\nu_{i}=\max_{j\in\mathcal{I}^{\prime}}v_{i}(j)$ and

\mathcal{A}^{\prime\prime}:=\{i\in\mathcal{A}^{\prime}:V_{i}\geq 6\nu_{i}\}.

We prove the following.

Lemma 3.

Assume that the valuations $v_{1},\ldots,v_{n}$ are subadditive. Given a feasible solution $(x_{i,S})$ of (Configuration LP) for an instance with agents $\mathcal{A}^{\prime\prime}$ and items $\mathcal{I}^{\prime}$ , where $V_{i}=\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x_{i,S}$ and $\nu_{i}=\max_{j\in\mathcal{I}^{\prime}}v_{i}(j)$ , we can find (in running time and a number of value queries polynomial in the number of nonzero coefficients $x_{i,S}$ ) a modified solution $(x^{\prime}_{i,S})$ such that

•

For every $S$ such that $x^{\prime}_{i,S}>0$ , $\frac{1}{3}V_{i}-\nu_{i}\leq v_{i}(S)\leq V_{i}$ .
•

For every $i\in\mathcal{A}^{\prime\prime}$ , $\sum_{S\subseteq\mathcal{I}}x^{\prime}_{i,S}=1$ .
•

For every $j\in\mathcal{I}^{\prime}$ , $\sum_{i,S\ni j}x^{\prime}_{i,S}\leq 1$ .

Proof.

We apply the following procedure to the fractional solution $\mathbf{x}=(x_{i,S})$ .

SetSplitting( $\mathbf{x}$ ).

1.

Let $V_{i}=\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x_{i,S}$ , $\nu_{i}=\max_{j\in\mathcal{I}^{\prime}}v_{i}(j)$ , and $\mathcal{F}_{i}=\{S\subseteq\mathcal{I}^{\prime}:v_{i}(S)\geq\frac{1}{3}V_{i}\}$ .
2.

Set $x^{\prime}_{i,S}=0$ and $k_{i,S}=0$ for $S\notin\mathcal{F}_{i}$ ; i.e., discard sets whose value is too low.
3.

For every $S\in\mathcal{F}_{i}$ , let $k_{i,S}=\lfloor\frac{3v_{i}(S)}{V_{i}}\rfloor$ . Split $S$ into sets $S_{1},\cdots,S_{k_{i,S}}$ such that $\forall\ell=1,\ldots,k_{i,S}$ ,

$v_{i}(S_{\ell})\geq\frac{1}{3}V_{i}-\nu_{i}.$

Note that this is possible since by subadditivity, the average value of a subset in any partition of $S$ into $k_{i,S}$ subsets is at least $v_{i}(S)/k_{i,S}\geq\frac{1}{3}V_{i}$ , and indivisibility of items can cause the value to drop by at most $\nu_{i}$ .
4.

For each set $S_{\ell}$ produced above, remove some items if necessary to ensure that its value is at most $V_{i}$ . Call the resulting set $S^{\prime}_{\ell}$ . Note that since removing an item can decrease the value by at most $\nu_{i}$ , we start from value $\geq\frac{1}{3}V_{i}-\nu_{i}$ , and we only remove items as long as the value is more than $V_{i}$ , we can conclude that

$V_{i}\geq v_{i}(S^{\prime}_{\ell})\geq\frac{1}{3}V_{i}-\nu_{i}.$
5.

Set $\tilde{x}_{i,T}=\sum_{S\in\mathcal{F}_{i},\exists\ell:S^{\prime}_{\ell}=T}x_{i,S}$ , and $x^{\prime}_{i,T}=\frac{\tilde{x}_{i,T}}{\sum_{S}\tilde{x}_{i,S}}$ .
6.

Return $\mathbf{x}^{\prime}$ .

Let us now prove the desired properties of $\mathbf{x}^{\prime}$ . By construction (step 5), the solution is normalized in the sense that $\sum_{T}x^{\prime}_{i,T}=1$ for every $i\in\mathcal{A}^{\prime\prime}$ . Also, as we argued above, $V_{i}\geq v_{i}(T)\geq\frac{1}{3}V_{i}-\nu_{i}$ for every set $T$ participating in the support of $\mathbf{x}^{\prime}$ . It remains to prove that the coefficients $x^{\prime}_{i,T}$ add up to at most $1$ on each item.

Let us first consider $\tilde{x}_{i,T}$ : Since each contribution to $\tilde{x}_{i,T}$ for $j\in T$ is inherited from some coefficient $x_{i,S}$ where $j\in S$ , each coefficient $x_{i,S}$ contributes at most once in this way, and the coefficients $x_{i,S}$ for $S\ni j$ add up to at most $1$ , it is clear that $\sum_{i,T\ni j}\tilde{x}_{i,T}\leq 1$ . Finally, $x^{\prime}_{i,T}$ is obtained by normalizing $\tilde{x}_{i,T}$ ; so we need to be concerned about the summation $\sum_{S}\tilde{x}_{i,S}$ , which could be possibly less than $1$ .

We have:

\sum_{S\in\mathcal{F}_{i}}v_{i}(S)x_{i,S}=V_{i}-\sum_{S\notin\mathcal{F}_{i}}v_{i}(S)x_{i,S}\geq V_{i}-\frac{1}{3}V_{i}=\frac{2}{3}V_{i}.

Observe that each coefficient $x_{i,S}$ for $S\in\mathcal{F}_{i}$ contributes $k_{i,S}$ coefficients of the same value to the summation $\sum_{S}\tilde{x}_{i,S}$ , and the union of the respective sets is $S$ . So we have

\sum_{S\subseteq\mathcal{I}^{\prime}}\tilde{x}_{i,S}=\sum_{S\in\mathcal{F}_{i}}k_{i,S}x_{i,S}=\sum_{S\in\mathcal{F}_{i}}\left\lfloor\frac{3v_{i}(S)}{V_{i}}\right\rfloor\cdot x_{i,S}\geq\frac{3}{2}\sum_{S\in\mathcal{F}_{i}}\frac{v_{i}(S)x_{i,S}}{V_{i}}\geq 1

considering that $3v_{i}(S)/V_{i}\geq 1$ for $S\in\mathcal{F}_{i}$ , so the floor operation can decrease the ratio by at most a factor of $2$ . Also, we have $\sum_{S\in\mathcal{F}_{i}}v_{i}(S)x_{i,S}\geq\frac{2}{3}V_{i}$ from above. Hence $x^{\prime}_{i,T}=\frac{\tilde{x}_{i,T}}{\sum_{S}\tilde{x}_{i,S}}\leq\tilde{x}_{i,T}$ and the coefficients $x^{\prime}_{i,S}$ for $S\ni j$ add up to at most $1$ . ∎

2.4 Iterated Rounding

Finally, we need to round the fractional solution $(x^{\prime}_{i,S})$ obtained in the previous phase. As a subroutine, we use the assumed Rounding Procedure for (additive) social welfare.

Given a fractional solution $\mathbf{x}^{\prime}=(x^{\prime}_{i,S})$ obtained in the previous phase, we call the procedure NSW-ROUND $(\mathbf{x}^{\prime},\mathcal{A}^{\prime\prime},\mathcal{I}^{\prime},\delta)$ with a parameter $\delta=\frac{1}{7d}$ , where $d$ is a approximation factor guaranteed by the Rounding Procedure.

Algorithm 1 Iterated Rounding

1:procedure NSW-Round(

\mathbf{x}^{\prime},\mathcal{A}_{0},\mathcal{I}_{0},\delta

2: Let

V^{\prime}_{i}\leftarrow\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x^{\prime}_{i,S}

3: For each item

j\in\mathcal{I}_{0}

independently, let

r_{j}\leftarrow t

with probability

\delta(1-\delta)^{t-1}

for

t\geq 1

4: Let

R_{t}\leftarrow\{j\in\mathcal{I}_{0}:r_{j}=t\}

for all

t\geq 1

5: Let

t\leftarrow 1

6: while

\mathcal{A}_{t}\neq\emptyset

(S_{i}:i\in\mathcal{A}_{t})\leftarrow{\bf RoundingProcedure}(\mathbf{x}^{\prime},\mathcal{A}_{t})

\mathcal{A}_{t+1}\leftarrow\{i\in\mathcal{A}_{t}:v_{i}(S_{i})<\delta V^{\prime}_{i}\}

9: For each agent

i\in\mathcal{A}_{t}\setminus\mathcal{A}_{t+1}

, allocate

T_{i}\leftarrow S_{i}\cap R_{t}

10: end while

11: Return

(T_{i}:i\in\mathcal{A}_{0})

12:end procedure

As we mentioned above, the intuition behind this rounding procedure is that it gives good value to a large fraction of agents, and exponentially small values to an exponentially decaying number of agents, so overall its Nash social welfare is good. We prove this in a sequence of lemmas.

Lemma 4.

Under our assumption on the Rounding Procedure, and setting $\delta=\frac{1}{7d}$ , in each round there is at least a $\delta$ -fraction of agents (rounded up to the nearest integer) who receive value at least $\delta V^{\prime}_{i}$ .

Proof.

Note that $V^{\prime}_{i}\geq\frac{1}{6}V_{i}$ , since every set in the support of $x^{\prime}_{i,S}$ has value at least $\frac{1}{3}V_{i}-\nu_{i}\geq\frac{1}{6}V_{i}$ . We assume that under valuations $w_{i}(S)=\frac{1}{V^{\prime}_{i}}v_{i}(S)$ , the Rounding Procedure returns an allocation $(S_{i}:i\in\mathcal{A}_{t})$ such that $\sum_{i\in\mathcal{A}_{t}}w_{i}(S_{i})\geq\frac{1}{d}|\mathcal{A}_{t}|$ . Also, the fractional solution $\mathbf{x}^{\prime}$ has been processed so that no set in its support for agent $i$ has value more than $V_{i}\leq 6V^{\prime}_{i}$ , and the rounding only allocates subsets of sets in the support of $\mathbf{x}^{\prime}$ . Hence, we have $w_{i}(S_{i})=\frac{1}{V^{\prime}_{i}}v_{i}(S_{i})\leq 6$ for every agent $i$ . Consider the agents who receive value $w_{i}(S_{i})\geq\delta$ ; if the number of such agents is less than $\delta|\mathcal{A}_{t}|$ , then the total value collected by the agents is $\sum_{i\in\mathcal{A}_{t}}w_{i}(S)<6\cdot\delta|\mathcal{A}_{t}|+\delta\cdot(1-\delta)|\mathcal{A}_{t}|<7\delta|\mathcal{A}_{t}|=\frac{1}{d}|\mathcal{A}_{t}|$ , which is a contradiction. ∎

Lemma 5.

If $|\mathcal{A}_{0}|=a$ and the agents are ordered by the round in which they received items (and arbitrarily within each round), then the $i$ -th agent receives each element of her set $S_{i}$ independently with probability at least $\delta(1-\frac{i-1}{a})$ .

Proof.

Consider the $i$ -th agent, and suppose that $i\in\mathcal{A}_{t}\setminus\mathcal{A}_{t+1}$ , i.e. the agent gets items in round $t$ . We claim that $a(1-\delta)^{t-1}\geq n-i+1$ : In each round, we allocate items to at least a $\delta$ -fraction of agents, so the set of agents $\mathcal{A}_{t-1}$ remaining after $t-1$ rounds has size at most $a(1-\delta)^{t-1}$ . This set must include agent $i$ , otherwise she would have been satisfied earlier. Therefore, $a-i+1\leq a(1-\delta)^{t-1}$ .

The items allocated to agent $i$ in round $t$ are $S_{i}\cap R_{t}$ , where $R_{t}$ contains each element independently with probability $\delta(1-\delta)^{t-1}$ . By the argument above, $\delta(1-\delta)^{t-1}\geq\delta\cdot\frac{a-i+1}{a}$ . ∎

Lemma 6.

If $T_{i}$ is the set allocated to the $i$ -th agent in the ordering defined above (and we assume w.l.o.g. that the index of this agent is also $i$ ), and $\max_{j\in\mathcal{I}^{\prime}}v_{i}(j)\leq\nu_{i}$ then

{\mathbb{E}}\left[\log\frac{V_{i}}{v_{i}(T_{i})+\nu_{i}}\right]\leq\log\frac{60}{\delta^{2}(1-\frac{i-1}{n})}.

Proof.

By definition, the set $S_{i}$ tentatively chosen for the $i$ -th agent in the round where $i\in\mathcal{A}_{t}\setminus\mathcal{A}_{t+1}$ satisfies

v_{i}(S_{i})\geq\delta V^{\prime}_{i}\geq\delta\left(\frac{1}{3}V_{i}-\nu_{i}\right)

(see Lemma 3). By Lemma 5, the $i$ -th agent receives a set $T_{i}=S_{i}\cap R_{t}$ which contains each element of $S_{i}$ independently with probability at least $\delta(1-\frac{i-1}{n})$ .

Consider now the expression $\log\frac{V_{i}}{f(T_{i})}$ , where $f(T_{i})=v_{i}(T_{i})+\nu_{i}$ . This is a random quantity due to the randomness in $R_{t}$ (the set $S_{i}$ is fixed here). We use concentration of subadditive functions (Theorem 20) to argue that this expression is not too large in expectation. We have $f(S_{i})=v_{i}(S_{i})+\nu_{i}\geq\frac{1}{3}\delta V_{i}$ . By the expectation property of subadditive functions (Lemma 16), we have

\displaystyle{\mathbb{E}}[f(T_{i})]={\mathbb{E}}[f(S_{i}\cap R_{t})]\geq\delta(1-\frac{i-1}{n})\cdot\frac{1}{3}\delta V_{i}=\frac{1}{3}\delta^{2}(1-\frac{i-1}{n})V_{i}.

Let us denote the last expression $\mu_{i}:=\frac{1}{3}\delta^{2}(1-\frac{i-1}{n})V_{i}\leq{\mathbb{E}}[f(T_{i})]$ .

Now, we apply the lower-tail inequality, Theorem 20, with $q=2$ . Observe that we can assume $\nu_{i}<\frac{1}{20}\mu_{i}$ . Otherwise,

\frac{V_{i}}{\nu_{i}}\leq\frac{20V_{i}}{\mu_{i}}=\frac{60}{\delta^{2}(1-\frac{i-1}{n})}

and so the desired bound holds.

Let us set $q=2$ and $k+1=\lfloor\frac{\mu_{i}}{10\nu_{i}}\rfloor\geq\frac{\mu_{i}}{15\nu_{i}}$ (considering that $\frac{\mu_{i}}{10\nu_{i}}\geq 2$ ) in Theorem 20. We get

	$\displaystyle\Pr\left[f(T_{i})<\frac{\mu_{i}}{30}\right]$	$\displaystyle\leq\Pr\left[f(T_{i})\leq\frac{{\mathbb{E}}[f(T_{i})]}{15}-\frac{\mu_{i}}{30}\right]$
		$\displaystyle\leq\Pr\left[f(T_{i})\leq\frac{{\mathbb{E}}[f(T_{i})]}{5(q+1)}-\frac{(k+1)\nu_{i}}{q+1}\right]$
		$\displaystyle\leq\left(\frac{2}{2^{k}}\right)^{1/2}\leq\frac{2}{2^{\mu_{i}/(30\nu_{i})}}.$

Our goal is to bound the expectation ${\mathbb{E}}[\log\frac{V_{i}}{f(T_{i})}]$ . We distinguish two cases: When $f(T_{i})<\frac{1}{30}\mu_{i}$ , we use the bound $f(T_{i})\geq\nu_{i}$ , which always holds. Otherwise, we use the bound $f(T_{i})\geq\frac{1}{30}\mu_{i}$ . From here,

{\mathbb{E}}\left[\log\frac{V_{i}}{f(T_{i})}\right]\leq\Pr\left[f(T_{i})<\frac{\mu_{i}}{30}\right]\cdot\log\frac{V_{i}}{\nu_{i}}+\left(1-\Pr\left[f(T_{i})<\frac{\mu_{i}}{30}\right]\right)\cdot\log\frac{30V_{i}}{\mu_{i}}

=\Pr\left[f(T_{i})<\frac{\mu_{i}}{30}\right]\cdot\log\frac{\mu_{i}}{30\nu_{i}}+\log\frac{30V_{i}}{\mu_{i}}

\leq\frac{2}{2^{\mu_{i}/(30\nu_{i})}}\log\frac{\mu_{i}}{30\nu_{i}}+\log\frac{30V_{i}}{\mu_{i}}.

One can verify that the function $\frac{2}{2^{x}}\log x$ is upper-bounded by $\log 2$ for all $x>0$ .¹¹1We are using natural logarithms everywhere. Hence,

{\mathbb{E}}\left[\log\frac{V_{i}}{f(T_{i})}\right]\leq\log 2+\log\frac{30V_{i}}{\mu_{i}}<\log\frac{60V_{i}}{\mu_{i}}=\log\frac{60}{\delta^{2}(1-\frac{i-1}{n})}.

∎

Lemma 7.

\frac{1}{|\mathcal{A}^{\prime\prime}|}\sum_{i\in\mathcal{A}^{\prime\prime}}{\mathbb{E}}\left[\log\frac{V_{i}}{v_{i}(T_{i})+\nu_{i}}\right]\leq\log\frac{165}{\delta^{2}}.

Proof.

Let us denote $a=|\mathcal{A}^{\prime\prime}|$ . From Lemma 6, we have

\displaystyle\frac{1}{a}\sum_{i=1}^{a}{\mathbb{E}}\left[\log\frac{V_{i}}{v_{i}(T_{i})+\nu_{i}}\right]

\displaystyle\leq

\displaystyle\frac{1}{a}\sum_{i=1}^{a}\log\frac{60}{\delta^{2}(1-\frac{i-1}{n})}=\left(\log\frac{60}{\delta^{2}}-\frac{1}{a}\sum_{i=1}^{a}\log\left(1-\frac{i-1}{a}\right)\right)

Here, we have $\sum_{i=1}^{a}\log(1-\frac{i-1}{a})=\log\prod_{i=1}^{a}\frac{a-i+1}{a}=\log\frac{a!}{a^{a}}\geq-a$ by a standard estimate for the factorial. So we can conclude

\frac{1}{a}\sum_{i=1}^{a}{\mathbb{E}}\left[\log\frac{V_{i}}{v_{i}(T_{i})+\nu_{i}}\right]\leq\log\frac{60}{\delta^{2}}+1<\log\frac{165}{\delta^{2}}.

∎

This concludes the analysis of the iterated rounding phase, which allocates the set $T_{i}$ to each agent $i\in\mathcal{A}^{\prime\prime}$ . For agents $i\in\mathcal{A}\setminus\mathcal{A}^{\prime\prime}$ , we set $T_{i}=\emptyset$ .

2.5 Rematching and finishing the analysis

The last step in the algorithm is to replace the initial matching $\tau:\mathcal{A}\to\mathcal{H}$ with a new matching $\sigma:\mathcal{A}\to\mathcal{H}$ which is optimal on top of the allocation $(T_{i}:i\in\mathcal{A})$ . To analyze this step, we need two lemmas from previous work, whose proofs can be modified easily to yield the following. (We provide full proofs in the appendix.)

Lemma 8 (matching extension).

Let $\tau:\mathcal{A}\rightarrow\mathcal{I}$ be the matching maximizing $\prod_{a\in\mathcal{A}}v_{i}(\tau(a))$ , $\mathcal{H}=\tau(\mathcal{A})$ , and $\mathcal{I}^{\prime}=\mathcal{I}\setminus\mathcal{H}$ . Let $(V_{i}:i\in\mathcal{A})$ be values such that $V_{i}>0$ for $i\in\mathcal{A}^{\prime}$ , $V_{i}=0$ for $i\in\mathcal{A}\setminus\mathcal{A}^{\prime}$ and

\sum_{i\in\mathcal{A}^{\prime}}\frac{v_{i}(T^{*}_{i})}{V_{i}}\leq c|\mathcal{A}^{\prime}|

for every allocation $(T^{*}_{1},\ldots,T^{*}_{n})$ of the items in $\mathcal{I}^{\prime}$ . Then there is a matching $\pi:\mathcal{A}\rightarrow\mathcal{H}$ such that

\prod_{i\in\mathcal{A}}(V_{i}+v_{i}(\pi(i)))^{1/|\mathcal{A}|}\geq\frac{1}{c+1}\prod_{i\in\mathcal{A}}\left(v_{i}(S^{*}_{i})\right)^{1/|\mathcal{A}|}=\frac{OPT}{c+1}

where $(S^{*}_{1},\ldots,S^{*}_{n})$ is an allocation of $\mathcal{I}$ optimizing Nash social welfare.

Lemma 9 (rematching).

Let $\tau:\mathcal{A}\rightarrow\mathcal{I}$ be the matching maximizing $\prod_{a\in\mathcal{A}}v_{i}(\tau(a))$ , $\mathcal{H}=\tau(\mathcal{A})$ , $\mathcal{I}^{\prime}=\mathcal{I}\setminus\mathcal{H}$ , $\pi:\mathcal{A}\to\mathcal{H}$ another arbitrary matching, and $\nu_{i}=\max_{j\in\mathcal{I}^{\prime}}v_{i}(j)$ . Let $(W_{i}:i\in\mathcal{A})$ be nonnegative values. Then there is a matching $\rho:\mathcal{A}\rightarrow\mathcal{H}$ such that

\prod_{i\in\mathcal{A}}(\max\{W_{i},v_{i}(\rho(i))\})^{1/|\mathcal{A}|}\geq\prod_{i\in\mathcal{A}}\left(\max\{W_{i},v_{i}(\pi(i)),\nu_{i}\}\right)^{1/|\mathcal{A}|}.

We apply Lemma 8 with the values $V_{i}=\sum_{S\subseteq\mathcal{I}^{\prime}}v_{i}(S)x_{i,S}$ , where $(x_{i,S})$ is the fractional solution returned by Relaxation Solver. Due to our assumptions, the condition of Lemma 8 is satisfied and hence there is a matching $\pi:\mathcal{A}\to\mathcal{H}$ as described in Lemma 8:

\prod_{i\in\mathcal{A}}(V_{i}+v_{i}(\pi(i)\})^{1/|\mathcal{A}|}\geq\frac{OPT}{c+1}.

From Lemma 7, we can find with constant probability an assignment $(T_{i}:i\in\mathcal{A}^{\prime\prime})$ such that

\left(\prod_{i\in\mathcal{A}^{\prime\prime}}\frac{V_{i}}{v(T_{i})+\nu_{i}}\right)^{1/|\mathcal{A}^{\prime\prime}|}<\frac{200}{\delta^{2}}<10000\,d^{2}.

(Recall that $\delta=\frac{1}{7d}$ , where $d>1$ is the parameter guaranteed by the Rounding Procedure.)

Moreover, we know that $v(T_{i})\leq V_{i}$ and $V_{i}\geq 6\nu_{i}$ , hence $v(T_{i})+\nu_{i}\leq 2V_{i}$ for $i\in\mathcal{A}^{\prime\prime}$ . For agents in $\mathcal{A}\setminus\mathcal{A}^{\prime\prime}$ , we have $T_{i}=\emptyset$ and $V_{i}\leq 6\nu_{i}$ . From here, we have

	$\displaystyle\prod_{i\in\mathcal{A}}\frac{V_{i}+v_{i}(\pi(i))}{v(T_{i})+\nu_{i}+v_{i}(\pi(i))}$	$\displaystyle\leq$	$\displaystyle\prod_{i\in\mathcal{A}^{\prime\prime}}\frac{2V_{i}+v_{i}(\pi(i))}{v(T_{i})+\nu_{i}+v_{i}(\pi(i))}\prod_{i\in\mathcal{A}\setminus\mathcal{A}^{\prime\prime}}\frac{6\nu_{i}+v_{i}(\pi(i))}{\nu_{i}+v_{i}(\pi(i))}$
		$\displaystyle\leq$	$\displaystyle\prod_{i\in\mathcal{A}^{\prime\prime}}\frac{2V_{i}}{v(T_{i})+\nu_{i}}\prod_{i\in\mathcal{A}\setminus\mathcal{A}^{\prime\prime}}6\leq(20000\,d^{2})^{\|\mathcal{A}\|}.$

Finally, we use the rematching Lemma 9, with values $v_{i}(T_{i})$ : there exists a matching $\rho:\mathcal{A}\to\mathcal{H}$ such that

\prod_{i\in\mathcal{A}}(\max\{v_{i}(T_{i}),v_{i}(\rho(i))\})^{1/|\mathcal{A}|}\geq\prod_{i\in\mathcal{A}}(\max\{v_{i}(T_{i}),v_{i}(\pi(i)),\nu_{i}\})^{1/|\mathcal{A}|}\geq\frac{1}{3}\prod_{i\in\mathcal{A}}(V_{i}+\nu_{i}+v_{i}(\pi(i)))^{1/|\mathcal{A}|}

\geq\frac{1}{20000\,d^{2}}\prod_{i\in\mathcal{A}}(V_{i}+v_{i}(\pi(i)))^{1/|\mathcal{A}|}\geq\frac{OPT}{20000(c+1)d^{2}}.

Recall that at the end, we find a matching $\sigma:\mathcal{A}\to\mathcal{H}$ maximizing $\prod_{i\in\mathcal{A}}v_{i}(T_{i}+\sigma(i))$ . Therefore, the NSW value of our solution is at least as much as the one provided by the matching $\rho$ , which is $\prod_{i\in\mathcal{A}}(v_{i}(T_{i}+\rho(i))^{1/|\mathcal{A}|}\geq\prod_{i\in\mathcal{A}}(\max\{v_{i}(T_{i}),v_{i}(\rho(i))\})^{1/|\mathcal{A}|}\geq\frac{1}{20000(c+1)d^{2}}OPT$ . This proves Theorem 1.

3 Nash social welfare with subadditive valuations

Here we explain how to use the general framework described in Section 2 to obtain a constant-factor approximation for subadditive valuations, accessible by demand queries.

Theorem 10.

There is a constant-factor approximation algorithm for the Nash social welfare problem with subadditive valuations, using polynomial running time and a polynomial number of queries to a demand oracle for each agent’s valuation.

Aside from our general reduction and the ability to solve the Eisenberg-Gale relaxation with demand queries, the main component that we need here is an implementation of a Rounding Procedure for subadditive valuations, as described in Theorem 1. To our knowledge, there is only one such procedure known, which is rather intricate and forms the basis of Feige’s ingenious $1/2$ -approximation algorithm for maximizing social welfare with subadditive valuations [Fei09]. We use it here as a black-box, which can be described as follows.

Theorem 11.

For any $\epsilon>0$ , there is a polynomial-time algorithm, which given a fractional solution $(x_{i,S})$ of (Configuration LP) for an instance with subadditive valuations, produces a random allocation $(R_{i}:i\in\mathcal{A})$ such that for every agent, $R_{i}\subseteq S_{i}$ for some $S_{i},x_{i,S_{i}}>0$ , and

{\mathbb{E}}[v_{i}(R_{i})]\geq\left(\frac{1}{2}-\epsilon\right)V_{i},\mbox{ where }V_{i}=\sum_{S\subseteq\mathcal{I}}v_{i}(S)x_{i,S}.

For the proof, we refer the reader to Section 3.2.2 of [Fei09], Theorem 3.9 and the summary of its proof which shows that every player receives expected value at least $(\frac{1}{2}-\epsilon)V_{i}$ .

Now we are ready to prove Theorem 10.

Proof.

Considering Theorem 1, we want to show how to implement the Relaxation Solver and Rounding Procedure for subadditive valuations.

The Relaxation Solver can be obtained applying standard convex optimization techniques to the (Eisenberg-Gale Relaxation) relaxation. As we discuss in more detail in Appendix A, we can compute the values and supergradients of the objective function using demand queries, and obtain an optimal solution satisfying the assumption of Lemma 15 (with $f_{i}=v^{+}_{i}$ , $\alpha=1)$ , and hence

\sum_{i\in\mathcal{A}}\frac{v^{+}_{i}(\mathbf{x}^{*}_{i})}{v^{+}_{i}(\mathbf{x}_{i})}\leq 2|\mathcal{A}|

for every feasible solution $\mathbf{x}^{*}$ . Another way to interpret this condition is that for $V_{i}=v^{+}_{i}(\mathbf{x}_{i})$ and modified valuations defined as $w_{i}(S)=\frac{1}{V_{i}}v_{i}(S)$ , there is no feasible solution $\mathbf{x}^{*}$ achieving value $\sum_{i\in\mathcal{A}}w^{+}_{i}(\mathbf{x}^{*}_{i})>2|\mathcal{A}|$ . In particular, the social welfare optimum with the valuations $(w_{i}:i\in\mathcal{A})$ is at most $2|\mathcal{A}|$ . Hence, we satisfy the Relaxation Solver assumptions with $c=2$ .

Next, we implement the Rounding Procedure: Given a fractional solution $(x_{i,S})$ , Theorem 11 gives a procedure which returns a random allocation $(R_{i}:i\in\mathcal{A})$ such that ${\mathbb{E}}[v_{i}(R_{i})]\geq(\frac{1}{2}-\epsilon)V_{i}=(\frac{1}{2}-\epsilon)\sum_{S}x_{i,S}v_{i}(S)$ . This means that for the modified valuations, $w_{i}(S)=\frac{1}{V_{i}}v_{i}(S)$ , we have ${\mathbb{E}}[w_{i}(R_{i})]\geq\frac{1}{2}-\epsilon$ , and $\sum_{i\in\mathcal{A}}w_{i}(R_{i})\geq(\frac{1}{2}-\epsilon)|\mathcal{A}|$ . Hence, we satisfy the Rounding Procedure assumptions with $d=\frac{2}{1-2\epsilon}$ .

Finally, we apply Theorem 1 with $c=2$ and $d=\frac{2}{1-2\epsilon}$ . We obtain a constant-factor approximation algorithm for the Nash social welfare problem with subadditive valuations accessible via demand queries. (The constant factor ends up being $20000(c+1)d^{2}=375000$ for $\epsilon=0.1$ .) ∎

References

[AGSS17] Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash social welfare, matrix permanent, and stable polynomials. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017.
[AMGV18] 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 29th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2274–2290. SIAM, 2018.
[Bar05] Julius B Barbanel. The geometry of efficient fair division. Cambridge University Press, 2005.
[BBKS20] Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. Tight approximation algorithms for p-mean welfare under subadditive valuations. In 28th Annual European Symposium on Algorithms, ESA 2020, volume 173, pages 11:1–11:17, 2020.
[BCE⁺16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
[BKKN21] Siddharth Barman, Anand Krishna, Pooja Kulkarni, and Shivika Narang. Sublinear approximation algorithm for nash social welfare with XOS valuations. CoRR, abs/2110.00767, 2021.
[BKV18] 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.
[BS06] Nikhil Bansal and Maxim Sviridenko. The Santa Claus problem. In Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), pages 31–40, 2006.
[BT96] Steven J Brams and Alan D Taylor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996.
[CCG⁺18] 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), pages 25:1–17. Springer, 2018.
[CDG⁺17] Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex program duality, Fisher markets, and Nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), pages 459–460. ACM, 2017.
[CG15] Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), pages 371–380. ACM, 2015.
[CGM21] Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and efficient allocations under subadditive valuations. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5269–5276, 2021.
[DHHW23] Daniel Dadush, Christopher Hojny, Sophie Huiberts, and Stefan Weltge. A simple method for convex optimization in the oracle model. Mathematical Programmming, 2023.
[DNS10] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res., 35(1):1–13, 2010.
[Fei08] Uriel Feige. On allocations that maximize fairness. In SODA, volume 8, pages 287–293. Citeseer, 2008.
[Fei09] Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122–142, 2009.
[GHL⁺23] Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, and Jan Vondrák. Approximating nash social welfare by matching and local search. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1298–1310. ACM, 2023.
[GHM17] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Satiation in Fisher markets and approximation of Nash social welfare. arXiv preprint arXiv:1707.04428, 2017.
[GHM18] Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the Nash social welfare with budget-additive valuations. In Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2326–2340. SIAM, 2018.
[GHV20] Jugal Garg, Edin Husić, and László A. Végh. Approximating Nash social welfare under Rado valuations. arXiv preprint arXiv:2009.14793, 2020.
[GHV21] Jugal Garg, Edin Husić, and László Végh. Approximating nash social welfare under rado valuations. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1412–1425, 2021.
[GKK20] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash social welfare under submodular valuations through (un)matchings. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2673–2687, 2020.
[Kel97] Frank Kelly. Charging and rate control for elastic traffic. European transactions on Telecommunications, 8(1):33–37, 1997.
[KN79] Mamoru Kaneko and Kenjiro Nakamura. The Nash social welfare function. Econometrica: Journal of the Econometric Society, pages 423–435, 1979.
[LV21a] Wenzheng Li and Jan Vondrák. A constant-factor approximation algorithm for nash social welfare with submodular valuations. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 25–36. IEEE, 2021.
[LV21b] Wenzheng Li and Jan Vondrák. Estimating the nash social welfare for coverage and other submodular valuations. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1119–1130. SIAM, 2021.
[Mou04] Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
[Nas50] John F Nash. The bargaining problem. Econometrica: Journal of the econometric society, pages 155–162, 1950.
[Rot16] Jörg Rothe, editor. Economics and Computation, An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer, 2016.
[RW98] Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. CRC Press, 1998.
[Sch03] Gideon Schechtman. Concentration, results and applications. Handbook of the Geometry of Banach Spaces, (2):1603–1634, 2003.
[Tal89] Michel Talagrand. Isoperimetry and integrability of the sum of independent banach space valued random variables. Annals of Probability, 17:1546–1570, 1989.
[Tal95] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Etudes Sci.Publ. Math., 81:73–205, 1995.
[Var74] Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63–91, 1974.
[You95] H Peyton Young. Equity: in theory and practice. Princeton University Press, 1995.

Appendix A The Eisenberg-Gale Relaxation

We consider the following relaxation of the Nash Social Welfare problem similar to the relaxations in [GHV21, LV21a]. We remark that the application of (Eisenberg-Gale Relaxation) in the Nash Social Welfare algorithm excludes the items allocated in the initial matching; indeed we ignore those items for the analysis in this section.

$\displaystyle\max\quad$	$\displaystyle\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}_{i})$		(Eisenberg-Gale Relaxation)
	$\displaystyle\quad\sum_{i\in\mathcal{A}}x_{ij}\leq 1$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\quad x_{ij}\geq 0$	$\displaystyle\forall i\in\mathcal{A},j\in\mathcal{I}$

where $f_{i}$ is a suitable relaxation of the valuation function $v_{i}$ for each $i$ . In particular, we will use the concave extension, $f_{i}=v_{i}^{+}$ :

$\displaystyle v_{i}^{+}(\mathbf{x}_{i}):=$	$\displaystyle\max\sum_{S\subseteq\mathcal{I}}v_{i}(S)x_{i,S}:$		(Concave Extension)
	$\displaystyle\sum_{S\subseteq\mathcal{I}:j\in S}x_{i,S}\leq x_{ij}$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\ \ \sum_{S\subseteq\mathcal{I}}x_{i,S}=1$
	$\displaystyle\ \ x_{i,S}\geq 0$	$\displaystyle\forall S\subseteq\mathcal{I}$

Note that (Concave Extension) is a linear program. The dual LP to (Concave Extension) is

$\displaystyle v_{i}^{+}(\mathbf{x}_{i})=$	$\displaystyle\min q+\sum_{j\in\mathcal{I}}p_{j}x_{ij}:$		(Dual LP)
	$\displaystyle q+\sum_{j\in S}p_{j}\geq v_{i}(S)$	$\displaystyle\forall S\subseteq\mathcal{I}$
	$\displaystyle p_{j}\geq 0$	$\displaystyle\forall j\in\mathcal{I}.$

From here, we can see that $v^{+}_{i}(\mathbf{x}_{i})$ is a minimum over a collection of linear functions, and hence a concave function.

A.1 Solving the Eisenber-Gale Relaxation

Here we show how to solve the (Eisenberg-Gale Relaxation) using demand queries.

Lemma 12.

Given demand oracles for $v_{1},\cdots,v_{n}$ , an optimal solution $\mathbf{x}^{*}$ for (Eisenberg-Gale Relaxation) can be found within a polynomially small error in polynomial time. Moreover, the support of $\mathbf{x}^{*}$ has size polynomial in $n$ .

Since $v^{+}_{i}(\mathbf{x}_{i})$ is a nonnegative concave function, $\log v^{+}_{i}(\mathbf{x}_{i})$ is a concave function as well (wherever $v^{+}_{i}(\mathbf{x}_{i})>0$ ). If we implement the evaluation and supergradient oracles for $\log v^{+}_{i}(\mathbf{x}_{i})$ , then we can use standard techniques (see, e.g., [DHHW23]) to maximize $\sum_{i\in\mathcal{A}}\log v^{+}_{i}(\mathbf{x}_{i})$ over the convex polytope

P=\{\mathbf{x}\in{\mathbb{R}}_{+}^{\mathcal{I}\times\mathcal{A}}:\forall j\in\mathcal{I},\sum_{i\in\mathcal{A}}x_{ij}\leq 1\}.

The function $v^{+}_{i}(\mathbf{x}_{i})$ can be evaluated with polynomially many demand queries; this is well-known [Fei08] and holds because the demand oracle happens to be the separation oracle for (Dual LP). Hence we can also evaluate $\log v^{+}_{i}(\mathbf{x}_{i})$ . We focus here on the implementation of a supergradient oracle.

A supergradient of $\log v^{+}_{i}$ at a point $\mathbf{z}$ is any linear function $L_{i}(\mathbf{y})$ such that $L_{i}(\mathbf{z})=\log v^{+}_{i}(\mathbf{z})$ and $L_{i}(\mathbf{y})\geq\log v^{+}_{i}(\mathbf{y})$ everywhere. Given $\mathbf{z}$ , as a first step, we find a supergradient of $v^{+}_{i}$ itself: This can be done by solving the dual LP and finding $\alpha$ and $(p_{j}:j\in\mathcal{I})$ such that $v^{+}_{i}(\mathbf{z})=\alpha+\sum_{j\in\mathcal{I}}p_{j}z_{j}=\alpha+\mathbf{p}\cdot\mathbf{z}$ . Since $v^{+}_{i}(\mathbf{y})$ for every $\mathbf{y}$ is the minimum over such linear functions, we also have $v^{+}_{i}(\mathbf{y})\leq\alpha+\mathbf{p}\cdot\mathbf{y}$ for all $\mathbf{y}$ . Hence $\alpha+\mathbf{p}\cdot\mathbf{y}$ is the desired supergradient at $\mathbf{z}$ .

Next, we compute the gradient of $\log(\alpha+\mathbf{p}\cdot\mathbf{y})$ with respect to $\mathbf{y}$ :

\nabla\log(\alpha+\mathbf{p}\cdot\mathbf{y})=\frac{\nabla(\alpha+\mathbf{p}\cdot\mathbf{y})}{\alpha+\mathbf{p}\cdot\mathbf{y}}=\frac{\mathbf{p}}{\alpha+\mathbf{p}\cdot\mathbf{y}}.

We claim that the linear approximation of $\log(\alpha+\mathbf{p}\cdot\mathbf{y})$ obtained by evaluating this gradient at $\mathbf{z}$ ,

L_{i}(\mathbf{y})=\log(\alpha+\mathbf{p}\cdot\mathbf{z})+(\mathbf{y}-\mathbf{z})\cdot\nabla(\log(\alpha+\mathbf{p}\cdot\mathbf{y}))|_{\mathbf{z}}=(\alpha+\mathbf{p}\cdot\mathbf{z})+(\mathbf{y}-\mathbf{z})\cdot\frac{\mathbf{p}}{\alpha+\mathbf{p}\cdot\mathbf{z}}

is a valid supergradient for $\log v^{+}_{i}(\mathbf{y})$ at $\mathbf{z}$ . Indeed, we have $\log v^{+}_{i}(\mathbf{z})=\log(\alpha+\mathbf{p}\cdot\mathbf{z})=L_{i}(\mathbf{z})$ , and for all $\mathbf{y}$ ,

\log v^{+}_{i}(\mathbf{y})\leq\log(\alpha+\mathbf{p}\cdot\mathbf{y})\leq(\alpha+\mathbf{p}\cdot\mathbf{z})+(\mathbf{y}-\mathbf{z})\cdot\nabla(\log(\alpha+\mathbf{p}\cdot\mathbf{y}))|_{\mathbf{z}}=L_{i}(\mathbf{y}).

where the second inequality follows from the concavity of $\log(\alpha+\mathbf{p}\cdot\mathbf{y})$ .

Hence, (Eisenberg-Gale Relaxation) can be solved in polynomial time, within a polynomially small error, using standard convex optimization techniques [DHHW23]. In particular, we can find a point $\mathbf{x}$ such that $\sum_{i\in\mathcal{A}}\log v^{+}_{i}(\mathbf{x}^{*}_{i})\leq\sum_{i\in\mathcal{A}}\log v^{+}_{i}(\mathbf{x}_{i})+\epsilon$ for every feasible solution $\mathbf{x}^{*}$ .

Finally, let’s explain why the solution can be assumed to have polynomially bounded support. Given a fractional solution $x_{ij}$ (which has obviously polynomially bounded support), for each agent $i$ , using demand queries we also obtain a solution of (Dual LP) certifying the value of $v^{+}_{i}(\mathbf{x}_{i})$ . By complementary slackness, there is a matching primal solution of (Eisenberg-Gale Relaxation) which has nonzero variables corresponding to the tight constraints in (Dual LP) that define the dual solution. Since the dimension of (Dual LP) is polynomial, the number of such tight constraints is also polynomial. Hence we can assume that the number of nonzero variables in (Eisenberg-Gale Relaxation) is polynomial.

A.2 Properties of the optimal solution

Consider now the (Eisenberg-Gale Relaxation) in a general form, with objective functions $f_{i}$ (which could be equal to $v^{+}_{i}$ or perhaps some other extension of $v_{i}$ ).

$\displaystyle\max\quad$	$\displaystyle\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}_{i})$		(Eisenberg-Gale Relaxation)
	$\displaystyle\quad\sum_{i\in\mathcal{A}}x_{ij}\leq 1$	$\displaystyle\forall j\in\mathcal{I}$
	$\displaystyle\quad x_{ij}\geq 0$	$\displaystyle\forall i\in\mathcal{A},j\in\mathcal{I}$

Suppose that $\mathbf{x}$ is an optimal solution of this relaxation. We will need the following property, which is also stated in [GHV20] in the context of general concave valuations (Lemma 4.1 in [GHV20]). Our proof here is much simpler. First, we consider the case of differentiable concave $f_{i}$ which makes the proof cleaner. (Recall however that $v^{+}_{i}$ is not differentiable everywhere.)

Lemma 13.

For an optimal solution $\mathbf{x}$ of (Eisenberg-Gale Relaxation) with differentiable nonnegative monotone concave functions $f_{i}$ , and any other feasible solution $\mathbf{x}^{*}$ , we have

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}\leq|\mathcal{A}|.

Proof.

Since $f_{i}(\mathbf{x})$ is a concave function, we have

f_{i}(\mathbf{x}^{*}_{i})\leq f_{i}(\mathbf{x}_{i})+(\mathbf{x}^{*}_{i}-\mathbf{x}_{i})\cdot\nabla f_{i}(\mathbf{x}_{i}).

From here, we get

\displaystyle\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}

\displaystyle\leq\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}_{i})+(\mathbf{x}^{*}_{i}-\mathbf{x}_{i})\cdot\nabla f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}=|\mathcal{A}|+\sum_{i\in\mathcal{A}}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i})\cdot\nabla(\log f_{i}(\mathbf{x}_{i}))\leq|\mathcal{A}|

using the fact that $\mathbf{x}^{*}$ is feasible and $\mathbf{x}$ is an optimum for the objective function $\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}_{i})$ . ∎

To deal with a more general situation where $f_{i}$ is not necessarily differentiable, and we don’t find an exact optimum, we prove a robust version of this lemma.

Lemma 14.

Let $f_{i}:[0,1]^{\mathcal{I}}\to{\mathbb{R}}$ for each $i\in\mathcal{A}$ be nonnegative, monotone and concave. For $\epsilon>0$ , let $\mathbf{x}$ be an $\epsilon^{4}$ -approximate solution of (Eisenberg-Gale Relaxation), in the sense that for every other feasible solution $\mathbf{x}^{\prime}$ ,

\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}^{\prime})\leq\sum_{i\in\mathcal{A}}(\log f_{i}(\mathbf{x})+\epsilon^{4}).

(1)

And suppose further that that $y_{ij}\geq\epsilon$ for all $i,j$ , Then for every feasible solution $\mathbf{x}^{*}$ , we have

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}\leq(1+2\epsilon)|\mathcal{A}|.

Note that we must necessarily have $\epsilon\leq 1/|\mathcal{A}|$ , because $1\geq\sum_{i\in\mathcal{A}}x_{ij}\geq\epsilon|\mathcal{A}|$ .

Proof.

Let $\mathbf{x}$ satisfy the assumptions of the lemma. For any feasible $\mathbf{x}^{*}$ and $T\geq 1$ , using the concavity of $f_{i}$ , we can write

f_{i}(\mathbf{x}^{*}_{i})-f_{i}(\mathbf{x}_{i})\leq T(f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))-f_{i}(\mathbf{x}_{i})).

From here,

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})-f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}\leq T\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))-f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}.

Note that since $y_{ij}\geq\epsilon$ , we have $\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i})\leq\mathbf{x}_{i}+\frac{1}{T}{\bf 1}\leq(1+\frac{1}{T\epsilon})\mathbf{x}_{i}$ . Also, $f_{i}(0)\geq 0$ , so by monotonicity and concavity, $f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))\leq f_{i}((1+\frac{1}{T\epsilon})\mathbf{x}_{i})\leq(1+\frac{1}{T\epsilon})f_{i}(\mathbf{x}_{i})$ . Similarly, $f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))\geq f_{i}(\mathbf{x}_{i}-\frac{1}{T}{\bf 1})\geq(1-\frac{1}{T\epsilon})f_{i}(\mathbf{x}_{i})$ . Hence the ratio $r_{i}=\frac{f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))-f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}$ is at most $\delta=\frac{1}{T\epsilon}$ in absolute value, and we can use the following elementary approximation:

r_{i}-\delta^{2}\leq\log(1+r_{i})\leq r_{i}.

Plugging into the inequality above, we obtain

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})-f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}\leq T\sum_{i\in\mathcal{A}}r_{i}\leq T\sum_{i\in\mathcal{A}}(\delta^{2}+\log(1+r_{i}))=\frac{|\mathcal{A}|}{T\epsilon^{2}}+T\sum_{i\in\mathcal{A}}\log\frac{f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))}{f_{i}(\mathbf{x}_{i})}.

Applying the assumption of the lemma to the feasible solution $\mathbf{x}^{\prime}=\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i})$ , we have $\sum_{i\in\mathcal{A}}\log\frac{f_{i}(\mathbf{x}_{i}+\frac{1}{T}(\mathbf{x}^{*}_{i}-\mathbf{x}_{i}))}{f_{i}(\mathbf{x}_{i})}\leq\epsilon^{4}|\mathcal{A}|,$ which gives

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}=|\mathcal{A}|+\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})-f_{i}(\mathbf{x}_{i})}{f_{i}(\mathbf{x}_{i})}\leq|\mathcal{A}|+\frac{|\mathcal{A}|}{T\epsilon^{2}}+T\epsilon^{4}|\mathcal{A}|.

We set $T$ to equate the last two terms: $T=1/\epsilon^{3}$ , which gives the statement of the lemma. ∎

Corollary 15.

Given a value oracle and a supergradient oracle for each $f_{i}$ , for any constant $\alpha>0$ , we can find a solution $\mathbf{x}$ of (Eisenberg-Gale Relaxation) in polynomial time such that for any feasible solution $\mathbf{x}^{*}$ ,

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}\leq(1+\alpha)|\mathcal{A}|.

Proof.

For $\epsilon>0$ (to be chosen at the end), we run a convex optimization algorithm on (Eisenberg-Gale Relaxation) with the additional constraint that $x_{ij}\geq\epsilon$ , to obtain a solution $\mathbf{x}$ such that for any feasible $\mathbf{x}^{\prime}$ satisfying the same constraint, we have

\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}_{i})\geq\sum_{i\in\mathcal{A}}\log f_{i}(\mathbf{x}^{\prime})-\epsilon^{4}n.

By Lemma 14, this solution also satisfies

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{\prime}_{i})}{f_{i}(\mathbf{x}_{i})}\leq(1+2\epsilon)n.

Finally, note that every feasible solution $\mathbf{x}^{*}$ of (Eisenberg-Gale Relaxation) can be modified to obtain a feasible solution $\mathbf{x}^{\prime}=(1-\epsilon n)\mathbf{x}^{*}+\epsilon n\cdot\frac{1}{n}{\bf 1}$ which satisfies the constraint $x^{\prime}_{ij}\geq\epsilon$ , and we have $f_{i}(\mathbf{x}^{\prime}_{i})\geq(1-\epsilon n)f_{i}(\mathbf{x}^{*}_{i})$ for every $i\in\mathcal{A}$ . Therefore, our solution also satisfies

\sum_{i\in\mathcal{A}}\frac{f_{i}(\mathbf{x}^{*}_{i})}{f_{i}(\mathbf{x}_{i})}\leq\frac{(1+2\epsilon)n}{1-\epsilon n}.

For $\epsilon=\frac{\alpha}{2+(1+\alpha)n}$ , we obtain the desired statement. ∎

Appendix B Rematching lemmas

Here we prove the rematching lemmas from Section 2.2. These are essentially identical to lemmas in previous work on Nash social welfare, only reformulated in a way convenient for our presentation. We give self-contained proofs here for completeness.

Proof of Lemma 8.

Suppose that $S^{*}_{i}=H^{*}_{i}\cup T^{*}_{i}$ where $H^{*}_{i}\subseteq\mathcal{H}$ and $T^{*}_{i}\subseteq\mathcal{I}^{\prime}$ . We define a matching $\pi$ as follows: For each nonempty $H^{*}_{i}$ , let $\pi(i)$ be the item of maximum value (as a singleton) in $H^{*}_{i}$ . For $H^{*}_{i}=\emptyset$ , let $\pi(i)$ be an arbitrary item in $\mathcal{H}$ not selected as $\pi(i^{\prime})$ for some other agent. (Since $|\mathcal{H}|=|\mathcal{A}|$ , we can always find such items.) Recall that $\mathcal{A}^{\prime}$ are the agents who get positive value from $\mathcal{I}^{\prime}$ ; in particular, we can assume $T^{*}_{i}=\emptyset$ for $i\notin\mathcal{A}^{\prime}$ . Then we have, using monotonicity and subadditivity

	$\displaystyle\prod_{i\in\mathcal{A}}\frac{v_{i}(S^{*}_{i})}{\max\{V_{i},v_{i}(\pi(i))\}}$	$\displaystyle\leq$	$\displaystyle\prod_{i\in\mathcal{A}}\frac{v_{i}(T^{}_{i})+v_{i}(H^{}_{i})}{\max\{V_{i},v_{i}(\pi(i))\}}\leq\prod_{i\in\mathcal{A}}\frac{v_{i}(T^{}_{i})+\|H^{}_{i}\|v_{i}(\pi(i)))}{\max\{V_{i},v_{i}(\pi(i))\}}$
		$\displaystyle\leq$	$\displaystyle\prod_{i\in\mathcal{A}^{\prime}}\left(\frac{v_{i}(T^{}_{i})}{V_{i}}+\|H^{}_{i}\|\right)\prod_{i\in\mathcal{A}\setminus\mathcal{A}^{\prime}}\|H^{*}_{i}\|.$

Here we use the AMGM inequality:

\displaystyle\left(\prod_{i\in\mathcal{A}^{\prime}}\left(\frac{v_{i}(T^{*}_{i})}{V_{i}}+|H^{*}_{i}|\right)\prod_{i\in\mathcal{A}\setminus\mathcal{A}^{\prime}}|H^{*}_{i}|\right)^{1/|\mathcal{A}|}\leq\frac{1}{|\mathcal{A}|}\left(\sum_{i\in\mathcal{A}^{\prime}}\left(\frac{v_{i}(T^{*}_{i})}{V_{i}}+|H^{*}_{i}|\right)+\sum_{i\in\mathcal{A}\setminus\mathcal{A}^{\prime}}|H^{*}_{i}|\right)\leq c+1

where the last inequality is by assumption and the fact that $\sum_{i\in\mathcal{A}}|H^{*}_{i}|\leq|\mathcal{H}|=|\mathcal{A}|$ . ∎

Proof of Lemma 9.

Let $\tilde{A}=\{i\in\mathcal{A}:W_{i}<\max\{v(\pi(i)),\nu_{i}\}$ . We define a directed bipartite graph $B$ between $\tilde{A}$ and $\mathcal{H}$ , with two types of edges: $E_{\tau}=\{(\tau(i),i):i\in\tilde{A}\}$ and $E_{\pi}=\{(i,\pi(i):i\in\tilde{A}\}$ . We also define:

•

$A_{\nu}=\{i\in\tilde{A}:\nu_{i}>v_{i}(\pi(i))\}$ ,
•

$A_{\tau}=A_{\nu}\cup\{i\in\tilde{A}:\exists\mbox{ directed path in }B\mbox{ from }i\mbox{ to }A_{\nu}\}$ ,
•

$A_{\pi}=\tilde{A}\setminus A_{\tau}$ .

We define a matching $\rho$ as follows;

•

For $i\in A_{\tau}$ , $\rho(i):=\tau(i)$ ,
•

For $i\in A_{\pi}$ , $\rho(i):=\pi(i)$ .
•

For $i\notin\tilde{A}$ , we define $\rho(i)$ arbitrarily, to make $\rho$ a matching.

First, observe that this is indeed a matching: If it was the case that $\tau(i)=\pi(i^{\prime})=j$ for some $i\in A_{\tau},i^{\prime}\in A_{\pi}$ , then we would have edges $(i^{\prime},j)$ and $(j,i)$ in the graph, and since there is a directed path from $i$ to $A_{\nu}$ ( $i\in A_{\tau}$ ), there would also be a directed path from $i^{\prime}$ to $A_{\nu}$ , contradicting the fact that $i^{\prime}\in A_{\pi}$ . Hence, $\rho$ is a matching.

Also, it’s easy to see that for every

Next, we analyze the value guarantee for $\rho$ :

\prod_{i\in\mathcal{A}}\max\{W_{i},v_{i}(\rho(i))\}\geq\prod_{i\in\mathcal{A}\setminus\tilde{A}}W_{i}\prod_{i\in\tilde{A}}v_{i}(\rho(i))=\prod_{i\in\mathcal{A}\setminus\tilde{A}}W_{i}\prod_{i\in A_{\tau}}v_{i}(\tau(i))\prod_{i\in A_{\pi}}v_{i}(\pi(i)).

We claim that $\prod_{i\in A_{\tau}}v_{i}(\tau(i))\geq\prod_{i\in A_{\nu}}\nu_{i}\prod_{i\in A_{\tau}\setminus A_{\nu}}v_{i}(\pi(i))$ . Observe that the vertices of $A_{\tau}$ can be covered disjointly by directed paths that terminate in $A_{\nu}$ (from each vertex of $A_{\tau}$ , there is such a path and it is also unique, because the in-degrees / out-degrees in the graph are at most $1$ ). Let $P$ denote the $A_{\tau}$ -vertices on some directed path like this, and let $s$ be its last vertex (in $A_{\nu}$ ). If it was the case that $\prod_{i\in P}v_{i}(\tau(i))<\nu_{s}\prod_{i\in P\setminus\{s\}}v_{i}(\pi(i))$ , then we could modify the matching $\tau$ by swapping its edges on $P$ for the $\pi$ -edges from $P\setminus\{s\}$ , and finally an element of value $\nu_{i}$ for $s$ (since this item is outside of $\mathcal{H}$ and hence available). This would increase the value of the matching $\tau$ , which was chosen to be optimal, so this cannot happen.

It follows that $\prod_{i\in P}v_{i}(\tau(i))\geq\nu_{s}\prod_{i\in P\setminus\{s\}}v_{i}(\pi(i))$ for every maximal directed path terminating in $A_{\nu}$ , and since these paths cover $A_{\tau}$ disjointly, by combining all these inequalities we obtain

\prod_{i\in A_{\tau}}v_{i}(\tau(i))\geq\prod_{i\in A_{\nu}}\nu_{i}\prod_{i\in A_{\tau}\setminus A_{\nu}}v_{i}(\pi(i)).

Substituting this into the inequality above,

\prod_{i\in\mathcal{A}}\max\{W_{i},v_{i}(\rho(i))\}\geq\prod_{i\in\mathcal{A}\setminus\tilde{A}}V_{i}\prod_{i\in A_{\nu}}\nu_{i}\prod_{i\in A_{\tau}}v_{i}(\pi(i))=\prod_{i\in\mathcal{A}}\max\{W_{i},\nu_{i},v_{i}(\pi(i))\}.

∎

Appendix C Concentration of subadditive functions

Let us start with a simple lower bound on the expected value of a random set with independently sampled elements.

Lemma 16.

If $f:2^{M}\to{\mathbb{R}}_{+}$ is a monotone subadditive function and $R$ is a random subset of $S$ where each element appears independently with probability $1/k$ , $k\geq 1$ integer, then

{\mathbb{E}}[f(R)]\geq\frac{1}{k}f(S).

Proof.

Consider a random coloring of $S$ , where every element $j\in S$ receives independently a random color $c(j)\in[k]$ . Defining $S_{\ell}=\{j\in S:c(j)=\ell\}$ , we see that each set $S_{\ell}$ has the same distribution as the set $R$ in the Lemma. Therefore,

{\mathbb{E}}[f(R)]={\mathbb{E}}[f(S_{1})]=\ldots={\mathbb{E}}[f(S_{k})]={\mathbb{E}}\left[\frac{1}{k}\sum_{\ell=1}^{k}f(S_{\ell})\right]\geq\frac{1}{k}f(S)

by subadditivity. ∎

This property is similar to the properties of submodular or self-bounding functions, which satisfy very convenient concentration bounds (similar to additive functions). Unfortunately, the same bounds are not true for subadditive functions; however, some concentration results can be recovered with a loss of certain constant factors.

Here we state a powerful concentration result presented by Schechtman [Sch03], based on the “ $q$ -point control” concentration inequality by Talagrand [Tal89, Tal95]. We state it here in a simplified form suitable for our purposes.

Theorem 17.

Let $f:2^{M}\to{\mathbb{R}}_{+}$ be a monotone subadditive function, where $f(\{i\})\leq 1$ for every $i\in M$ . Then for any real $a>0$ and integers $k,q\geq 1$ , and a random set $R$ from a product distribution,

\Pr[f(R)\geq(q+1)a+k]\ (\Pr[f(R)\leq a])^{q}\leq\frac{1}{q^{k}}.

This statement can be obtained from Corollary 12 in [Sch03] by extending the definition of $f$ to $\Omega^{*}=\bigcup_{I\subset M}2^{I}$ simply by saying $f_{I}(S)=f(S)$ for all $S\subseteq I$ . Also, we identify $2^{I}$ with $\{0,1\}^{I}$ in a natural way. Assuming $f(\{i\})\leq 1$ means that $0\leq f(S+i)-f(S)\leq 1$ for any set $S$ , by monotonicity and subadditivity. Therefore, $f$ is $1$ -Lipschitz with respect to the Hamming distance, as required in [Sch03]. The statement holds for any product distribution, i.e. a random set $R$ where elements appear independently.

Note that Theorem 17 refers to tails on both sides and hence is more convenient to use with the median of $f$ than the expectation. The next lemma shows that this is not a big issue, since the theorem also implies that the median and expectation must be within a constant factor.

Definition 18.

We define the median of a random variable $Z$ as any number $\mbox{\sf med}(Z)=m$ such that

\Pr[Z\leq m]\geq 1/2,\ \ \ \Pr[Z\geq m]\geq 1/2.

For any nonnegative variable, obviously ${\mathbb{E}}[Z]\geq\frac{1}{2}\mbox{\sf med}(Z)$ . For subadditive functions of independent random variables, we also get a bound in the opposite direction.

Lemma 19.

Let $f:2^{M}\to{\mathbb{R}}_{+}$ be a monotone subadditive function, where $f(\{i\})\leq 1$ for every $i\in M$ . Then for a random set $R$ from a product distribution,

{\mathbb{E}}[f(R)]\leq 5(\mbox{\sf med}(f(R))+1).

Proof.

Let $a=\mbox{\sf med}(f(R))$ be the median. We apply Theorem 17 with $k=q+1,q\geq 3$ :

\Pr[f(R)\geq(q+1)(a+1)]\leq\frac{2^{q}}{q^{q+1}}\leq\left(\frac{2}{3}\right)^{q}.

We can bound the expectation as follows:

{\mathbb{E}}[f(R)]\leq 4(a+1)+(a+1)\sum_{q=3}^{\infty}\Pr[f(R)>(q+1)(a+1)]\leq 4(a+1)+(a+1)\sum_{q=3}^{\infty}\left(\frac{2}{3}\right)^{q}<5(a+1).

∎

Hence, we obtain the following as a corollary of Theorem 17 and Lemma 19. For convenience, we also introduce a parameter $\nu>0$ as an upper bound on singleton values.

Theorem 20.

Let $f:2^{M}\to{\mathbb{R}}_{+}$ be a monotone subadditive function, where $f(\{i\})\leq\nu$ , $\nu>0$ , for every $i\in M$ . Then for any integers $k,q\geq 1$ , and a random set $R$ where elements appear independently,

\Pr\left[f(R)\leq\frac{{\mathbb{E}}[f(R)]}{5(q+1)}-\frac{(k+1)\nu}{q+1}\right]\leq\left(\frac{2}{q^{k}}\right)^{1/q}.

Proof.

Assume first $g$ is a function satisfying the assumptions with $\nu=1$ . We use Theorem 17 with parameter $a=(\mbox{\sf med}(g)-k)/(q+1)$ . Note that $\Pr[g(R)\geq(q+1)a+k]=\Pr[g(R)\geq\mbox{\sf med}(g)]=1/2$ . Hence, Theorem 17 gives

\frac{1}{2}\cdot(\Pr[g(R)\leq a])^{q}\leq\frac{1}{q^{k}}.

From Lemma 19, we have $a=(\mbox{\sf med}(g)-k)/(q+1)\geq(\frac{1}{5}{\mathbb{E}}[g(R)]-1-k)/(q+1)$ which implies the statement for $\nu=1$ :

\Pr\left[g(R)\leq\frac{{\mathbb{E}}[g(R)]}{5(q+1)}-\frac{k+1}{q+1}\right]\leq\left(\frac{2}{q^{k}}\right)^{1/q}.

For a function $f$ satisfying the assumptions for $\nu>0$ , we apply this inequality to the function $g(R)=\frac{1}{\nu}f(R)$ , to obtain the statement of the lemma. ∎

A constant factor approximation for Nash social welfare with subadditive valuations

Abstract

1 Introduction

1.1 Preliminaries

Classes of valuation functions

Oracle access.

1.2 Prior work

1.3 Our results and techniques

Theorem.

Reducing Nash Welfare to Rounding of Configuration LP

Paper organization.

2 Optimizing NSW via relaxation and rounding for social welfare

Theorem 1.

NSW Algorithm Template.

2.1 Initial Matching

Lemma 2.

Proof.

2.2 Relaxation Solver

2.3 Set Splitting

Lemma 3.

Proof.

SetSplitting(𝐱\mathbf{x}).

2.4 Iterated Rounding

Lemma 4.

Proof.

Lemma 5.

Proof.

Lemma 6.

Proof.

Lemma 7.

Proof.

2.5 Rematching and finishing the analysis

Lemma 8 (matching extension).

Lemma 9 (rematching).

3 Nash social welfare with subadditive valuations

Theorem 10.

Theorem 11.

Proof.

References

Appendix A The Eisenberg-Gale Relaxation

A.1 Solving the Eisenber-Gale Relaxation

Lemma 12.

A.2 Properties of the optimal solution

Lemma 13.

Proof.

Lemma 14.

Proof.

Corollary 15.

Proof.

Appendix B Rematching lemmas

Proof of Lemma 8.

Proof of Lemma 9.

Appendix C Concentration of subadditive functions

Lemma 16.

Proof.

Theorem 17.

Definition 18.

Lemma 19.

Proof.

Theorem 20.

Proof.

SetSplitting( $\mathbf{x}$ ).