New Convex Programming Technique for Nash Social Welfare and Scheduling

Our main contribution is a new convex program for the weighted Nash social welfare (NSW) problem, which also achieves an $e^{1/e}$-approximation using the rounding algorithm of Feng and Li [16]. In contrast to the exponential-size configuration LP of [16], our convex program can be converted into a compact linear program of polynomial size, incurring only an additive loss of $\ln (1+ϵ)$ in the objective value. So, it can be solved directly with the loss using standard LP solvers, without resorting to the ellipsoid method and a dual separation oracle.

More interestingly, we show that in the unweighted case, our program is equivalent to the convex program CP(f-SR) introduced by Cole and Gkatzelis [11] that captures the Fisher market equilibrium with restricted spending. The program is defined later in Section 2.3. This yields a constructive proof that the integrality gap of this convex program is at most $e^{1/e}$. Combined with the $e^{1/e}$ lower bound by [11], this shows that the integrality gap of CP(f-SR) is exactly $e^{1/e}$.

With a slight modification of our analysis, we obtain a simple proof of the $e^{1/e}$ EF1 gap for the unweighted NSW problem with identical agents, which was proved by Barman, Krishnamurthy and Vaish [5]. Our proof avoids the sequence of adjustment steps.

Finally, we demonstrate that our convex programming technique naturally extends to two unrelated machine scheduling problems: one with the objective of minimizing the $L_q$ norm of machine loads, and another with the objective of minimizing weighted completion time when all jobs have the same Smith ratio. The known results [22, 24] for both problems use configuration LPs and the rounding algorithm of [34]. Similarly, we show that our simple convex programs are sufficient to recover the same approximation ratios as proved in [22, 24]. In particular, for the $\frac{1+\sqrt{2}}{2}$ approximation ratio for the weighted completion time problem in [24], we obtain a simpler analysis.

As in [16], we take the logarithm of the weighted Nash social welfare as the objective of our convex program relaxation. Specifically, we design a concave function $f_i:{[0,1]}^M\to {ℝ}_{\ge 0}$ for each agent $i\in N$, and aim to maximize ${\sum }_{i\in N}{w}_i{f}_i(x_i)$, where $x_i\in {[0,1]}^M$ denotes the fractional allocation of items to agent $i$.

The strongest choice for $f_i$ is the concave closure of the discrete function mapping $x_i\in {\{0,1\}}^M$ to $\ln {\sum }_j{v}_{ij}{x}_{ij}$. This corresponds to the configuration LP introduced by Feng and Li [16], where $f_i(x_i)$ is defined as the maximum of ${\sum }_{S\subseteq M}{\alpha }_S\ln v_i(S)$ over all convex combination decompositions ${\sum }_{S\subseteq M}{\alpha }_S{\chi }^S$ of $x_i$, where ${\chi }^S\in {\{0,1\}}^M$ is the indicator vector for $S$.

On the opposite side, if all items are assumed to be infinitely divisible, allowing configuration to contain portions of items, then $f_i(x_i)$ is maximized when all configurations have the same value. In this case, the function simplifies to $f_i(x_i)=\ln {\sum }_j{v}_{ij}{x}_{ij}$, which preserves the original formula but extends its domain to ${[0,1]}^M$.

Our approach lies between these two extremes. We only treat the largest 1 fractional item of maximum value $v_{ij}$ in $x_i$ as indivisible, while all remaining items are treated as divisible. Under this assumption, the optimal decomposition of items into configurations is given as follows: each configuration contains exactly one indivisible item, and the divisible items are allocated via a water-filling procedure. Then $f_i$ is defined as the average logarithm of the value of these configurations. We show that our $f_i$ is concave by expressing it as the minimum of linear functions. This is sufficient to recover the $e^{1/e}$ approximation factor using the rounding algorithm of [16], as in the worst instance, only the largest 1 fractional item is indivisible.

