Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

The two anchors are genuine fairness theorems, but neither states an algorithm, running-time bound, hardness result, or computational formulation used to compute. The continuous population/configuration-LP question is coherent and authors would likely recognize it, so the failure is the required computational anchor, not the mirror's population model.

The objection that survived

Neither Theorem 3.1 nor Theorem 4.2 is a qualifying computational result under the stated anchor rule; the paper explicitly leaves computing Max-NSW unstudied.

What the mirror covers

The proposed mirror covers budget-feasible Max-NSW allocation and the \(1/4\)-EF1, Pareto-optimality, and large-\(\kappa\) fairness guarantees from Theorems 3.1 and 4.2. It leaves the paper's unnumbered APX-hardness observation, future computational questions, and other discussion without a qualifying anchored mirror.

Open questions for a prover

The case FOR (proponent)

The honest caveat is that this paper contains no qualifying named computational-complexity result. The numbered results are fairness guarantees, not theorems saying that a problem is in \( \mathrm{P} \), NP-hard, FPT, and so on. Indeed, Section 5 explicitly says that computing a Max-NSW allocation “was not studied”; its APX-hardness remark is unnumbered and inherited from the no-budget special case. Thus, under the strict anchor rule, this paper cannot support a full ChoCo case about a named computational result.

The strongest positive case is nevertheless a genuine structural mirror.

The lead anchor would be Theorem 3.1, proved in this paper: “A Max-NSW allocation \(X^*\) is \(1/4\)-EF1 and PO.” In full, for additive valuations, item costs, and agent budgets, every allocation maximizing \( \prod_i v_i(X_i) \) is Pareto optimal and satisfies the paper’s budget-aware \(1/4\)-EF1 condition: for every pair of agents \(i,j\), and every subset \(S\subseteq X_j\) with \(c(S)\le B_i\), some item \(j'\in S\) can be removed so that \(v_i(X_i)\ge \frac14 v_i(S-\{j'\})\).

A natural continuous problem is:

Continuum Budget-Feasible Max-NSW. An instance has a unit-mass population with finitely many types \(t\in T\), type masses \(\mu_t\), type-specific additive valuations \(v_{tr}\), and budgets \(B_t\). There are finitely many good classes \(r\), with per-capita supplies \(q_r\) and per-copy costs \(c_r\). An individual of type \(t\) receives an integral bundle \(s=(s_r)_r\in\mathbb Z_{\ge0}^{|R|}\) satisfying \(\sum_r c_rs_r\le B_t\), and obtains utility \(u_t(s)=\sum_r v_{tr}s_r\).

Let \(x_{t,s}\) be the mass of type \(t\) receiving bundle \(s\). Feasibility requires

\( \sum_s x_{t,s}=\mu_t \)

and

\( \sum_{t,s}s_r x_{t,s}\le q_r \)

for each good class \(r\). The continuous Max-NSW allocation is a feasible \(x\) maximizing

\( \exp\!\left(\sum_{t,s}x_{t,s}\log u_t(s)\right) \).

The solution is the mass allocation \(x\), or an integral-bundle assignment realizing it. EF1 is interpreted almost everywhere: whenever \(x_{t,s}>0\) and \(x_{u,r}>0\), every affordable subbundle \(Q\subseteq r\) must contain an item \(j\) such that \(u_t(s)\ge \alpha u_t(Q-\{j\})\). Pareto optimality means that no feasible reassignment can weakly improve every individual’s utility and strictly improve a positive mass of agents.

This is a faithful high-multiplicity mirror. With \(N\) agents, \(N\mu_t\) agents of type \(t\), and \(Nq_r\) copies of each good class, rational \(x\) is exactly the empirical distribution of a finite allocation. Moreover,

\( \sum_{t,s}x_{t,s}\log u_t(s) \)

is \(1/N\) times the logarithm of the discrete Nash product. Thus the objective is not replaced by a product over types; it is the genuine high-multiplicity limit of the product over agents. Each individual still receives an integral bundle. Only the type-level masses are fractional.

The regime is plausible in settings with many exchangeable households, applicants, or residents, finitely many valuation-and-budget profiles, and repeated supplies of service or aid packages. The number of agents is large while the number of distinct types and good classes is moderate. A type includes the complete valuation vector and budget, so this is not erasing idiosyncratic information; it is grouping agents who are indistinguishable for the problem.

I would expect the \(1/4\)-EF1 and Pareto guarantee to transfer. The proof of Theorem 3.1 is a local exchange argument: if positive mass of type \(t\) receives a bundle that violates EF1 against positive mass receiving another bundle, one can perform the same exchange on a small mass \( \varepsilon>0 \). The product improvement becomes a positive improvement in the integral log-NSW objective. The theorem should therefore hold almost everywhere in the continuum, and Example 3.2 can be replicated across many identical agents, suggesting that \(1/4\) remains tight.

