{"id":"4f1e2c55-ef64-4fbd-b7a6-49977f4f3f0c","arxiv_id":"2607.13340","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An efficient randomized algorithm approximates max Nash social welfare under additive valuations by e^{1/e} - c for some c > 0 — the first improvement over the 2018 bound of Barman et al.","lead":"This preprint presents a randomized algorithm that divides indivisible goods among people with additive valuations and approximates the Nash social welfare strictly better than the previous eight-year-old e^{1/e} bound. The gap is an existential constant that the paper itself estimates at around 10^{-80}, so the result matters as a structural separation in algorithm theory, not as a practical speedup.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the ST-rounding bridge (Lemma 6.2) is the most intricate step, but its swap invariant holds under review.","rationale":"The reader identified Lemma 6.2 as the weakest assumption, and I agree that it is the most load-bearing unformalized step: every later bound routes through it. However, attempting to falsify it, I found the swap argument internally consistent. The two cases in Lemma 6.2 both preserve the invariant that each agent receives at most one good from each bucket, which is necessary for the induction to reach W. The matching-marginal argument that logNSW(Z)=ST(x,i) is also sound given the Rationality and Cardinality properties. I similarly checked the dependent partial rounding properties D1–D4; D2's negative-correlation proof computes the expected product drop correctly, and D4's pairing argument works because goods are never endpoints of the chosen paths. The constants in Theorems 6.21, 7.2, and 8.1 are positive despite being tiny, and the final composition with ε=c*/2 is valid. I found one minor, non-central error: Observation B.7 is overbroad—it can fail for i>Δ—but the argument in Theorem 4.8 only needs i≤Δ, where the claim is true because goods in G_Δ are never removed. Since no load-bearing flaw surfaced, I do not recommend changing the reader's CONDITIONAL verdict; the conditionality should remain based on the proof's intricacy rather than on any identified error.","tokens_in":63191,"tokens_out":45807,"duration_ms":397381,"concrete_test":"Brute-force Lemma 6.2: for all instances with n,m≤4 and rational x with denominators ≤4 (and a suitable feasible Δ), enumerate the ST matching distribution, build the artificial instance I_{i,x}(Δ), compute the round-robin allocation W and the induced allocation Z, and verify ST(x,i)≥logNSW(W) with a small numerical tolerance. If the inequality holds for all enumerated cases and for a randomized sample with m=5 and denominators ≤3, the bridge is supported; any violation would pinpoint the failing swap case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After close review, I cannot identify a concrete flaw in the central chain. The most load-bearing step is Lemma 6.2, which connects ST(x,i) to the round-robin allocation of the artificial instance. I checked the two-case swap argument: the 'at most one good per bucket' invariant is preserved in both cases. In Case 2, swapping the entire >t parts still leaves each agent with exactly one good from every bucket <t and >t and one from bucket t, so repeated swaps can reach W. The equality ST(x,i)=logNSW(Z) follows from Δ·Pr[M'] integrality and the matching marginals. I also audited D1–D4: D2's negative-correlation calculation is correct, and D4's pairing argument is sound because goods are never path endpoints, so a good loses desirability only when an incident edge is fixed. The only defect I found is a non-load-bearing overstatement: Observation B.7 is false as stated for i>Δ, but the proof of Theorem 4.8 uses it only for i≤Δ, where it holds because G_Δ goods are never removed. Thus no significant objection to the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a randomized polynomial-time algorithm for maximizing Nash social welfare (NSW) under additive valuations, achieving an approximation factor of e^{1/e} - c for a universal constant c > 0. The algorithm rounds a configuration LP solution. The analysis is a case split: if a constant fraction of agents are not 'well-behaved', Shmoys-Tardos rounding already beats e^{1/e} (Theorem 6.21); if the 'large good consistency property' fails, a reallocation beats e^{1/e} (Theorem 7.2); in the remaining case, a three-step algorithm using dependent partial rounding, shrinking of non-well-behaved agents, and small-good redistribution beats e^{1/e} (Theorem 8.1). A central technical bridge is Lemma 6.2, which identifies the expected log utility from ST rounding with the log NSW of a round-robin allocation in an artificial identical-valuation instance.","tokens_in":63317,"tokens_out":44474,"duration_ms":401549,"significance":"If correct, this is the first improvement over the eight-year-old e^{1/e} bound of Barman, Krishnamurthy, and Vaish, shows that the configuration LP integrality gap for unweighted NSW is strictly below e^{1/e}, and separates weighted from unweighted NSW with respect to the configuration LP. The proof is unusually detailed and auditable: the round-robin reduction, the configuration-LP upper bounds, and the dependent-partial-rounding properties are argued with explicit calculations and appendices. The improvement constant is tiny (estimated around 10^{-80}), but the theoretical separation is significant. The paper does not ship code, but the arguments are sufficiently explicit for independent verification.","major_comments":[{"comment":"The proof of Lemma 3.6 invokes Lemma 2.1 to claim that moving a bundle S_i from an agent holding a large good to a worse-off agent increases NSW. But Lemma 2.1 as stated requires v(S_j) ≥ v(S_i) and v(X_i \\ S_i) ≥ v(X_j \\ S_j), and its conclusion is that the product does not increase. In the transfer used in Lemma 3.6, S_j = ∅, so the hypothesis is reversed; the stated lemma would actually predict a decrease, not an increase. The same reversed use appears in the proof of Lemma 3.16. The product inequalities themselves are correct and can be verified by a direct calculation (for Lemma 3.6, the change in the two-agent product is v(S_i)(v(g)-v(X_j)) > 0). Because Lemma 3.6 supplies the upper bound on optimal NSW used throughout, this is a load-bearing proof repair, though local: add a reverse-swap lemma or replace the citations with the direct calculation.","section":"Sections 2 and 3.1 (Lemma 2.1 and Lemma 3.6)"}],"minor_comments":[{"comment":"Observation B.7 is stated as v(g'_i) ≥ v(g_i) without restricting i. As written this is false for i > Δ. The proof of Theorem 4.8 uses it only for i ∈ [Δ], where it holds because G_Δ goods are never removed; please state the observation with this restriction.","section":"Appendix B, Observation B.7"},{"comment":"The proof says the case where Property B is violated by agents with v(S_i) ≥ (1+γ)μ is 'similar'. Given the intricacy of the first case, it would help reproducibility to include the analogous argument in the appendix.","section":"Section 3.1, Lemma 3.15"},{"comment":"The final constant is set to ε = c*/2, and c* is on the order of γ^3 = 10^{-30} (Remark 9.1). Since the configuration LP solver runs in time polynomial in 1/ε, the running time has an enormous but constant factor; this is acceptable for a theoretical result but should be stated for clarity.","section":"Section 9, proof of Theorem 1.1"}],"recommendation":"major_revision","confidential_remarks":"The stress-test review found no fatal flaw in the central chain, and my own audit agrees with the soundness of the ST-rounding bridge and the Section 8 analysis. The main issue I found is the reversed application of Lemma 2.1 in Lemma 3.6 and Lemma 3.16; it is a local but load-bearing proof repair. The paper is very long, and the improvement constant is astronomically small, but the conceptual contribution—a strict separation between the configuration LP and the spending-restricted market equilibrium—is significant. I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this paper likely does what it claims. It gives an (e^{1/e} − c)-approximation for max Nash welfare with additive valuations, breaking the 2018 BKV bound, and does it via configuration LP rounding. That is a real result, not a numerical accident. The structural corollaries are legitimately interesting: the configuration LP gap for unweighted NSW is strictly below e^{1/e}, and so separates from the weighted case, where BFH+26 leave the gap at e^{1/e}.\n\nWhat is genuinely new: dependent partial rounding, the reduction of ST-rounding expected log-utility to log NSW of a round-robin allocation of an artificial instance (Lemma 6.2), and the large-good consistency dichotomy. I spot-checked several algebraic lemmas and the constant composition; they hold. The authors are also honest: Remark 9.1 says the constant is around 10^{-80}, and even optimized probably not better than 0.001. That disclosure helps, though the abstract's \"some constant c > 0\" is technically true but easy to misread as practically relevant.\n\nThe soft spots are real but manageable. The proof is long, and the load-bearing Lemma 6.2 plus the dependent partial rounding properties D1–D4 are intricate and partly relegated to appendices. With γ = 10^{-10}, a sign error would be invisible to casual checks. The stress-test went through the two-case swap in Lemma 6.2 and the D4 pairing, and found no flaw. I did spot one non-load-bearing overstatement: Observation B.7 is false as stated for i > Δ, but the proof only uses it for i ≤ Δ, so no damage. The constant is so small that the result is a structural statement, not an algorithmic recommendation; anyone wanting a usable algorithm should look elsewhere.\n\nWho should read this: researchers in fair division, configuration LP rounding, or approximation algorithms. It deserves a serious referee — an editor should not desk-reject it, though the referee should expect a heavy, technical proof. I would cite it, and I'd put it on a reading group schedule. My main caveat is verification burden; I'd want an independent pass on Section 8 before treating the constant as settled.","headline":"Likely real breakthrough: first improvement over e^{1/e} for Nash social welfare, but the constant is ~1e-80 and the proof is a heavy lift; the intricate core survives scrutiny.","tokens_in":63979,"tokens_out":2382,"would_cite":true,"duration_ms":52051,"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":"This paper claims an efficient randomized (e^{1/e} - c)-approximation algorithm for maximizing Nash social welfare under additive valuations, with c > 0 an absolute constant.","keywords":["Nash social welfare","additive valuations","configuration LP","rounding algorithm","round-robin allocation","dependent rounding","integrality gap","fair division"],"falsifier":"Enumerate small rational instances (e.g., 2 agents and 3 goods) and all feasible Delta; for each agent i and fractional allocation x, compute the exact distribution of the bucket-based rounding over all integral matchings and compare E[ln v_i(X_i)] with the log Nash welfare of the round-robin allocation of I_{i,x}(Delta). A single violation of the asserted inequality would falsify the main bridge and therefore Theorem 1.1. A less direct check: run the full algorithm on known worst-case families for e^{1/e} and look for empirical expected log welfare above LP-value minus 1/e; absence of any suc","tokens_in":62861,"feed_emoji":"⚖️","tokens_out":8005,"duration_ms":76475,"temperature":0.7,"pith_summary":"This paper tries to establish that the long-standing e^{1/e} approximation barrier for maximizing Nash social welfare with additive valuations is not the real limit: there exists an efficient randomized algorithm with ratio e^{1/e} - c for a fixed c > 0. The improvement comes from rounding the configuration LP and showing that its integrality gap for unweighted Nash welfare is strictly below e^{1/e}. If correct, this would be the first algorithmic improvement over the e^{1/e} bound, would show the configuration LP strictly beats the spending-restricted market-equilibrium gap, and would separate unweighted from weighted Nash welfare with respect to that LP. The paper locates the only structure where the old analysis is tight—agents it calls 'well-behaved'—and gives a three-step rounding scheme that handles that structure with dependent partial rounding and small-good redistribution.","feed_headline":"New algorithm beats the e^{1/e} barrier for Nash welfare","feed_subtitle":"The old e^{1/e} bound holds only in a specific worst-case structure; the new rounding escapes it.","key_machinery":"The load-bearing identity is Lemma 6.2: for a fractional allocation x and a feasible replication count Delta, the expected log utility ST(x,i) of the bucket-based rounding for agent i is at least the log Nash welfare of the round-robin allocation of the artificial instance I_{i,x}(Delta), an identical-valuations instance containing Delta copies of every good g with multiplicity Delta x_{i g}. This bridge converts small changes in a fractional bundle into adding or removing goods in an identical-valuations instance, where round-robin allocations have explicit Nash-welfare guarantees. Around it, the paper defines 'well-behaved' agents—those whose fractional large-good amount is 1-1/e and whose","core_discovery":"On the paper's own terms, the central claim is Theorem 1.1: an efficient randomized (e^{1/e} - c)-approximation for max Nash welfare under additive valuations. The proof works with a rational optimum of the configuration LP, converts it to a fractional allocation, and applies a bucket-based rounding for fractional matchings. For each agent, the expected log utility is lower bounded by the log Nash welfare of the round-robin allocation of an artificial identical-valuations instance built by replicating that agent's fractional bundle; this is the paper's main technical bridge. The old e^{1/e} analysis is shown to be tight only when agents are 'well-behaved'—a precise structure involving large","pith_inferences":["Editorial inference: if the well-behaved structure is the unique tight case, optimizing over its parameters could yield a larger explicit constant than the paper's 10^{-80}.","Editorial inference: the round-robin bridge likely transfers to other identical-valuations objectives, turning rounding analysis into add/remove-good perturbation arguments.","Editorial inference: because the weighted gap stays at e^{1/e}, transferring this unweighted algorithm to weighted Nash welfare would require new ideas, not small tweaks.","Testable extension: on synthetic instances with many well-behaved agents, one can check empirically that the dependent partial rounding's high-variance property holds; a collapse of variance would pinpoint a flawed step."],"forward_implications":["The approximation factor for unweighted Nash social welfare under additive valuations becomes e^{1/e} - c, the first strict improvement over e^{1/e}.","The configuration LP has an integrality gap strictly below e^{1/e} for unweighted Nash welfare, so it is strictly stronger than the spending-restricted market-equilibrium rounding used previously.","Weighted and unweighted Nash welfare are separated with respect to the configuration LP: the weighted gap remains e^{1/e}, while the unweighted gap is strictly smaller.","The three-step structure—well-behaved classification, dependent partial rounding, and small-good redistribution—gives a reusable template for beating e^{1/e} in other configuration-LP rounding problems.","Because the constant c exists but is tiny (on the order of 10^{-80}), the result is primarily an existence proof; algorithms that improve c by orders of magnitude would require new structural ideas."],"fun_headline_variants":["Beating e^(1/e) for Nash social welfare","First improvement over e^(1/e) for Nash welfare","Rounding beats e^(1/e) for Nash social welfare","Nash welfare: a constant better than e^(1/e)","Higher than e^(1/e): new Nash welfare algorithm"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof assumes that the expected log-utility produced by the rounding is always at least the log welfare of a certain round-robin allocation built from copies of each agent's fractional bundle; if this comparison fails for even one bucketing configuration, every improved bound in the paper collapses.","fun_headline_variants_meta":{"raw":{"variants":["Beating e^(1/e) for Nash social welfare","First improvement over e^(1/e) for Nash welfare","Rounding beats e^(1/e) for Nash social welfare","Nash welfare: a constant better than e^(1/e)","Higher than e^(1/e): new Nash welfare algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000293,"raw_usage":{"total_tokens":1463,"prompt_tokens":582,"completion_tokens":881,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":326,"completion_tokens_details":{"reasoning_tokens":799}},"tokens_in":326,"tokens_out":881,"duration_ms":8682,"temperature":1.0,"reasoning_tokens":799,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T05:28:52.346523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate small rational instances (e.g., 2 agents and 3 goods) and all feasible Delta; for each agent i and fractional allocation x, compute the exact distribution of the bucket-based rounding over all integral matchings and compare E[ln v_i(X_i)] with the log Nash welfare of the round-robin allocation of I_{i,x}(Delta). A single violation of the asserted inequality would falsify the main bridge and therefore Theorem 1.1. A less direct check: run the full algorithm on known worst-case families for e^{1/e} and look for empirical expected log welfare above LP-value minus 1/e; absence of any suc","supporting_citations":[],"review_version":1}