pith. sign in

arxiv: 2604.24120 · v1 · submitted 2026-04-27 · 💻 cs.DS

New Convex Programming Technique for Nash Social Welfare and Scheduling

Yuda Feng , Weijiang Hu , Shi Li This is my paper

Pith reviewed 2026-05-08 02:03 UTC · model grok-4.3

classification 💻 cs.DS
keywords Nash social welfareconvex programmingapproximation algorithmsintegrality gapfair allocationunrelated machine schedulinglinear programming
0
0 comments X

The pith

A new convex programming relaxation for weighted Nash social welfare matches the e^{1/e} approximation ratio and reduces to a compact polynomial-size linear program.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a new convex relaxation for maximizing weighted Nash social welfare. This relaxation supports an existing rounding procedure that produces an approximation factor of e to the power 1/e, yet it converts into a linear program whose size is polynomial in the input. In the unweighted case the program is equivalent to a known Fisher market formulation, which immediately shows that the integrality gap cannot be smaller. The same convex program also yields simpler proofs that recover the best approximation ratios for two unrelated-machine scheduling problems. These properties eliminate the need for the ellipsoid method or dual separation oracles required by prior exponential-size formulations.

Core claim

We introduce a convex program for the weighted Nash social welfare problem whose value, after appropriate rounding, is guaranteed to be at least 1 over e to the power 1/e of the optimal welfare. The program can be written as a compact linear program whose objective differs from the convex version by at most ln(1 + ε). When restricted to identical agents the program coincides with the restricted-spending Fisher market program, proving that its integrality gap is exactly e to the power 1/e. The same convex technique yields simple proofs of the best approximation ratios for two unrelated-machine scheduling problems.

What carries the argument

The new convex programming relaxation for weighted Nash social welfare that converts to a compact linear program while preserving the approximation guarantee under existing rounding.

Load-bearing premise

Existing rounding procedures for Nash social welfare continue to achieve the same approximation factor when applied to optimal solutions of this new relaxation rather than to earlier formulations.

What would settle it

A concrete small instance of weighted Nash social welfare on which rounding an optimal solution of the new linear program produces an allocation whose welfare is more than e to the power 1/e worse than the optimal integral allocation.

Figures

Figures reproduced from arXiv: 2604.24120 by Shi Li, Weijiang Hu, Yuda Feng.

Figure 1
Figure 1. Figure 1: Definition of hi(xi) and fi(xi) when |xi |1 > 1. The dark gray part denotes the 1 fractional largest items in xi . The light gray part denotes the V units of water. fi(xi) is the average height of the histogram on a logarithmic scale. 2.5 Creating Unweighted NSW Instance I with Identical Agents and EF1 Al￾location σ for a Fixed Agent i Let ρ be the random allocation given by the algorithm. In the analysis … view at source ↗
Figure 2
Figure 2. Figure 2: Liquidization Operations in Analysis of Rounding Algorithm in Section view at source ↗
read the original abstract

We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching $(e^{1/e}\approx 1.445)$-approximation via the rounding algorithm of Feng and Li. Unlike the exponential-size configuration LP used in prior work, our formulation can be converted into a compact linear program of polynomial size, incurring only an additive loss of $\ln(1+\epsilon)$ in the objective. This allows the program to be solved directly using standard LP solvers, without the ellipsoid method or dual separation oracles. In the unweighted case, we show that our convex program is equivalent to the restricted-spending Fisher market convex program of Cole and Gkatzelis, yielding a constructive proof that its integrality gap is exactly $e^{1/e}$. With a minor modification, our analysis also gives a simple proof of the $e^{1/e}$ EF1 gap for the identical agent setting. Finally, we show that our convex programming technique extends to two unrelated machine scheduling problems, recovering the best-known approximation ratios with simpler analyses.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a new convex programming relaxation for the weighted Nash social welfare (NSW) maximization problem. It claims this relaxation admits an (e^{1/e})-approximation by direct application of the rounding procedure from Feng and Li, and that the formulation can be converted into a compact polynomial-size LP with only an additive ln(1+ε) loss in the objective. In the unweighted case the new program is shown to be equivalent to the restricted-spending Fisher-market convex program of Cole and Gkatzelis, yielding a constructive proof that the integrality gap is exactly e^{1/e}. The same technique is extended to two unrelated-machine scheduling problems, recovering the best-known approximation ratios.

Significance. If the rounding transfer holds, the result supplies a computationally attractive, polynomial-size LP formulation for weighted NSW together with a matching approximation guarantee. The constructive equivalence proof for the unweighted case and the simple EF1-gap argument are also valuable. The extension to scheduling demonstrates broader applicability of the convex-programming technique.

