Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities

The strongest positive case is a high-multiplicity two-sided labour-market mirror. My lead anchor is Theorem 4.1, proved in this paper: there is a \(1.33\)-approximation for Capacitated Two-Sided NSW under subadditive firm valuations.

Imagine a large centralized labour market with millions of workers and many employer units, but only a few hundred recurring worker and employer profiles. A worker type contains the complete vector of values for employer types. A firm type contains its capacity and its complete valuation over bundles of worker types. Thus agents of one type are genuinely indistinguishable; idiosyncratic prices or preferences would simply define separate types.

Let \(\mathcal F\) and \(\mathcal W\) be finite sets of firm and worker types, with masses \(\phi_f,\psi_w\in\mathbb Q_{\ge0}\). A firm type \(f\) has capacity \(c_f\) and a monotone, normalized, subadditive valuation

\[ V_f(b),\qquad b\in\mathbb Z_{\ge0}^{\mathcal W},\quad \lVert b\rVert_1\le c_f, \]

where \(b_w\) is the number of workers of type \(w\) in the bundle. A worker type \(w\) has cardinal value \(\omega_w(f)\) for firm type \(f\).

The continuous problem is:

\[ \textsc{Capacitated Two-Sided NSW}_{\infty} \]

Choose \(z_{f,b}\ge0\), where \(z_{f,b}\) is the mass of firms of type \(f\) receiving bundle \(b\), subject to

\[ \sum_b z_{f,b}=\phi_f \]

for every \(f\), and

\[ \sum_{f,b} b_w z_{f,b}\le \psi_w \]

for every worker type \(w\). In the positive-welfare regime, all worker mass is matched. The objective is the population Nash welfare

\[ \operatorname{NSW}_{\infty}(z) = \exp\!\left( \frac{ \displaystyle \sum_{f,b}z_{f,b}\log V_f(b) + \sum_{f,b,w}b_wz_{f,b}\log\omega_w(f) }{ \displaystyle \sum_f\phi_f+\sum_w\psi_w } \right). \]

The task is to output a feasible mass allocation maximizing this quantity, or an \(\alpha\)-approximation to it.

This is recognizably the authors’ problem, not a tractability-induced simplification: firms still receive bundles, capacities remain per firm, firm valuations remain combinatorial, and workers still choose among firms. Only the population has been replaced by masses. A rational solution can be implemented by assigning the corresponding fractions of a large cohort of identical workers and firms.

The paper’s flow proof also survives aggregation. Give each firm type a “main” copy of capacity \(\phi_f\) and a secondary copy of capacity \((c_f-1)\phi_f\). A worker-type-to-main-copy edge has cost

\[ -\log\!\bigl(V_f(e_w)\omega_w(f)\bigr), \]

and an edge to a secondary copy has cost

\[ -\log\omega_w(f). \]

This is a minimum-cost flow over types and masses. Subadditivity gives

\[ V_f(b)\le \lVert b\rVert_1\max_{w:b_w>0}V_f(e_w), \]

and weighted AM–GM bounds the aggregate bundle-size loss by

\[ \left(\frac{\Psi}{\Phi}\right)^{\Phi/(\Phi+\Psi)}, \qquad \Phi=\sum_f\phi_f,\quad \Psi=\sum_w\psi_w, \]

whose maximum is below \(1.33\). I therefore expect this mirror to be Class A: the paper’s \(1.33\)-approximation should extend to the type-level problem, with exact optimization and sharper ratios becoming pricing questions.

The main follow-up questions are whether additive valuations permit an exact convex or flow formulation, whether fixed numbers of firm types yield a PTAS, and whether arbitrary subadditive type valuations create a genuinely continuum-specific pricing problem.

A second, especially clean anchor is Theorem 5.1, also proved in this paper. It states that Uncapacitated Two-Sided NSW is NP-hard to approximate within \(1.0000759\) under additive valuations. Its proof uses Lemma 5.2, modified from Garg and Murhekar [23], but Theorem 5.1 itself is established here.

For its continuous mirror, take additive firm values \(v_f(w)\), no firm capacity, and masses \(\phi_f,\psi_w\). Let \(x_{fw}\) be the mass of workers of type \(w\) assigned to firms of type \(f\), with

\[ \sum_f x_{fw}=\psi_w. \]

In the nonatomic limit, identical firms of type \(f\) can be balanced, so each receives average utility

\[ \bar u_f(x)=\frac{1}{\phi_f}\sum_w v_f(w)x_{fw}. \]

The continuous problem is to maximize

\[ \exp\!\left( \frac{ \displaystyle \sum_f\phi_f\log \bar u_f(x) + \sum_{f,w}x_{fw}\log\omega_w(f) }{ \displaystyle \sum_f\phi_f+\sum_w\psi_w } \right). \]

This is a concave maximization over linear flow constraints: the firm terms are logarithms of affine functions of \(x\), and the worker terms are linear. Hence it should admit a polynomial-time \((1+\varepsilon)\)-approximation through standard convex optimization. In the theorem’s reduction, worker values are uniformly \(1\), so the worker term is constant and the structure is even simpler.

This is a good example of hardness disappearing for the right reason. The theorem’s reduction encodes indivisible item allocation. In the high-multiplicity mirror, \(x_{fw}\) is not a fractional individual worker: it is a fraction of a large cohort of identical workers. The combinatorics caused by indivisibility vanish, while the two-sided Nash objective and additive preferences remain.

I would not anchor on Theorem 3.1 without additional assumptions. A one-sided mirror is plausible, but arbitrary submodular valuations over named items do not automatically induce a canonical valuation over masses of item types. The two-sided additive and subadditive settings provide a substantially cleaner case.

The weakest point is precisely this valuation-extension issue. The mirror requires symmetry within worker types: a firm’s value must depend on the counts of worker profiles, not on hidden identities among supposedly identical workers. The paper’s oracle model alone does not guarantee that. The uncapacitated scenario in Theorem 5.1 is also less realistic than the capacitated labour-market setting. But the symmetric repeated-cohort regime is a legitimate high-multiplicity instance family, and Theorem 4.1 gives a concrete, capacity-sensitive mirror whose algorithmic structure is already visible in the paper.