To show the equivalence of our convex program and that of [11] via market equilibrium, we establish a correspondence between whether items that are covered by water in the water filling procedure defining $f_i$’s, and items whose market prices are at most 1. Thanks to the uniform weight vector, this classification of items is the same for all agents. This uniformity is why the convex program of [11] applies only to the unweighted case.

In both the analysis of our rounding algorithm and our simplified proof of the EF1 gap, we define a liquidization operation that converts an item into arbitrarily small items with the same total value, this operation preserves total values but allows us to treat the liquidized items as divisible in the analysis. In the EF1-gap proof, we focus on the agent receiving the smallest value, say $\psi$. We then liquidize items of total value exactly $\psi$ for every agent, leaving only a portion of the largest item unliquidized. This transformation can only increase the gap. In the optimal solution, the liquidized items are allocated using the water-filling procedure. The remaining task of analyzing the gap between our solution and the optimal one is straightforward.

A more general function family that has been studied for the NSW problem is submodular functions. In contrast to the additive valuation function setting, each agent $i\in N$ is associated with a monotone submodular valuation function $v_i:2^M\to {ℝ}_{\ge 0}$, and the goal remains to find an allocation $\rho :M\to N$ that maximizes ${\prod }_{i\in N}{v}_i{\left({\rho }^{-1}(i)\right)}^{w_i}$. As in the additive case, we have the unweighted submodular NSW problem, where all agents have weights $1/n$, and the weighted submodular NSW problem, where the weight vector $w$ can be any vector in ${[0,1]}^N$ satisfying ${\sum }_{i\in N}{w}_i=1$.

In the unweighted case, the current best-known inapproximability for submodular NSW is $e/(e-1)\approx 1.582$, proved by Garg, Kulkarni and Kulkarni [19], even when the number of agents is a constant.

Algorithmically, the first $O(1)$-approximation for unweighted submodular NSW was obtained by Li and Vondrák [29] via convex programming, with an approximation ratio of $e^3/{(e-1)}^2$. Subsequently, Garg, Husic, Li, Végh and Vondrák [18] introduced an elegant local-search method that improved the approximation ratio to $4$ for the unweighted case. The same framework also yields an $O(n{w}_{\max })$-approximation for the weighted case [18], where $w_{\max }={\max }_{i\in N}{w}_i$.

Whether one can obtain an $O(1)$-approximation remained open. This was resolved by Feng, Hu, Li and Zhang [14], who developed a $233$-approximation based on the configuration LP from [16], giving the first constant-factor approximation for the weighted case. Very recently, Bei, Feng, Hu, Li and Zhang [6] significantly advanced this line of work by presenting a $3.56$-approximation, simultaneously improving the best-known ratios for both weighted and unweighted submodular NSW. They solve the same configuration LP via a stronger separation oracle that loses an $e/(e-1)$ factor only on small items, and then round the solution using a new bipartite multigraph construction to achieve the improved constant.

Throughout, we shall simply refer to the NSW problems with additive valuations as unweighted/weighted NSW problems, as they are our focuses of the paper.

For the unrelated machine scheduling problem with the objective of minimizing the $L_q$ norm of machine loads ($q\ge 1$), Im and Li [22] obtained an approximation ratio of $O_q(1)$-approximation algorithm, using a time-index LP relaxation and the Shmoys-Tardos rounding algorithm [34]. This framework improves upon some earlier results [2, 3, 25]. In particular, their approximation ratio for $q=2$ is $\sqrt{4/3}\le 1.155$.

The unrelated machine weighted completion time problem has been extensively studied in the literature. Following a sequence of work [20, 22, 23], Li [28] gave the current best approximation ratio of $1.36+ϵ$ for the problem. The case we are interested is when all jobs have the same Smith ratios across all machines, for which Kalaitzis, Svensson and Tarnawski [24] gave a $\frac{1+\sqrt{2}}{2}$-approximation. This is also based on the Shmoys-Tardos rounding algorithm, along with the configuration LP relaxation for the problem.

