{"id":"4e47c21f-00c1-48b6-9fed-ff19e908032a","arxiv_id":"2411.14007","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New constant-factor approximation algorithms for capacitated Nash social welfare: (6+ε) for one-sided submodular valuations and 1.33 for two-sided subadditive valuations.","lead":"This paper gives approximation algorithms for maximizing Nash social welfare, a fairness and efficiency measure, in two resource allocation settings with capacity limits. It achieves a (6+ε)-approximation for fair division with submodular values and a 1.33-approximation for matching workers to firms with subadditive firm preferences.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the reader's flagged AM-GM step in Lemma 3.9 is actually valid because n≤m, and the weighted separation-oracle issue is repairable; central Theorems 3.1 and 4.1 appear sound.","rationale":"The reader's weakest_assumption is that Lemma 3.9's AM-GM/Bernoulli step fails for m>1 and typical ε. That concern does not land: the phase-1 matching requires n ≤ m, and under that condition the required inequality follows from monotonicity of ((1+δ)^k - 1)/k. The weighted-LP separation-oracle concern is a terseness issue rather than a demonstrated false step: negative α'_j values do not break the stated DP for minimum-sum subsets of fixed cardinality and rounded value, and +∞ values can be excluded. My independent review of the one-sided local-search proof found the price arguments, the endowed-valuation lemmas, and the matching-based Phase 3 argument coherent after accounting for notation typos. The two-sided min-cost-flow argument is straightforward and correct, including the 1.33 constant. I therefore see no reason to change the reader's conditional verdict on the basis of the concerns raised; the central theorems appear correct, though the paper would benefit from fixing the Lemma 3.9 inequality proof, renaming the accuracy parameter, and tightening the Corollary 4.3 numerical estimates.","tokens_in":26925,"tokens_out":51826,"duration_ms":444632,"concrete_test":"Run a numerical spot-check of Lemma 3.9's final inequality for a range of values with n ≤ m, e.g., n=2, m=100, ε=0.1 and n=50, m=100, ε=0.5, computing (m/n)((1+ε)^{n/m} - 1) and comparing to ε. If the inequality fails for any n ≤ m, the constant 6 in Theorem 3.1 would degrade; if it holds, as the algebra above predicts, the reader's central objection is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful pass over the central proofs, I did not find a load-bearing flaw in Theorems 3.1 or 4.1. The reader's main concern is Lemma 3.9's final bound, which as typeset says (6 + 4(m/n)εhat)^n ≤ 6^n(1+ε)^n. Writing δ = (1+ε)^{1/m} - 1, we have εhat = (1+δ)^n - 1, and the required inequality is (m/n)((1+δ)^n - 1) ≤ (1+δ)^m - 1. This is exactly f(n) ≤ f(m) for f(k) = ((1+δ)^k - 1)/k, which is increasing for k ≥ 1. Since Phase 1 requires n ≤ m, the inequality holds; the attribution to Bernoulli is a proof-writing error, not a mathematical gap. The self-referential ε notation is also a typographical issue: the local-search parameter should be a fresh symbol depending on the desired approximation ε. The Appendix A.1 separation oracle with possibly negative α'_j values is not obviously broken: a knapsack DP over cardinality and rounded value still computes the minimum sum even with negative item weights, and values of +∞ for w_j(i)=0 are handled by excluding such items. The two-sided 1.33 proof is clean: the min-cost flow is integral, the cost decomposition is valid under the nonzero-NSW assumption, and Lemma 4.2 correctly bounds the loss from replacing each firm's bundle by its favorite worker. There are minor issues elsewhere (the Corollary 4.3 proof contains a numerically false intermediate inequality, and some edge cases such as c_i=1 require small patches), but these do not threaten the two main theorems.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies capacity-constrained Nash social welfare (NSW) maximization in two preference models. For the one-sided model with submodular valuations, it gives a (6+ε)-approximation algorithm via a matching-based local search that uses two-way swaps to respect capacities (Theorem 3.1). For the two-sided model with subadditive firm valuations, it gives a 1.33-approximation via a single minimum-cost flow computation (Theorem 4.1). It also provides an e^{1/e+ε}-approximation for weighted two-sided NSW with additive valuations by adapting a configuration LP of Feng and Li (Theorem 5.1), a PTAS for a constant number of firms (Corollary 4.3), and an APX-hardness result (Theorem 6.1). The analysis builds on prior work by Garg et al. and Jain and Vaish.","tokens_in":27369,"tokens_out":26504,"duration_ms":228241,"significance":"These are strong results. The one-sided result is the first constant-factor approximation for capacitated submodular NSW; the two-sided result improves the prior sqrt(OPT) bound while covering subadditive valuations, and it exhibits a computational separation between Nash and utilitarian welfare. The two-sided proof is particularly clean: the min-cost-flow integrality argument and the subadditivity-based bound (Lemma 4.2) are correct and elegant. The one-sided proof adapts the local-search framework of Garg et al. with swap operations that preserve feasibility, and the high-level structure is sound. The paper ships reproducible, self-contained arguments for the main theorems, which is a significant strength. Several local corrections and clarifications are needed, but they do not undermine the central results.","major_comments":[{"comment":"The approximate separation oracle for the dual of the configuration LP is under-specified with respect to zero and negative values. The quantities α'_j = (α_j - ζ_j ln w_j(i))/η_i can be negative because ln w_j(i) may be negative, and the text states \"assume ln 0 = -∞\" in the sorting step for η_i = 0. The dynamic program is described as finding the minimum sum of α'_j values subject to cardinality and rounded-value constraints, but the text does not justify that the DP remains correct with negative item costs, nor does it explain how infinite entries (from w_j(i) = 0 with positive ζ_j) are excluded from the DP and from the sorting rule. This is a gap in the proof of Theorem 5.1 as written; it should be repaired by a formal treatment of arbitrary real costs and by spelling out the convention for zero-valuation pairs.","section":"Section 5.1 and Appendix A.1"}],"minor_comments":[{"comment":"The symbol ε is used both for the target approximation and for the local-search threshold, making the definition ε = -1 + (1+ε)^{1/m} self-referential. Use a fresh symbol (e.g., δ) for the local-search parameter. The final inequality (6 + 4(m/n)ε̂)^n ≤ 6^n(1+ε)^n is valid with δ = -1 + (1+ε)^{1/m}, because (m/n)((1+δ)^n - 1) ≤ ε follows from monotonicity of ((1+x)^k - 1)/k for 0 ≤ k ≤ m; the attribution to Bernoulli is inaccurate and should be corrected.","section":"Section 3, \"Accuracy parameter\" and Lemma 3.9"},{"comment":"The proof uses the inequality log(x)/(1+x) < 1/x^{0.75} for all x > 9, which is false (e.g., at x = 10, the left side is about 0.209 and the right side is about 0.178). The PTAS conclusion is still true, but a correct proof should verify log(x)/(1+x) < log(1+ε) directly from x > 1/ε^2 rather than through the false intermediate bound.","section":"Corollary 4.3 proof"},{"comment":"The exponent in \"e^{m/(e(m+n))}\" should be n/(e(m+n)), since ∑_{i∈F} η_i = n/(m+n) when η_i = 1/(m+n) for all firms. As written, the claimed equality with e^{1/(e(x+1))} is algebraically incorrect.","section":"Section 5.2"},{"comment":"The stated inequality v(R-j) ≥ ∑_{k∈R}(v(R) - v(R-k)) is not true for arbitrary submodular valuations; for example, the additive valuation v(S)=|S| with R={a,b} gives 1 ≥ 2. The lemma relies on the endowed-valuation property v(∅)>0, and this hypothesis should be stated explicitly in the lemma.","section":"Lemma 3.7"},{"comment":"In the proof of Lemma 3.3, the chain \"vi(J) ≤ (|J|+1)vi(∅)\" appears to mix the endowed and non-endowed valuations; the tilde over v should be used consistently and the inequality should be justified via the endowed-valuation definition. Also, the two-sided flow network in Section 4 requires n ≤ m for feasibility; this follows from the positive-NSW assumption but is worth stating explicitly.","section":"Lemma 3.3 and Section 4"},{"comment":"The approximation ratio in Theorem 5.1, typeset as \"e(∑_{i∈F} η_i)/e+ϵ\", is garbled; it should read e^{(∑_{i∈F} η_i)/e + ε}.","section":"Theorem 5.1 statement"}],"recommendation":"minor_revision","confidential_remarks":"The central claims, Theorems 3.1 and 4.1, appear correct; my reading did not identify a fatal flaw in the local-search or min-cost-flow arguments. The main issues are concentrated in the weighted configuration-LP section (Appendix A.1) and in several proof details that should be fixed in revision. The paper is in scope for a theory venue and should be given a fair revision opportunity."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time. The paper proves two real results: a (6+ε)-approximation for one-sided capacitated Nash social welfare under submodular valuations, and a clean 1.33-approximation for the two-sided version under subadditive valuations. Both are firsts or substantial improvements, and both are likely correct.\n\nThe two-sided part is the strongest. The min-cost flow construction is elegant, the integrality argument is sound, and Lemma 4.2's AM-GM step is valid. The one-sided part is a careful adaptation of Garg et al.'s local search with two-way swaps; the phase analysis holds together.\n\nThe reader's main concern was Lemma 3.9's final inequality. I checked it: the step is valid because n ≤ m. If the local-search parameter is written as δ = (1+ε)^{1/m} − 1, the required inequality reduces to monotonicity of f(k) = ((1+δ)^k − 1)/k, which is increasing for k ≥ 1. So (m/n)((1+δ)^n − 1) = f(n) ≤ f(m) = ε. The paper's real mistake is presentation: it reuses ε for both the local-search parameter and the final accuracy, and it attributes the step to Bernoulli when it is actually monotonicity. That is a rewrite, not a flaw.\n\nThe appendix's separation oracle also looks fine. Negative α'_j terms are fine for a knapsack DP that minimizes a sum; the +∞ values from logs of zero are simply ignored. The concern does not land.\n\nSoft spots are minor. Corollary 4.3's proof contains a numerically false intermediate inequality, log(x)/(1+x) < 1/x^{0.75}, for natural log and the relevant range of x. The PTAS conclusion is likely true, but that proof needs fixing. Some edge cases, like c_i = 1, are brushed aside but are patched by the dummy-item reduction. The iteration bound in Lemma 3.3 is slightly hand-wavy.\n\nWho benefits: anyone working on fair division, Nash welfare, or matching-with-preferences. The two-sided result is the one people will remember. Send it to a serious referee; the main theorems are correct and the paper deserves engagement despite the presentation issues.","headline":"Solid constant-factor results for capacitated Nash welfare; the one-sided proof's suspicious step is actually fine once you track the parameter definitions.","tokens_in":27884,"tokens_out":5470,"would_cite":true,"duration_ms":49319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Capacitated Nash social welfare admits a (6+ε)-approximation under submodular one-sided valuations and a 1.33-approximation under subadditive two-sided valuations, both in strongly polynomial time, while two-sided Nash welfare is APX-hard…","keywords":["Nash social welfare","fair division","capacity constraints","submodular valuations","subadditive valuations","approximation algorithms","two-sided matching","min-cost flow"],"falsifier":"Concretely, expand Lemma 3.9's AM-GM chain with $n=2,m=3,\\varepsilon=0.2$: the printed inequality $(6+4(m/n)\\hat{\\varepsilon})^n\\le 6^n(1+\\varepsilon)^n$ requires $1+(m/n)((1+\\varepsilon)^n-1)\\le 1+\\varepsilon$, which is false, so verifying whether a corrected bound can keep the constant independent of $m$ is the direct test of the one-sided theorem.","tokens_in":26720,"feed_emoji":"⚖️","tokens_out":11053,"duration_ms":89385,"temperature":0.7,"pith_summary":"The paper's goal is to show that capacity constraints do not make Nash social welfare maximization intractable in either of the two standard allocation models. For one-sided allocations of indivisible items with per-agent capacities, it claims a $(6+\\varepsilon)$-approximation whenever valuations are submodular, running in strongly polynomial time with polynomially many value queries; for two-sided worker-firm matchings with firm capacities, it claims a $1.33$-approximation whenever firms have subadditive valuations. If both claims hold, these are the first constant-factor results for the capacitated one-sided submodular setting and a large improvement over the prior $\\sqrt{\\mathrm{OPT}}$ bound for the two-sided setting. The paper also proves that two-sided Nash welfare is APX-hard at factor $1.0000759$, so the approximation effort has a matching lower-bound direction.","feed_headline":"Capacitated Nash welfare gains 6+ε and 1.33 approximations","feed_subtitle":"A swap-based local search handles the one-sided caps; one min-cost flow gives the two-sided 1.33.","key_machinery":"One-sided: the algorithm runs in three phases—a maximum-weight matching that fixes a set $H$ of items, a local search over the remaining items using only full and partial swaps so that every bundle has size $c_i-1$, and a final rematching of $H$. The analysis works with endowed valuations $\\bar v_i(S)=v_i(S)+v_i(\\ell(i))$ that add each agent's favourite remaining item, defines swap prices $p_{jk}=\\max\\{0,(v_i(R_i)-v_i(R_i-j+k))/v_i(R_i-j+k)\\}$, and uses the price bound $\\sum p\\le 1$ plus an AM-GM bound to show the intermediate mapping $T$ has NSW at least $\\mathrm{OPT}/6(1+\\varepsilon)$. Two-sided: Lemma 4.2 shows subadditivity gives $\\mathrm{NSW}(\\mu)\\le 1.33(\\prod_i v_i(j_i)\\prod_j w_j(\\mu_j))^{1/(m+n)}$, reducing the objective to favourite-worker values and worker values; a min-cost flow network with a main and a secondary copy of each firm then maximizes the product in the bound in strongly polynomial time.","core_discovery":"The paper's central claim is that capacity constraints do not push Nash social welfare maximization out of the constant-factor regime. In the one-sided model, where each agent may receive at most $c_i$ items, it gives a $(6+\\varepsilon)$-approximation for monotone submodular valuations, in strongly polynomial time and with polynomially many value queries; this is the first constant-factor result for the capacitated submodular setting. In the two-sided model, where firms have capacities over workers and workers rank firms cardinally, it gives a $1.33$-approximation when firms have monotone subadditive valuations, improving on the earlier $\\sqrt{\\mathrm{OPT}}$ bound for additive valuations and matching a much broader domain. The same flow-based construction yields a PTAS when the number of firms is constant, and a weighted version of the configuration LP gives an $e^{1/e}+\\epsilon$ approximation for additive valuations. Complementing these, the paper proves two-sided Nash welfare is APX-hard, inapproximable within $1.0000759$ unless P=NP, even with additive valuations and no capacities.","pith_inferences":["If the AM-GM bound in Lemma 3.9 cannot be repaired, the one-sided result is not a uniform $6+\\varepsilon$ in $m$; a direct numerical test with $m>1$ and small $\\varepsilon$ settles which constant the proof actually supports.","The two-sided argument uses subadditivity only through $v_i(\\mu_i)\\le |\\mu_i|v_i(j_i)$, so the same min-cost-flow construction should work for any valuation class satisfying a top-worker bound, including possibly matroid or lower-quota variants of the matching problem.","The one-sided algorithm's reliance on swaps rather than one-way transfers is the natural bridge to matroid constraints, where exchange axioms play the role of the two-way transfer; the paper names matroid constraints as future work.","The weighted configuration-LP result depends on a separation oracle whose knapsack dynamic program may encounter negative $\\alpha'_j$ values, so the $e^{1/e}+\\epsilon$ guarantee should be treated as contingent on that oracle's correctness being pinned down."],"forward_implications":["For the one-sided model under submodular valuations, capacities are no longer a barrier to constant-factor approximation: a $(6+\\varepsilon)$ polynomial-time, value-query algorithm exists.","For the two-sided model under subadditive valuations, a single min-cost flow gives a $1.33$-approximation, improving the previous $\\sqrt{\\mathrm{OPT}}$ bound even for additive valuations.","Two-sided Nash welfare is computationally easier than utilitarian welfare in this setting, since utilitarian welfare retains an $e/(e-1)-\\varepsilon$ hardness while Nash welfare has a constant-factor algorithm.","With a constant number of firms, the same flow construction yields a PTAS, and exhaustive search covers the small $m$ regime.","The weighted additive case inherits an $e^{1/e}+\\epsilon$ approximation from the adapted configuration LP, and in the unweighted additive case the two methods combine to roughly $1.163$."],"supporting_citations":[{"why":"Supplies the uncapacitated (4+ε) matching-and-local-search algorithm whose swap operation the paper modifies into two-way exchanges to respect capacities.","marker":"Garg et al. [2023a]"},{"why":"Provides the $e/(e-1)-\\varepsilon$ value-query hardness bound that motivates the one-sided constant-factor algorithm and frames its guarantee.","marker":"Garg et al. [2023b]"},{"why":"Defines the two-sided capacitated Nash welfare problem and contributes the $\\sqrt{\\mathrm{OPT}}$-approximation that the 1.33 algorithm improves, along with the NP-hardness baseline.","marker":"Jain and Vaish [2024]"},{"why":"Supplies the configuration LP and rounding scheme that Section 5 adapts to weighted two-sided capacity-constrained Nash welfare.","marker":"Feng and Li [2024]"},{"why":"Gives the APX-hard one-sided instances with $m \\le 1.5n$ that Lemma 6.2 converts into two-sided hardness.","marker":"Garg and Murhekar [2021]"},{"why":"Provides the minimum-mean-cycle cancellation algorithm that makes the min-cost-flow computation strongly polynomial.","marker":"Goldberg and Tarjan [1989]"}],"fun_headline_variants":["Capacitated Nash welfare gets 6+ε and 1.33 approximations","First constant-factor for one-sided submodular Nash welfare with caps","1.33-approximation for two-sided Nash welfare with subadditive firms","Capacity constraints don't break constant-factor Nash welfare","Nash welfare under caps: 6+ε and 1.33 approximations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the arithmetic-mean/geometric-mean estimate in the one-sided proof can be repaired to give a constant independent of $m$, since the printed version requires $1+(m/n)((1+\\varepsilon)^n-1)\\le 1+\\varepsilon$, which fails when $m>1$.","fun_headline_variants_meta":{"raw":{"variants":["Capacitated Nash welfare gets 6+ε and 1.33 approximations","First constant-factor for one-sided submodular Nash welfare with caps","1.33-approximation for two-sided Nash welfare with subadditive firms","Capacity constraints don't break constant-factor Nash welfare","Nash welfare under caps: 6+ε and 1.33 approximations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00074,"raw_usage":{"total_tokens":3380,"prompt_tokens":1101,"completion_tokens":2279,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":2183}},"tokens_in":717,"tokens_out":2279,"duration_ms":18229,"temperature":1.0,"reasoning_tokens":2183,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:39:10.505473+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Concretely, expand Lemma 3.9's AM-GM chain with $n=2,m=3,\\varepsilon=0.2$: the printed inequality $(6+4(m/n)\\hat{\\varepsilon})^n\\le 6^n(1+\\varepsilon)^n$ requires $1+(m/n)((1+\\varepsilon)^n-1)\\le 1+\\varepsilon$, which is false, so verifying whether a corrected bound can keep the constant independent of $m$ is the direct test of the one-sided theorem.","supporting_citations":[{"cited_title":"Maximizing Nash Social Welfare under Two-Sided Preferences","cited_arxiv_id":null,"evidence_quote":"Defines the two-sided capacitated Nash welfare problem and contributes the $\\sqrt{\\mathrm{OPT}}$-approximation that the 1.33 algorithm improves, along with the NP-hardness baseline."},{"cited_title":"A Note on Approximating Weighted Nash Social Welfare with Additive Valuations","cited_arxiv_id":null,"evidence_quote":"Supplies the configuration LP and rounding scheme that Section 5 adapts to weighted two-sided capacity-constrained Nash welfare."},{"cited_title":"Finding Minimum-Cost Circulations by Canceling Negative Cycles","cited_arxiv_id":null,"evidence_quote":"Provides the minimum-mean-cycle cancellation algorithm that makes the min-cost-flow computation strongly polynomial."}],"review_version":1}