major comments (2)
  1. [§3] §3 (or wherever the rounding is invoked): the manuscript asserts that any feasible solution to the new convex program can be fed directly into the Feng–Li rounding procedure while preserving the e^{1/e} guarantee. Because the new variables and constraints differ from those of the exponential configuration LP / Fisher-market formulation used in the original analysis, an explicit mapping (or invariant) must be exhibited that shows the per-agent marginal probabilities or configuration probabilities required by the expectation and concentration arguments are preserved. Without this mapping the transfer is not immediate.
  2. [§4] §4 (equivalence claim): the proof that the new convex program is equivalent to the Cole–Gkatzelis restricted-spending program should be checked for the precise sense of equivalence (same optimal value, or same feasible region up to a change of variables). If the equivalence is only approximate, the claimed exact integrality-gap result requires an additional error term.
minor comments (2)
  1. [Abstract] The abstract states that the compact LP incurs an additive loss of ln(1+ε); the main text should clarify whether this loss is with respect to the optimal value of the original convex program or with respect to the true NSW optimum.
  2. [§2] Notation for the new convex program (variables, objective, constraints) should be introduced once in a single display and then used consistently; several ad-hoc symbols appear without prior definition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight important points for rigor, and we address them point by point below. We will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (or wherever the rounding is invoked): the manuscript asserts that any feasible solution to the new convex program can be fed directly into the Feng–Li rounding procedure while preserving the e^{1/e} guarantee. Because the new variables and constraints differ from those of the exponential configuration LP / Fisher-market formulation used in the original analysis, an explicit mapping (or invariant) must be exhibited that shows the per-agent marginal probabilities or configuration probabilities required by the expectation and concentration arguments are preserved. Without this mapping the transfer is not immediate.

    Authors: We agree that an explicit mapping is required to make the transfer fully rigorous. Our formulation is derived by relaxing the configuration LP while preserving the key marginal probabilities x_{ij} (probability that agent i receives item j) and the per-agent geometric-mean constraints that encode the same expected log-utility and concentration invariants used by Feng and Li. We will add a short lemma (new Lemma 3.1) that formally exhibits the correspondence: any feasible solution to our convex program induces identical per-agent marginals and configuration probabilities (via the standard randomized rounding interpretation), so the expectation and Chernoff-type bounds carry over verbatim. This addition will be placed immediately before the rounding invocation in §3. revision: yes

  2. Referee: [§4] §4 (equivalence claim): the proof that the new convex program is equivalent to the Cole–Gkatzelis restricted-spending program should be checked for the precise sense of equivalence (same optimal value, or same feasible region up to a change of variables). If the equivalence is only approximate, the claimed exact integrality-gap result requires an additional error term.

    Authors: The equivalence established in §4 is exact in both senses: the programs attain the same optimal value, and their feasible regions are related by a bijective linear change of variables that preserves the objective exactly. The mapping is constructed by setting the new spending variables equal to the Cole–Gkatzelis restricted-spending variables and verifying that the geometric-mean constraints are equivalent under this substitution. Consequently, the integrality gap is precisely e^{1/e} with no additive or multiplicative error. We will revise the opening paragraph of §4 to state this precise equivalence explicitly and include the change-of-variables details in the proof. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new formulation and constructive equivalence are independent

full rationale

The paper introduces a new convex programming relaxation for weighted NSW that converts to a compact polynomial-size LP with only additive ln(1+ε) loss. The e^{1/e} approximation is obtained by applying the rounding procedure from prior work (Feng and Li), while the unweighted case establishes equivalence to the Cole and Gkatzelis restricted-spending Fisher market program via an explicit constructive proof of the integrality gap. This equivalence and the new LP formulation constitute independent content rather than a reduction to inputs by definition, fitting, or unverified self-citation chain. The self-citation supports an externally established rounding algorithm whose analysis is not redefined here, and extensions to scheduling problems recover known ratios with simpler analyses. No step matches the enumerated circularity patterns with a quotable reduction.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The paper relies on the new relaxation as an invented formulation whose correctness is proven within the work, along with standard assumptions from approximation algorithms literature.

free parameters (1)
  • epsilon
    Additive loss parameter for the approximation in converting to LP; chosen for desired accuracy.
axioms (1)
  • domain assumption The rounding algorithm of Feng and Li preserves the approximation ratio when applied to the new relaxation.
    Central to achieving the matching approximation.