For the weighted additive Nash Social Welfare (NSW) problem, it is convenient for us to avoid agent-item pairs $ij$ with $0$ value. So in our definition of the problem, we are given a set $N$ of $n$ agents, each $i\in N$ with a weight $w_i\in (0,1]$ subject to ${\sum }_{i\in N}{w}_i=1$, a set $M$ of $m$ items, a set $E\subseteq N\times M$ of edges, along with a value $v_{ij}\in {ℝ}_{>0}$ for every $ij\in E$. We assume every $i\in N$ or $j\in M$ is incident to at least one edge in $E$. Let $M_i:=\{j\in M:ij\in E\}$ for every $i\in N$ and $N_j=\{i\in N:ij\in E\}$ for every $j\in M$. Our goal is to find an allocation $\rho :M\to N$ such that $\rho (j)j\in E$ for every $j\in M$, so as to maximize ${\prod }_{i\in N}{v}_i{({\rho }^{-1}(i))}^{w_i}$, where we use $v_i(M^{\prime }):={\sum }_{j\in M^{\prime }}{v}_{ij}$ for every $i\in N$ and $M^{\prime }\subseteq M_i$. In the unweighted Nash Social Welfare problem, we have $w_i=\frac{1}{n}$ for every $i\in N$.

We shall consider the following general unrelated machine scheduling problem. There is a set $M$ of $m$ machines, a set $J$ of $n$ jobs, a size $p_{ij}\in {ℝ}_{>0}$ for every $i\in M$ and $j\in J$. We are given an increasing convex function $\theta :{ℝ}_{\ge 0}\to {ℝ}_{\ge 0}$ with $\theta (0)=0$. Our goal is to find an allocation $\rho :J\to M$ so as to minimize ${\sum }_{i\in M}\theta ({\text{load}}_i)$, where ${\text{load}}_i:=q_i({\rho }^{-1}(i))$ and $q_i(J^{\prime }):={\sum }_{j\in J^{\prime }}{p}_{ij}$ for every $J^{\prime }\subseteq J$. We call the problem the unrelated machine scheduling problem with ${\sum }_{i\in M}\theta ({\text{load}}_i)$ objective.¹¹1We remark the notation change from NSW problems to scheduling problems. In both settings we need to allocate some objects to some players. $M$ denotes the objects (items) in NSW problems, and players (machines) in scheduling problems. We always have $m=|M|$. $n$ is the number of players ($n=|N|$) in NSW problems, and number of objects ($n=|J|$) in scheduling problems. When $\theta (x)=x^q$ for $q\ge 1$, the objective becomes the $L_q$ norm, after taking the $q$-th root of the objective.

In the unrelated machine scheduling with weighted completion time objective and uniform Smith ratios, we are given $M,m,J,n$ and ${(p_{ij}\in {ℝ}_{>0})}_{i\in M,j\in J}$ as in the previous problem. Our goal is to find an allocation $\rho :J\to M$ so as to minimize

When a job $j$ is allocated to $i=\rho (j)$, it has processing time $p_{ij}$ and weight $p_{ij}$. Namely, the Smith ratio of any job on any machine is always $1$. On every machine $i\in M$, the weighted completion time of scheduling ${\rho }^{-1}(i)$ on $i$ is $\frac{1}{2}\left(p_i{({\rho }^{-1}(i))}^2+{\sum }_{j\in {\rho }^{-1}(i)}{p}_{ij}^2\right)$. As all jobs have the same Smith ratio, any permutation of jobs is optimum. The objective is closely related to the $L_2$ norm of machine loads.

Suppose we are given an unweighted NSW instance with $n$ identical agents $N$, and $m$ indivisible items $M$. As the valuation functions are identical, we simply use $v_j$ to denote the value of item $j$ for any agent $i\in N$.

So in an EF1 allocation $\sigma$, for any pair $i,i^{\prime }$ of agents, $i$ does not envy $i^{\prime }$ once we remove the largest item in the bundle of agent $i^{\prime }$. [5] proved the following theorem:

The $e^{1/e}$ factor is called the EF1 gap of for the NSW problem. At a high level, the proof in [5] compares an arbitrary EF1 allocation to an optimal partially-fractional allocation via a sequence of swap operations, derives a lower bound for the EF1 allocation and an upper bound on the optimal NSW, and then optimizes these bounds to obtain the $e^{-1/e}$ guarantee. However, the argument relies on several structural lemmas and nontrivial inequalities, which makes the proof rather complicated.

[11] introduced a market equilibria based convex program for the unweighted additive Nash social welfare problem. The convex program, denoted as CP(f-SR), is defined as follows:

We note that [12] uses the NSW value as the objective, while we instead use its logarithm, for the ease of comparison with our convex program. Consider an allocation $\rho :M\to N$ for the instance. Then, we define $b_{ij}=\frac{v_{ij}}{v_i({\rho }^{-1}(i))}$ if $i=\rho (j)$ and $b_{ij}=0$ otherwise. $q_j=b_{\rho (j)j}$. This gives us a valid solution to CP(f-SR). The logarithm of the NSW of $\rho$ is

which is exactly the objective of CP(f-SR).

[12] proved the following lemma:

The lemma says that one can define prices $p_j$ for items so that the value of an item $j$ to any agent is at most its price. So the bang-per-buck (BaB) for any $ij$ pair is at most $1$. Moreover, in the solution $(b,q)$, $i$ will only be allocated items with BaB exactly 1. When agent $i$ gets a value $b_{ij}$ from item $j$, he pays $\$b_{ij}$ to $j$. Every agent $i$ spends $\$1$, and the money spent on any item $j$ is $\$q_j:=\min \{\$p_j,\$1\}$. This achieves a market equilibrium with “restricted spending”.

We revisit the rounding algorithm of [16], which is the same as that of [34] for the unrelated machine makespan minimization problem. This is the same rounding algorithm used in both [22] and [24].

We shall describe the rounding algorithm in the context of weighted Nash Social Welfare. We are given a fractional allocation $x\in {[0,1]}^E$ of items to agents: we have ${\sum }_{i\in N_j}{x}_{ij}=1$ for every $j\in M$. We further have ${\sum }_{j\in M_i}{x}_{ij}\ge 1$ for every $i\in N$ since otherwise the value of the solution $x$ will be $0$. (This property does not hold for scheduling problems, and it is not required by the rounding algorithm.) Throughout, for the given $x$, we shall use $x_i:={(x_{ij})}_{j\in M_i}$ to denote the fractional allocation for agent $i$.

For each agent $i\in N$, we sort items in $M_i$ by non-increasing $v_{ij}$ and partition the fractional items $x_i$ into $q_i:=\lceil {\sum }_{j\in M_i}{x}_{ij}\rceil$ groups $G_i=\{z^{i,1},z^{i,2},\mathrm{\dots },z^{i,q_i}\in {[0,1]}^{M_i}\}$ using this order, each containing $1$ fractional item except for the last one. Here each $z^{i,t}$ is a fractional bundle over $M_i$ with ${|z^{i,t}|}_1\le 1$, and for each $j\in M_i$, $z_j^{i,t}$ denotes the fraction of item $j$ contained in $z_j^{i,t}$. More formally, we define a total order ${\succ }_i$ over $M_i$ that sorts the items in non-increasing order of $v_{ij}$ with ties broken arbitrarily. Thus, $j{\succ }_i{j}^{\prime }$ implies $v_{ij}\ge v_{i{j}^{\prime }}$. Then $z^{i,1},z^{i,2},\mathrm{\cdots },z^{i,q_i}$ are vectors in ${[0,1]}^{M_i}$ satisfying the following properties:

• $\mathrm{■}$

  ${\sum }_{t=1}^{q_i}{z}^{i,t}=x_i$.

• $\mathrm{■}$

  ${|z^{i,t}|}_1=1$ for every $t=1,2,\mathrm{\cdots },q_i-1$.