The computational question is more interesting than the paper’s theorem. The formulation is a configuration LP: its variables are type–bundle masses, and its objective is linear in those variables after taking logarithms. If bundles are explicitly listed, or if the pricing problem is polynomial, this is a Class A candidate solvable by LP or column generation. With implicit bundles, pricing has the form

\( \max_{s:\,\sum_r c_rs_r\le B_t}\left\{\log u_t(s)-\sum_r y_rs_r\right\} \),

which is knapsack-like. Hence the continuous population may remove the assignment-level integrality while leaving a genuine bundle-pricing boundary; the unrestricted version could be continuum-specifically hard. That is precisely the sort of new computational question the ChoCo programme seeks.

The secondary structural anchor is Theorem 4.2, also proved in this paper: if

\( \kappa=\min_{i,j}\left\lfloor B_i/c_j\right\rfloor \),

then every Max-NSW allocation is \( \left(\frac12-\frac{5}{\kappa^{1/4}}\right) \)-EF1. The corresponding mirror is the same continuum problem with the promise that every individual good is small relative to every relevant budget. Its expected answer is a parameterized Class A guarantee: the ratio should converge to \(1/2\) as \( \kappa\to\infty \), while the replicated version of Example 4.3 suggests that this limit is tight.

The weakest point is unavoidable: neither Theorem 3.1 nor Theorem 4.2 is a computational-complexity anchor, and the paper does not prove the continuous extension. A strict referee could therefore reject this as a ChoCo case on the grounds that it supplies a compelling continuous analogue of the paper’s fairness mathematics, but not a mirror of one of the paper’s named computational results. The positive argument survives only as a proposal for a faithful new computational problem, not as a result already anchored by this paper.

The case AGAINST (opponent, writing after the proponent)

The decisive negative is that neither proposed anchor is a qualifying computational result. Theorem 3.1 and Theorem 4.2 are fairness guarantees about an optimal allocation. They do not establish membership in \( \mathrm{P} \), hardness, approximation complexity, or a parameterized algorithm. Section 5 explicitly says that computing a Max-NSW allocation was not studied. Thus the proposed continuization cannot be a mirror of a named computational result of this paper; it is a new fair-division problem inspired by its structural theorems.

Theorem 3.1 does admit a mathematically coherent high-multiplicity interpretation, and the negative case should not pretend otherwise. With repeated valuation-budget profiles, a mass \(x_{t,s}\) over integral bundles is exactly the empirical distribution of a large finite allocation, and the log-NSW objective is the normalized logarithm of the discrete Nash product. The exchange proof should indeed lift to positive masses. This is a legitimate high-multiplicity model.

But that observation mirrors the fairness theorem, not a computational claim. The proposed configuration LP and its pricing problem arise only after replacing the paper’s one-copy item set and arbitrary valuation matrix \(v_{ij}\) by repeatable good classes, per-capita supplies, and bundle configurations. Those changes may be entirely sensible, but they create a new capacitated configuration problem; they are not computational consequences of Theorem 3.1. If integral bundles are retained, EF1 is essentially a support-wise high-multiplicity lifting of the discrete definition. If bundles are fractionalized instead, the model no longer mirrors the paper’s indivisible-item EF1 statement. Either choice can motivate future work, but neither supplies this paper with a ChoCo computational anchor.

The same objection defeats Theorem 4.2. The parameter

\[ \kappa=\min_{i,j}\left\lfloor \frac{B_i}{c_j}\right\rfloor \]

measures item granularity relative to budgets, not population multiplicity. The paper’s tight example already has only two agents; making \(\kappa\) large requires changing item sizes or supplies, independently of taking a population limit. A model with both many repeated agents and many small repeated goods is possible, but its computational question is newly introduced and its \(1/2\)-limit is still a fairness statement, not a complexity result.

The proponent’s pricing discussion is therefore the strongest reason to study a related model, but also the clearest reason it is not a mirror of this paper. It proposes computation that the authors explicitly left open, under a materially redesigned resource model. That could be worthwhile research in its own right, but it cannot rescue this paper under the programme’s strict anchoring rule.

The universal claim is nevertheless weaker than the procedural one. It would be incorrect to say that no plausible continuous population exists: repeated households, applicants, or service recipients with common valuation-budget profiles are a sensible high-multiplicity regime. The strongest honest negative is narrower and sufficient for rejection here: this paper supplies continuous fairness analogues, but no named computational result to continuize.

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.