Dividing indivisible goods among agents is a basic problem in fair division and in the design of allocation mechanisms. Among the objectives one can maximize, the Nash social welfare (the geometric mean of the agents' utilities) is singled out because it balances efficiency and fairness: it is scale-invariant in each agent's valuation and its maximizers have strong fairness properties. Maximizing it is NP-hard and APX-hard even for additive valuations (Garg, Hoefer, Mehlhorn 2018 show inapproximability within 1.069 unless P = NP; Viswanathan 2026 gives 1.076 under the Unique Games Conjecture).
A line of market-equilibrium algorithms culminated in an approximation factor of for additive valuations (Barman, Krishnamurthy, Vaish 2018; Cole, Gkatzelis 2015; Cole et al. 2017), and more recent rounding algorithms for the weighted problem reached the same factor (Feng, Li 2025). The linear and convex relaxations used for the weighted problem have matching integrality gaps, but no lower bound rules out improving in the unweighted case. Whether is tight was asked explicitly in the survey of Amanatidis et al. (2023).
Timeline:
An instance has agents and goods . Agent values good at and a bundle at . An allocation is an -subpartition of . Its Nash social welfare is
and is the maximum over allocations. A randomized algorithm is an -approximation if its output satisfies .
The algorithm works through three objects.
The Lean development uses the namespace NSWBetter, with Inst, nsw, IsCLPSolution, lpVal, bucket, IsSTScheme, ST, rrBundle, largeCount, meanVal and WellBehaved for these objects.
There are a constant , a polynomial and a polynomial-time algorithm reading fair coins such that for every instance with nonnegative rational additive valuations and every allocation ,
The constant is not fixed (the paper estimates ), so the goal survives any improvement.
The result shows that is not the right approximation factor for unweighted additive Nash welfare, which separates the unweighted problem from the weighted one, where the known relaxations have integrality gap . The structural results of Section 3 describe exactly when round robin, and hence ST rounding of the configuration LP, is no better than ; they are reusable for any analysis that compares an allocation with the Lemma 3.6 bound.
The result is proved on paper in a 78-page preprint; none of it is machine-checked. A formalization would check a long case analysis with explicit small constants (, , , ) where arithmetic slips are easy, and would produce a formal library for configuration LPs, Shmoys–Tardos rounding and round-robin allocations.
The baseline analysis (Lemma 4.2 with Lemmas 3.1 and 4.5) gives exactly and is tight on well-behaved instances, so no slack can be found by sharpening it. The improvement has to come from the instances where it is tight: the paper isolates them (Properties A–E), proves a strict gain whenever they fail (Theorem 3.9), and for the remaining instances builds two new fractional allocations: one moving fractions of inconsistently large goods (Section 5), and a dependent partial rounding of large goods followed by redistribution of small goods (Section 6). The obvious alternative of rounding large goods integrally does not work: making one agent's utility makes the Nash welfare .
Agents and goods are Fin n and Fin m; inputs are nonnegative rationals; allocations are Fin m → Option (Fin n). Logarithms of quantities that may vanish are taken in EReal with (elog), so that a zero utility cannot be rewarded by Lean's Real.log 0 = 0. Polynomial time is Turing.TM2ComputableInPolyTime over fixed binary encodings (the platform's OnlineCRS.Combine and ReserveLB encodings); randomness is a uniform coin string of fixed polynomial length. Statements about hold for every rounding scheme with the Marginals, Cardinality and Rationality properties and every value order; constants are absolute (chosen before the instance). Hypotheses that are vacuous or trivializing are excluded: the comparator in the goal is every allocation, not a supremum; outputs are decoded totally, so malformed output can only lower the welfare.
The development needs: the configuration LP and its fractional allocation, the Shmoys–Tardos buckets and rounding distributions, round-robin allocations of multisets of values, large goods and well-behaved instances, artificial instances, and the algorithmic encodings. The Section 3 results and the bucket/ST machinery are reusable beyond this mission. Proofs of milestones, alternative arguments, and lemmas of the paper not listed as milestones (Facts 2.2–2.9, Lemmas 4.4–4.20, the properties (D1)–(D4) of dependent partial rounding) are welcome.
namespace NSWBetter
/-- **Theorem 1.1 — a better-than-e^(1/e) approximation for Nash social welfare.**
Viswanathan, *A Better-than-e^{1/e} Approximation Algorithm for Nash Social Welfare under Additive Valuations*, arXiv:2607.13340 (held version, sha256 08811cb4…), Theorem 1.1, p.3 (restated and proved p.48): "There exists an efficient randomized (e^(1/e) − c)-approximation algorithm for maximizing Nash social welfare when agents have additive valuations, for some constant c > 0." Approximation, p.9: "An allocation X is said to be an α-approximation (α ≥ 1) of the max Nash welfare for some instance I if NSW(X) ≥ (1/α)NSW(I)"; the proof (p.48) concludes `E[NSW(X)] ≥ NSW(I)/e^(1/e − c∗/2)`.
There are a constant `c > 0`, a polynomial `p` and a Turing machine `A`, polynomial time in the binary encoding of `(I, coins)`, such that for every instance `I` with nonnegative rational additive valuations and every allocation `Y`, `NSW(Y) ≤ (e^(1/e) − c) · E_w[NSW(X_w)]`, where `X_w` is the allocation output on coin string `w` and `w` is uniform of length `p(|enc I|)`.
**Formalization Note.** Randomness is a uniform coin string of fixed polynomial length given to a deterministic machine. Outputs are lists of naturals decoded totally into `n`-subpartitions (`decodeAlloc`). The comparator is every allocation, so the bound is against `NSW(I)` without a maximum or a division. -/
theorem theorem_1_1 :
∃ c : ℝ, 0 < c ∧
∃ (p : Polynomial ℕ) (A : Inst × List Bool → List ℕ),
Nonempty (Turing.TM2ComputableInPolyTime encInstCoins ReserveLB.encListNat A) ∧
∀ I : Inst, I.WellFormed → ∀ Y : Alloc I,
nsw I Y ≤ (Real.exp (1 / Real.exp 1) - c) *
coinAvg (p.eval (encInst I).length) (fun w => nsw I (decodeAlloc I (A (I, w)))) := by sorry
end NSWBetter
There are a constant , a polynomial and a randomized polynomial-time algorithm (a deterministic polynomial-time algorithm reading a uniformly random string of fair coins) such that for every instance with additive valuations given by nonnegative rationals, the allocation output by satisfies
that is, . Here and allocations are -subpartitions of the goods.
This is the first improvement over the approximation factor for maximizing Nash social welfare under additive valuations.
Differences from the source:
Turing.TM2ComputableInPolyTime map of (encoded instance, coin string), the guarantee holding for the average over all coin strings of length ; reason: the standard model of randomized polynomial time; the rational-probability steps of the paper (dependent rounding p.38, ST rounding p.16) are sampled with fair coins to accuracy , and since the loss is absorbed by the slack between and on p.48Fin n, Fin m, Fin m → Option (Fin n), outputs as lists of naturals decoded totally; reason: an algorithm's input is finite; Lean convention; same instancesTuring.TM2ComputableInPolyTime over fixed binary encodings over OnlineCRS.Combine.Sym; reason: Mathlib's Turing-machine model; binary numbers make the input length the bit sizeNo submissions yet on this mission's goal. Log in and be the first to prove it.