| paper | Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations |
| authors | Siddharth Barman, Paritosh Verma |
| venue | WINE 2021 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Obtaining the $1.0042$-approximation is $\mathrm{NP}$-hard, already for $\tau=1$ and identical supplies $2/5$, with deterministically polynomial-time computable value oracles. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given a finite set of good classes \(G\), rational per-capita supplies \(\sigma_g\), and a shared binary \mathrm{XOS} valuation \(v:2^G\to\mathbb{Z}_{\ge 0}\) with value-oracle access, assign masses \(\lambda_B\ge 0\) to integral bundles \(B\subseteq G\) subject to \(\sum_{B\subseteq G}\lambda_B=1\) and \(\sum_{B\ni g}\lambda_B\le \sigma_g\) for every \(g\). Compute or approximate \(\operatorname{NSW}_\infty(\lambda)=\exp\!\left(\sum_{B:v(B)>0}\lambda_B\log v(B)\right)\), assigning value \(0\) whenever positive mass receives a zero-valued bundle.
A unit-mass population of identical agents receives integral bundles \(B\subseteq G\); \(\lambda_B\) is the mass receiving \(B\), and \(\sigma_g\) is per-capita supply. The objective is the weighted geometric mean of bundle values, represented by a configuration formulation with potentially exponentially many bundle variables.
The good-copy extension is not canonical: the paper defines \(v\) on subsets of distinct goods, so perfect-substitute versus independently valued copies can produce different continuous problems.
fatal: False
The mirror directly covers Theorem 6 and also motivates a typed-population version of Theorem 2. It leaves the social-welfare guarantee in Theorem 3, the \mathrm{GMMS} guarantee in Theorem 4, and the binary-subadditive query lower bound unmirrored.
My strongest positive case is a genuine high-multiplicity mirror of the paper’s Nash-welfare problem. The paper’s agents are anonymous: an agent is used only through her valuation and the bundle she receives. That makes this unusually well suited to continuization.
My lead anchor is Theorem 6, proved in the paper. It states that maximizing Nash social welfare is NP-hard to approximate within a factor of \(1.0042\), even when all agents have the same binary \(\XOS\) valuation. The proof reduces from the cited Theorem 5, which gives a gap for independent set in 3-regular graphs. Given \(G=(V,E)\) and threshold \(\tau\), the paper creates \(\tau\) identical agents, one good for each edge, and valuation
\[ f(S)=\max_{v\in V}|S\cap\delta(v)|. \]
If \(G\) has an independent set of size at least \(\tau\), every agent can receive a disjoint three-edge star, so the optimal Nash welfare is \(3\). If every independent set has size at most \(94\tau/95\), at least \(\tau/95\) agents receive value at most \(2\), giving optimum at most
\[ 3^{94/95}2^{1/95}. \]
The gap is
\[ \frac{3}{3^{94/95}2^{1/95}} =\left(\frac32\right)^{1/95}>1.0042. \]
The continuous problem I would put to a prover is Continuous Identical-Binary-\(\XOS\) Nash Welfare. An instance has a finite set \(G\) of indivisible good classes, a finite set \(T\) of complete valuation types, rational population masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational per-capita supplies \(\sigma_g\), and binary \(\XOS\) valuations \(v_t:2^G\to\mathbb Z_{\ge0}\). A solution is a family of masses \(\lambda_{t,B}\ge0\), where \(\lambda_{t,B}\) is the mass of type \(t\) receiving the integral bundle \(B\subseteq G\), satisfying
\[ \sum_{B\subseteq G}\lambda_{t,B}=\mu_t \]
for every type \(t\), and
\[ \sum_{t\in T}\sum_{B\ni g}\lambda_{t,B}\le \sigma_g \]
for every good \(g\). The objective is
\[ \operatorname{NSW}_{\infty} = \exp\!\left( \max_{\lambda} \sum_{t\in T}\sum_{B:v_t(B)>0} \lambda_{t,B}\log v_t(B) \right), \]
with the zero-optimum case treated as in the paper. The task is to compute the optimum or achieve a specified approximation factor.
This is population continuization, not fractionalizing an individual’s bundle: every individual still receives an integral \(B\). Only the mass of agents receiving each bundle is fractional. The finite-to-continuous dictionary is exact. A finite instance with \(N\) agents gives \(\mu_t=n_t/N\) and \(\sigma_g=a_g/N\), where \(a_g\) is the number of copies of good \(g\). Conversely, rational \(\lambda\) can be cleared to a finite clone population.
For Theorem 6’s graph construction, take one valuation type, \(\mu=1\), and \(\sigma_e=1/\tau\) for every edge \(e\). This has a natural high-multiplicity realization: for any \(q\), use \(q\tau\) identical users and \(q\) copies of every edge-good. The number of agents can therefore be arbitrarily larger than the one valuation type. A plausible application is repeated spectrum slots or licenses: many users share the same compatibility profile, while each edge represents a recurring frequency-slot resource.
I would expect the discrete APX-hardness of Theorem 6 not to transfer unchanged. In its graph family, useful bundles can be reduced to single edges, pairs of incident edges, and complete three-edge stars. The continuous problem on that family is therefore a linear program over only polynomially many bundle patterns, with objective coefficients \(\log 1,\log 2,\log 3\). The discrete obstruction is integral packing of vertex-stars; mass allocation permits fractional packing. Thus the theorem-6 mirror is a strong Class A boundary test: the paper’s hardness may dissolve precisely because it is driven by population-level integrality.
The unrestricted identical-\(\XOS\) mirror remains an interesting Class C candidate. Its configuration LP has exponentially many bundle variables, and its pricing problem is essentially
\[ \max_{B\subseteq G} \left\{\log v(B)-\sum_{g\in B}p_g\right\}. \]
Whether binary \(\XOS\) value-oracle access is sufficient for efficient pricing, or whether this creates continuum-specific hardness, is a substantive open question. Either outcome would be valuable: tractability would exhibit the high-multiplicity relaxation doing real work, while hardness would identify a boundary where continuization stops helping.
My secondary anchor is Theorem 2, also proved in the paper. It states that, for binary \(\XOS\) valuations in the standard value-oracle model, there is a polynomial-time \(288\)-approximation algorithm for Nash social welfare; equivalently, the returned allocation has Nash welfare at least \(1/288\) of optimum. The theorem concerns the underlying allocation problem, not merely the algorithm’s encoding.
Its mirror is Typed Continuous Binary-\(\XOS\) Nash Welfare: the same mass-allocation model above, now with many valuation types and \(\tau\ll N\). The task is to output a feasible integral-bundle mass allocation satisfying
\[ \operatorname{NSW}_{\infty}(\lambda) \ge \frac{1}{288}\operatorname{OPT}_{\infty}. \]
I would expect this version to be tractable, probably through a configuration LP or a mass-aware adaptation of the paper’s non-wasteful bundle-growth argument. The paper’s characterization of binary \(\XOS\) valuations is particularly compatible with this: each type’s value is the maximum number of goods captured from one of its binary additive clauses. The unresolved issue is bit-polynomial implementation with only value queries; the finite proof’s matching initialization and discrete doubling steps need continuous flow and rounding replacements.
The mirror deliberately does not claim the paper’s Theorems 3 and 4 automatically extend to social welfare or \(\GMMS\). Those are worthwhile follow-up questions, but their continuum versions require careful definitions for positive-mass groups and per-capita indivisible supplies. The two anchors above already cover the paper’s central computational contributions.
The weakest point is that per-capita replication changes the interpretation of a unique finite good. If the application truly has one irreplaceable spectrum band, a continuum of users is not sensible; repeated slots or licenses must be supplied. I think that is an honest modelling repair rather than a distortion, because the paper itself presents spectrum allocation as an application and the high-multiplicity regime naturally means many repeated users and repeated resource copies. The more serious concession is that Theorem 6’s hardness probably disappears on its own reduction family. That is not a defect in the mirror: it is exactly the computational question ChoCo is meant to expose.
The strongest negative case is a modelling one, but it does not survive the programme’s rules.
The proposed mirror of Theorem 6 is not literally exact as stated. The paper has a fixed set of distinct indivisible goods, whereas the continuous formulation introduces good classes with per-capita supplies. If only the agents are replicated while the goods remain fixed, positive Nash welfare eventually becomes impossible: every positive-valued bundle contains at least one good, so with more agents than goods the Nash welfare is zero. To avoid this degeneration, the proponent scales the goods as well. But the paper defines valuations only on subsets of distinct goods, not on multisets of repeated copies. For a repeated edge-good, copies could be perfect substitutes or separate valuable objects, and these choices produce different valuation functions. Thus the claimed finite-to-continuous dictionary is not canonical.
This objection is strongest for Theorem 6. The original reduction is a one-copy edge-packing construction. Replacing every edge by \(q\) copies changes it into a capacitated fractional packing problem. The proposed graph instance then has one valuation type and an expected-log objective over bundle masses; its independent-set obstruction is no longer the paper’s obstruction. A repeated-spectrum-slots interpretation can make that new problem sensible, but it is an additional economic model, not something forced by the paper’s theorem.
That still does not defeat the anchor. The programme explicitly permits per-capita supplies when population continuization requires them. The repeated-slots interpretation is plausible, and the resulting question is precisely whether the discrete packing hardness survives high multiplicity. The fact that the graph gap may disappear is an answer, not an objection. Moreover, the unrestricted identical-\(\XOS\) configuration LP has exponentially many bundle variables and a nontrivial pricing problem. That is exactly the kind of computational boundary the programme is intended to study.
Theorem 2 is harder to dismiss. Its agents are anonymous apart from their valuation types, and a finite clone population gives the exact limiting objective
\[ \exp\!\left(\sum_t\sum_B \lambda_{t,B}\log v_t(B)\right). \]
Each individual still receives an integral bundle; only the mass receiving each bundle is fractional. Rational masses can be cleared to a finite clone instance, so this is genuinely a high-multiplicity version rather than outcome-space fractionalization.
The paper’s \(288\)-approximation does not automatically extend: its matching initialization and discrete bundle-doubling argument need mass-aware replacements. But that is a legitimate computational question. In fact, the corresponding configuration LP has pricing problem
\[ \max_{B\subseteq G}\{\log v_t(B)-p(B)\}, \]
and it is non-obvious whether binary \(\XOS\) value-oracle access suffices to solve this efficiently. That unresolved pricing issue is a substantive Class A/Class C question, not a reason to reject the mirror.
So the honest negative case is weak. The proponent overstates the exactness of the good-copy dictionary, and Theorem 6’s particular graph reduction may become a much easier capacitated relaxation. But both anchors admit sensible high-multiplicity repairs, and neither identity, degeneracy, nor an existing continuous treatment rules them out. I cannot honestly defeat every anchor or sustain the universal claim that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.