invented entities (1)
  • New convex programming relaxation for weighted NSW no independent evidence
    purpose: To provide a compact formulation solvable by standard LP solvers while maintaining approximation guarantees.
    This is the main new contribution introduced in the paper.

pith-pipeline@v0.9.0 · 5484 in / 1414 out tokens · 55971 ms · 2026-05-08T02:03:37.642208+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Nash Social Welfare, Matrix Permanent, and Stable Polynomials

    Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67, pages 36:1–36:12, 2017. 2

    work page 2017

  2. [2]

    Grove, Ming-Yang Kao, P

    Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, and Jeffrey Scott Vitter. Load balancing in the L/sub p/norm. In36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pages 383–391, 1995. 4 17

    work page 1995

  3. [3]

    Convex Programming for Scheduling Unrelated Parallel Machines

    Yossi Azar and Amir Epstein. Convex Programming for Scheduling Unrelated Parallel Machines. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), page 331–337,

    work page 2005

  4. [4]

    Barbanel.The geometry of efficient fair division

    Julius B. Barbanel.The geometry of efficient fair division. Cambridge University Press, 2005. 1

    work page 2005

  5. [5]

    Finding Fair and Efficient Alloca- tions

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding Fair and Efficient Alloca- tions. InProceedings of the 2018 ACM Conference on Economics and Computation (EC 2018), pages 557–574, 2018. 2, 5

    work page 2018

  6. [6]

    Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps

    Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang. Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), 2026. 3

    work page 2026

  7. [7]

    Brams and Alan D

    Steven J. Brams and Alan D. Taylor.Fair division - from cake-cutting to dispute resolution. Cambridge University Press, 1996. 1

    work page 1996

  8. [8]

    Procaccia, editors.Handbook of Computational Social Choice

    Felix Brandt, Vincent Conitzer, Ulle Endriss, J´ erˆ ome Lang, and Ariel D. Procaccia, editors.Handbook of Computational Social Choice. Cambridge University Press, 2016. 1

    work page 2016

  9. [9]

    Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

    Adam Brown, Aditi Laddha, Madhusudhan Reddy Pittu, and Mohit Singh. Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 1307–1327, 2024. 2

    work page 2024

  10. [10]

    Bargaining Among Groups: An Axiomatic Viewpoint.International Journal of Game Theory, 39(1):71–88, 2010

    Suchan Chae and Herv´ e Moulin. Bargaining Among Groups: An Axiomatic Viewpoint.International Journal of Game Theory, 39(1):71–88, 2010. 1

    work page 2010

  11. [11]

    Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V

    Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod. Convex Program Duality, Fisher Markets, and Nash Social Welfare. InProceedings of the 2017 ACM Conference on Economics and Computation (EC 2017), pages 459–460, 2017. 2, 3, 5, 8

    work page 2017

  12. [12]

    Approximating the Nash Social Welfare with Indivisible Items

    Richard Cole and Vasilis Gkatzelis. Approximating the Nash Social Welfare with Indivisible Items. SIAM J. Comput., 47(3):1211–1236, 2018. 1, 5

    work page 2018

  13. [13]

    Bankruptcy to surplus: Sharing transboundary river basin’s water under scarcity.Water Resources Management, 32:2735–2751,

    Dagmawi Mulugeta Degefu, Weijun He, Liang Yuan, An Min, and Qi Zhang. Bankruptcy to surplus: Sharing transboundary river basin’s water under scarcity.Water Resources Management, 32:2735–2751,

    work page

  14. [14]

    Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations

    Yuda Feng, Yang Hu, Shi Li, and Ruilong Zhang. Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 1395–1405, 2025. 3

    work page 2025

  15. [15]

    A Note on Approximating Weighted Nash Social Welfare with Additive Valu- ations

    Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valu- ations. In51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297, pages 63:1–63:9, 2024. 2

    work page 2024

  16. [16]

    A Note on Approximating Weighted Nash Social Welfare with Additive Valua- tions.TheoretiCS, Volume 4, Aug 2025

    Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valua- tions.TheoretiCS, Volume 4, Aug 2025. 2, 3, 6, 7, 10

    work page 2025

  17. [17]

    Satiation in Fisher Markets and Approximation of Nash Social Welfare.Math

    Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Satiation in Fisher Markets and Approximation of Nash Social Welfare.Math. Oper. Res., 49(2):1109–1139, 2024. 1

    work page 2024

  18. [18]

    V´ egh, and Jan Vondr´ ak

    Jugal Garg, Edin Husic, Wenzheng Li, L´ aszl´ o A. V´ egh, and Jan Vondr´ ak. Approximating Nash Social Welfare by Matching and Local Search. InProceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pages 1298–1310, 2023. 3 18

    work page 2023

  19. [19]

    Approximating Nash Social Welfare under Submod- ular Valuations through (Un)Matchings.ACM Trans

    Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash Social Welfare under Submod- ular Valuations through (Un)Matchings.ACM Trans. Algorithms, 19(4):36:1–36:25 (SODA’20), 2023. 3

    work page 2023

  20. [20]

    David G. Harris. Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 2275–2304, 2024. 4

    work page 2024

  21. [21]

    Asymmetric Nash Solutions in the River Sharing Problem

    Harold Houba, Gerard van der Laan, and Yuyu Zeng. Asymmetric Nash Solutions in the River Sharing Problem. 2013, 2013. 1

    work page 2013

  22. [22]

    Improved Approximations for Unrelated Machine Scheduling

    Sungjin Im and Shi Li. Improved Approximations for Unrelated Machine Scheduling. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 2917–2946, 2023. 2, 4, 6, 15

    work page 2023

  23. [23]

    Weighted completion time minimization for unrelated machines via iterative fair contention resolution

    Sungjin Im and Maryam Shadloo. Weighted completion time minimization for unrelated machines via iterative fair contention resolution. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 2790–2809, 2020. 4

    work page 2020

  24. [24]

    Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

    Christos Kalaitzis, Ola Svensson, and Jakub Tarnawski. Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2654–2669, 2017. 2, 4, 6

    work page 2017

  25. [25]

    A unified approach to scheduling on unrelated parallel machines.Journal of the ACM (JACM), 56(5):28, 2009

    VS Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines.Journal of the ACM (JACM), 56(5):28, 2009. 4

    work page 2009

  26. [26]

    Bargaining in Committees as An Extension of Nash’s Bar- gaining Theory.Journal of Economic Theory, 132(1):291–305, 2007

    Annick Laruelle and Federico Valenciano. Bargaining in Committees as An Extension of Nash’s Bar- gaining Theory.Journal of Economic Theory, 132(1):291–305, 2007. 1

    work page 2007

  27. [27]

    APX-hardness of maximizing Nash social welfare with indivisible items.Inf

    Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items.Inf. Process. Lett., 122:17–20, 2017. 1

    work page 2017

  28. [28]

    Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs

    Shi Li. Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 553–571, 2025. 4

    work page 2025

  29. [29]

    Estimating the Nash Social Welfare for coverage and other submodular valuations

    Wenzheng Li and Jan Vondr´ ak. Estimating the Nash Social Welfare for coverage and other submodular valuations. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 1119–1130, 2021. 3

    work page 2021

  30. [30]

    MIT Press, 2003

    Herv´ e Moulin.Fair division and collective welfare. MIT Press, 2003. 1

    work page 2003

  31. [31]

    Computational complexity and approximability of social welfare optimization in multiagent resource allocation.Auton

    Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and J¨ org Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation.Auton. Agents Multi Agent Syst., 28(2):256–289, 2014. 1

    work page 2014

  32. [32]

    Robertson and William A

    Jack M. Robertson and William A. Webb.Cake-cutting algorithms - be fair if you can. A K Peters,

    work page

  33. [33]

    Springer texts in business and economics

    J¨ org Rothe, editor.Economics and Computation, An Introduction to Algorithmic Game Theory, Com- putational Social Choice, and Fair Division. Springer texts in business and economics. Springer, 2016. 1

    work page 2016

  34. [34]

    An approximation algorithm for the generalized assignment problem

    David B Shmoys and ´Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical programming, 62(1-3):461–474, 1993. 2, 4, 6, 16

    work page 1993

  35. [35]

    Replication Invariance of Bargaining Solutions.Int

    William Thomson. Replication Invariance of Bargaining Solutions.Int. J. Game Theory, 15(1):59–63, mar 1986. 1 19

    work page 1986

  36. [36]

    Peyton Young.Equity - in theory and practice

    H. Peyton Young.Equity - in theory and practice. Princeton University Press, 1995. 1

    work page 1995

  37. [37]

    S. Yu, E. C. van Ierland, H. P. Weikard, and X. Zhu. Nash Bargaining Solutions for International Cli- mate Agreements under Different Sets of Bargaining Weights.International Environmental Agreements: Politics, Law and Economics, 17(5):709–729, 2017. 1 A Solving Convex Programs CP(3)Approximately Convex program can be solved within an additive error ofϵfo...

    work page 2017