• $\mathrm{■}$

  For any two integers $t,t^{\prime }$ with and two items $j,j^{\prime }\in M_i$ with $j{\succ }_i{j}^{\prime }$, it can not happen that $z_{j^{\prime }}^{i,t}>0$ and $z_j^{i,t^{\prime }}>0$.

Notice that under the above 3 conditions, the choice of $(z^{i,1},z^{i,2},\mathrm{\cdots },z^{i,q_i})$ is unique.

This yields a collection $G={⨄}_i{G}_i$ of groups and a fractional matching between the groups $G$ and items $M$: every group $z\in G$ is matched to an item $j$ with fraction $z_j$ (or $0$ if $j$ is not in the domain of $z$). So each group $z$ is matched to an extent of ${|z|}_1$, and each item is matched to an extent of $1$. By the way we construct the groups, a group which is not the last group for an agent $i$ is matched to an extent of $1$.

In the randomized rounding algorithm, we arbitrarily partition the fractional matching into a convex combination of (partial-)matchings between $G$ and $M$ and randomly pick a matching from the combination, according to their masses. Each integral matching allocates each item to one group, hence induces an integral allocation of items to agents: an item $j\in M$ is allocated to the agent $i$ if it is matched to a group in $G_i$. Marginal probabilities are maintained by the rounding algorithm: the probability that an item $j$ is allocated to an agent $i$ is precisely $x_{ij}$ for any $ij\in E$.

The algorithm can be derandomized by using a polynomial-sized decomposition and outputting the best matching from the decomposition. However, as is typical, it is more convenient to analyze the randomized version of the rounding algorithm.

Let $\rho$ be the random allocation given by the algorithm. In the analysis of the randomized rounding algorithm, we shall focus on a fixed agent $i$ most of the time. We create an unweighted NSW instance $ℐ$ with identical agents, which are all copies of the agent $i$, and an EF1 allocation $\sigma$ for $ℐ$.

Let $\mathrm{\Delta }$ be a sufficiently large integer such that $\mathrm{Pr}[{\rho }^{-1}(i)=S]$ for every $S$ is an integer multiple of $1/\mathrm{\Delta }$, so is $x_{ij}$ for every $j\in M_i$. We create $\mathrm{\Delta }$ copies of the agent $i$, and index them as $[\mathrm{\Delta }]$. We create $\mathrm{\Delta }{x}_{ij}$ copies of item $j$ for every $j\in M_i$. The allocation $\sigma$ is defined according to the output distribution of the rounding algorithm: for every $S\subseteq M_i$, there are precisely $\mathrm{\Delta }\cdot \mathrm{Pr}[{\rho }^{-1}(i)=S]$ agents in $[\mathrm{\Delta }]$ who gets a copy of $S$, in the allocation $\sigma$. It was shown in [16] that $\sigma$ is an EF1-allocation.

The procedure of creating $ℐ$ and $\sigma$ also applies to the rounding algorithm for scheduling problems.

Unlike [11], we could not show the rationality of the optimum solution of the convex program. So, it is not clear if the convex program can be solved in polynomial time, and more specifically, if the optimum solution can be represented using rational numbers. Nevertheless, the standard discretization technique allows us to solve the CP approximately within an additive error of $\ln (1+ϵ)$ for any constant $ϵ>0$. For every $i\in N$, we let ${\mathrm{\ell }}_i:=\min \{v_{ij}:j\in M_i\}$ and $r_i:={\sum }_{j\in M_i}{v}_{ij}$, so that we always have $h_i(x_i)\in [{\mathrm{\ell }}_i,r_i]$. (In case $|x_i|=1$, we can choose $h_i(x_i)=\min \{v_{ij}:j\in M_i,x_{ij}>0\}$.) Then, let $H_i=\{r_i{(1+ϵ)}^{-t}\ge {\mathrm{\ell }}_i:t\in {\mathbb{Z}}_{\ge 0}\}$. We shall use

as an approximation of $f_i(x_i)$.

In this section, we prove Theorem 1.2 by showing the equivalence of CP(2) and CP(f-SR) for unweighted NSW.