Greedy Algorithms for Maximizing Nash Social Welfare

The strongest positive case is a high-multiplicity mirror of the paper’s concave-binary Nash-welfare problem. My lead anchor is Corollary 5.2; Theorem 3.1 gives a useful, independent secondary anchor. The paper contains no numbered hardness theorem of its own: its NP-hardness and APX-hardness statements are unnumbered claims citing other work, so I do not present them as anchors.

The population has mass one and a finite set \(T\) of complete agent types. In the binary setting, a type \(t\) specifies an acceptable-good set \(\Gamma_t\subseteq [m]\) and, for the concave extension, a nondecreasing concave function \(f_t:\{0,\ldots,m\}\to\mathbb{Q}_{\ge 0}\). Its utility for an integral bundle \(B\subseteq[m]\) is

\[ u_t(B)=f_t(|B\cap\Gamma_t|). \]

The society is \(\mu\), where \(\mu_t\) is the mass of type \(t\). Because keeping only \(m\) one-off goods would give almost every agent utility zero, the natural high-multiplicity regime also scales supply: good \(j\) has \(\rho_j\) indivisible copies per unit population. A finite realization with population \(N\) has \(N\mu_t\) agents of type \(t\) and \(N\rho_j\) distinct copies of good \(j\). Each agent still receives an integral bundle; only the mass of agents receiving each bundle is fractional.

The action variable is \(x_{t,B}\ge 0\), the mass of type-\(t\) agents receiving bundle \(B\). It satisfies

\[ \sum_B x_{t,B}=\mu_t \]

for every \(t\), and

\[ \sum_{t}\sum_{B\ni j}x_{t,B}=\rho_j \]

for every good \(j\). The continuum Nash social welfare is

\[ \operatorname{NSW}_\infty(x) = \exp\!\left( \sum_t\sum_B x_{t,B}\log u_t(B) \right), \]

with zero-utility bundles treated as giving value zero. This is the correct population analogue of the finite geometric mean: it averages \(\log\) utility over individual agents, rather than taking the logarithm of a type’s average utility.

This is a credible regime for a national-scale allocation of a finite catalogue of indivisible benefit, education, or household goods. Millions of recipients may fall into a few dozen or few hundred repeated need-patterns, while supplies are planned per capita. Thus \(N\gg \tau\), with \(\tau=|T|\) fixed or moderate. A rational \(x\) has the exact finite interpretation obtained by choosing \(N\) so that all \(N x_{t,B}\) are integers. Conversely, every finite allocation induces such empirical masses. This is a genuine high-multiplicity dictionary, not an analogy.

My lead question is Concave-Binary-NSW\(_\infty\):

Given \(m\), rational \(\mu\), rational supplies \(\rho\), and the finite list of types \((\Gamma_t,f_t)\), compute a finite-support bundle-mass allocation \(x\) maximizing \(\operatorname{NSW}_\infty(x)\), or an \(\varepsilon\)-optimal allocation under the usual precision convention.

The anchor is Corollary 5.2, proved in this paper from Lemma 5.1. It states: given any fair-division instance with concave and binary valuations, a Nash-optimal allocation can be computed in polynomial time. The additive binary case \(f_t(k)=k\) is the narrower exact result stated as Theorem 3.2, also proved here.

I expect this mirror to be Class A: tractable. The configuration formulation is a linear program in the variables \(x_{t,B}\), with objective coefficients \(\log f_t(|B\cap\Gamma_t|)\). Although there can be exponentially many bundles, its pricing problem has the form

\[ \max_{B\subseteq[m]} \left\{ \log f_t(|B\cap\Gamma_t|) - \sum_{j\in B}p_j \right\}. \]

For a fixed number \(k\) of acceptable goods, the best bundle takes the \(k\) cheapest acceptable goods under the dual prices. Concavity then reduces pricing to a one-dimensional search over \(k\). Thus the continuous problem places the paper’s indivisible-allocation objective inside precisely the column-generation machinery that the continuization programme is meant to expose. The goods have not become divisible: \(x\) divides the population into groups, while every agent in each group receives an integral bundle.

My secondary question is Identical-Value-NSW\(_\infty^{1.061}\). Here there is one agent type, all agents share a common additive value vector \(v\in\mathbb{Q}_{>0}^m\), and the same supply vector \(\rho\). The question is to compute an integral-bundle mass allocation \(x\) satisfying

\[ \operatorname{NSW}_\infty(x) \ge \frac{1}{1.061}\operatorname{NSW}_\infty^\star. \]

The anchor is Theorem 3.1, proved in this paper. It states that for additive, identical valuations, there is a polynomial-time \(1.061\)-approximation algorithm for maximizing Nash social welfare. The finite greedy algorithm processes goods in descending value and gives each good to an agent with currently least valuation. In the continuum, its natural limit assigns each infinitesimal mass of a good supply to the currently least-valued mass of agents. Applying Theorem 3.1 to finite \(N\)-replicas and taking the high-multiplicity limit preserves the \(1/1.061\) guarantee.

This is also Class A, although it is a weaker anchor than Corollary 5.2 because the type distribution collapses to one type. It is nevertheless a direct mirror of the paper’s stated special case, and it raises useful questions about whether the continuum configuration formulation can improve the \(1.061\) factor or compute the exact optimum.

The main further questions are whether the finite exactness proof of Theorem 3.2 has a direct mass-transfer analogue, how to round an \(\varepsilon\)-optimal continuum allocation back to \(N\) agents with controlled welfare loss, and where pricing becomes hard for richer valuation classes. Those are substantive computational questions, not merely questions about divisible goods.

The weakest point is the supply co-modification. If the problem is interpreted as allocating a fixed collection of unique goods to an ever-growing population, Nash welfare degenerates because most agents receive nothing. The mirror therefore needs repeated good supplies, exactly as the programme permits. A referee who views the paper’s goods as inherently one-off objects might reject that regime. The positive case survives only if the catalogue-supply scenario—many agents with repeated need types and proportionally scaling indivisible supplies—is accepted as a sensible high-multiplicity version of their fair-division problem.