Pith. sign in

REVIEW 1 major objections 3 minor 157 references

A Better-than-$e^{1/e}$ Approximation Algorithm for Nash Social Welfare under Additive Valuations

T0 review · 1 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2607.13340 v1 pith:TXVB7ZBE submitted 2026-07-14 cs.GT cs.DS

Vignesh Viswanathan This is my paper
classification cs.GTcs.DS MSC 68W2591B32
keywords NashsocialwelfareadditivevaluationsconfigurationLProundingalgorithmround-robinallocationdependentintegralitygapfairdivision
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

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.

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 (1)
  1. [Sections 2 and 3.1 (Lemma 2.1 and Lemma 3.6)] 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.
minor comments (3)
  1. [Appendix B, Observation B.7] 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.
  2. [Section 3.1, Lemma 3.15] 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.
  3. [Section 9, proof of Theorem 1.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained and not reduced to its own inputs by construction.

full rationale

The paper's central chain is a genuine derivation, not a disguised restatement of an assumption. The benchmark is the configuration LP objective P_i,S y_i,S ln v_i(S), an external upper bound on log optimal Nash welfare; the algorithm then proves E[ST(z)] >= that objective - 1/e + c. No parameter is fitted to make the conclusion true: gamma and the various constants are fixed in advance (gamma = 10^-10), and every strict-improvement lemma is proved directly from the round-robin lower bounds and the large/small-good upper bound (Lemma 3.6). Lemma 6.2, the bridge from Shmoys-Tardos rounding to round-robin allocations, is proved by an explicit swap argument using Lemma 2.1 and the Marginals/Cardinality/Rationality properties of the matching, not imported from prior work. The 'well-behaved' taxonomy is reverse-engineered from the equality case of the BKV18 e^{1/e} bound, but that is standard tight-analysis: the paper proves that if Properties A-E fail, the strict improvement follows, rather than assuming the strict improvement. The citations to FL25, BKV18, BFH+26, and GKPS06 are independent prior results; the one self-citation ([Vis26]) appears only in the introductory hardness context and is not load-bearing for Theorem 1.1. No prediction reduces by construction to a fitted parameter, and no 'uniqueness' claim is imported from the author's own prior work without proof. The only concern noted by a close reader (Observation B.7 being false as stated for i > Delta) is a non-load-bearing overstatement and, in any case, is a correctness issue, not a circularity issue.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The mathematics is largely self-contained apart from standard inequalities and cited LP/rounding subroutines. The only hand-tuned quantity is γ = 10^{-10}, an analysis parameter absent from the theorem statement. No constants are fitted to data; no predictions are tuned to match the answer. The main conceptual debt is the well-behaved/large-good-consistency taxonomy, which is reverse-engineered to make the case analysis go through. No invented entities: the artificial instance I_{i,x}(Δ) is a proof device constructed from the input, not a postulated object with external falsifiable handles.

free parameters (1)
  • γ = 10^{-10}
    Hand-chosen tiny constant. Every threshold in the paper (γn, γ²n, γ³n, 10^{-4}γ², etc.) and ultimately the final c (Remark 9.1 puts it near 10^{-80}) is an artifact of this choice. It is an analysis parameter that does not appear in the theorem statement, not a value fitted to data.
assumptions (6)
  • domain assumption The configuration LP for max log-NSW under additive valuations is solvable in polynomial time up to an additive ln(1+ε) error and can be taken rational ([FL25, Thm 2.1], Remarks 2.6–2.7).
    Section 2.1; the algorithm's efficiency and the existence of a feasible Δ depend on this. The paper inherits this theorem from a recent cited work.
  • standard math Shmoys-Tardos rounding yields an integral matching with exact Marginals, Cardinality, and Rationality properties via Birkhoff-von Neumann / [Bir46, GKPS06].
    Section 6; Lemma 6.2 requires Δ·Pr[M=M'] integer (feasible Δ) and each full bucket matched with probability 1. Standard but load-bearing.
  • domain assumption Assumption 3.5: every identical-valuation instance analyzed has at least Δ positively valued goods.
    Section 3; needed so all logarithms are defined. Discharged for artificial instances by Lemma 6.4 using the LP solution's support.
  • standard math Fact 2.3 (x^{1/x} maximized at e), Fact 2.4 (ln(1+x) ≥ x/(1+x)), Jensen's inequality, AM-GM.
    Used pervasively in Sections 3–8 to produce the 1/e term and the additive constants.
  • standard math Round-robin allocations are EF1 and monotone in the picking order (Facts 2.8–2.9).
    Section 2.2; the basis of all Section 3 lower bounds on logNSW(W).
  • ad hoc to paper The well-behaved structure (Properties A–E and their fractional-bundle analogues) is the exact equality case of the BKV18 bound.
    Definitions 3.2–3.7 and 6.7–6.14. Reverse-engineered from the worst case; legitimate, but the dichotomy's exhaustiveness (Theorem 3.9) is where the entire argument could fail silently.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Better-than-$e^{1/e}$ Approximation Algorithm for Nash Social Welfare under Additive Valuations." pith.science (2026). https://pith.science/paper/TXVB7ZBE

@misc{pith2026260713340,
  author       = {Pith},
  title        = {Pith review of: A Better-than-$e^1/e$ Approximation Algorithm for Nash Social Welfare under Additive Valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TXVB7ZBE}},
  note         = {Machine review of arXiv:2607.13340}
}
abstract

We present an $(e^{1/e} - c)$-approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant $c > 0$. This result improves upon the previous best-known approximation factor of $e^{1/e}$ [Barman, Krishnamurthy and Vaish, EC 2018].

Figures

Figures reproduced from arXiv: 2607.13340 by the authors.

Figure 1
Figure 1. Structure of the fractional bundle xi of a well-behaved agent i. Each good g is drawn as a bar whose width is the fractional amount xig and whose height is the value vi(g) (assuming vi(g1) ≥ vi(g2) ≥ · · · ≥ vi(gm)). The first few goods are large goods, valued significantly higher than the small goods, and the total fractional amount of large goods is exactly 1 − 1/e. for some constant c ∗ 1 > 0. Therefore, if a con… view at source ↗
Figure 2
Figure 2. Bucketing construction for agent i. The fractional bundle xi is divided into ki = 3 buckets, each of size at most 1. We construct these buckets for each agent i ∈ N. Let Bi = {b 1 , . . . , bki} be the set of buckets constructed for agent i, and let B = S i∈N Bi be the set of buckets constructed for all agents i ∈ N. We use these buckets to construct an edge weighted bipartite graph G(x) over the set of nodes B ∪G. … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

157 extracted references · 1 canonical work pages

  1. [1]

    , title =

    Brent, Richard P. , title =. Journal of the ACM , pages =. 1976 , volume =

    1976

  2. [2]

    2025 , booktitle = proc #

    Feng, Yuda and Hu, Yang and Li, Shi and Zhang, Ruilong , title =. 2025 , booktitle = proc #

    2025

  3. [3]

    , title =

    Harris, David G. , title =. ACM Trans. Algorithms , articleno =. 2025 , volume =

    2025

  4. [4]

    Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines , volume =

    Bansal, Nikhil and Srinivasan, Aravind and Svensson, Ola , journal =. Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines , volume =

  5. [5]

    Davis, C. S. , title =. Journal of the Australian Mathematical Society , series =. 1978 , doi =

    1978

  6. [6]

    Vignesh Viswanathan , title =

  7. [7]

    APX-hardness of maximizing Nash social welfare with indivisible items , url =

    Euiwoong Lee , date-added =. APX-hardness of maximizing Nash social welfare with indivisible items , url =. Information Processing Letters , keywords =. 2017 , bdsk-url-1 =. doi:https://doi.org/10.1016/j.ipl.2017.01.012 , issn =

    work page doi:10.1016/j.ipl.2017.01.012 2017

  8. [8]

    Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions , volume =

    Aziz, Haris and Li, Bo and Moulin, Herv\'. Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions , volume =. SIGecom Exchanges , month = nov, number =

Show all 157 references
  1. [9]

    Fair allocation of indivisible goods: Improvements and generalizations , year =

    Ghodsi, Mohammad and HajiAghayi, MohammadTaghi and Seddighin, Masoud and Seddighin, Saeed and Yami, Hadi , booktitle = proc #. Fair allocation of indivisible goods: Improvements and generalizations , year =

  2. [10]

    A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations , year =

    Dobzinski, Shahar and Li, Wenzheng and Rubinstein, Aviad and Vondr\'. A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations , year =

  3. [11]

    CoRR , title =

    Haris Aziz and Bo Li and Herv. CoRR , title =

  4. [12]

    Fair and Truthful Mechanisms for Dichotomous Valuations , year =

    Moshe Babaioff and Tomer Ezra and Uriel Feige , booktitle = proc #. Fair and Truthful Mechanisms for Dichotomous Valuations , year =

  5. [13]

    , journal =

    Brualdi, Richard A. , journal =. Comments on bases in dependence structures , volume =

  6. [14]

    Fair Allocation of Indivisible Goods to Asymmetric Agents , volume =

    Farhadi, Alireza and Ghodsi, Mohammad and Hajiaghayi, MohammadTaghi and Lahaie, S\'. Fair Allocation of Indivisible Goods to Asymmetric Agents , volume =. Journal of Artificial Intelligence Research , number =

  7. [15]

    Fair-Share Allocations for Agents with Arbitrary Entitlements , year =

    Babaioff, Moshe and Ezra, Tomer and Feige, Uriel , booktitle = proc #. Fair-Share Allocations for Agents with Arbitrary Entitlements , year =

  8. [16]

    Weighted Fairness Notions for Indivisible Items Revisited , year =

    Chakraborty, Mithun and Segal-Halevi, Erel and Suksompong, Warut , journal = proc #. Weighted Fairness Notions for Indivisible Items Revisited , year =

  9. [17]

    Picking sequences and monotonicity in weighted fair division , volume =

    Mithun Chakraborty and Ulrike Schmidt-Kraepelin and Warut Suksompong , journal =. Picking sequences and monotonicity in weighted fair division , volume =

  10. [18]

    A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation , volume =

    Haris Aziz and Herv. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation , volume =. Operations Research Letters , number =

  11. [19]

    Computing Fair and Efficient Allocations with Few Utility Values , year =

    Garg, Jugal and Murhekar, Aniket , booktitle = proc #. Computing Fair and Efficient Allocations with Few Utility Values , year =

  12. [20]

    Fair and efficient allocations of chores under bivalued preferences , year =

    Garg, Jugal and Murhekar, Aniket and Qin, John , booktitle = proc #. Fair and efficient allocations of chores under bivalued preferences , year =

  13. [21]

    How to Fairly Allocate Easy and Difficult Chores , year =

    Ebadian, Soroush and Peters, Dominik and Shah, Nisarg , booktitle = proc #. How to Fairly Allocate Easy and Difficult Chores , year =

  14. [22]

    Voudouris , journal =

    Georgios Amanatidis and Georgios Birmpas and Aris Filos-Ratsikas and Alexandros Hollender and Alexandros A. Voudouris , journal =. Maximum

  15. [23]

    Maximizing

    Hannaneh Akrami and Bhaskar Ray Chaudhury and Martin Hoefer and Kurt Mehlhorn and Marco Schmalhofer and Golnoosh Shahkarami and Giovanna Varricchio and Quentin Vermande and Ernest van Wijland , booktitle = proc #. Maximizing

  16. [24]

    A General Framework for Fair Allocation under Matroid Rank Valuations , year =

    Viswanathan, Vignesh and Zick, Yair , booktitle = proc #. A General Framework for Fair Allocation under Matroid Rank Valuations , year =

  17. [25]

    Complexity of approximating bounded variants of optimization problems , volume =

    Miroslav Chleb. Complexity of approximating bounded variants of optimization problems , volume =. Theoretical Computer Science , number =

  18. [26]

    Truthful and Fair Mechanisms for Matroid-Rank Valuations , year =

    Barman, Siddharth and Verma, Paritosh , booktitle = proc #. Truthful and Fair Mechanisms for Matroid-Rank Valuations , year =

  19. [27]

    Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations , year =

    Viswanathan, Vignesh and Zick, Yair , booktitle = proc #. Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations , year =

  20. [28]

    Fairness Towards Groups of Agents in the Allocation of Indivisible Items , year =

    Nawal Benabbou and Mithun Chakraborty and Edith Elkind and Yair Zick , booktitle = proc #. Fairness Towards Groups of Agents in the Allocation of Indivisible Items , year =

  21. [29]

    Finding Fair and Efficient Allocations for Matroid Rank Valuations , volume =

    Nawal Benabbou and Mithun Chakraborty and Ayumi Igarashi and Yair Zick , journal =. Finding Fair and Efficient Allocations for Matroid Rank Valuations , volume =

  22. [30]

    Minimal dependent sets , volume =

    Asche, DS , journal =. Minimal dependent sets , volume =

  23. [31]

    , isbn =

    Nisan, Noam and Roughgarden, Tim and Tardos, Eva and Vazirani, Vijay V. , isbn =. Algorithmic Game Theory , year =

  24. [32]

    Combinatorial Algorithm for Restricted Max-Min Fair Allocation , volume =

    Annamalai, Chidambaram and Kalaitzis, Christos and Svensson, Ola , journal =. Combinatorial Algorithm for Restricted Max-Min Fair Allocation , volume =

  25. [33]

    Bansal, Nikhil and Sviridenko, Maxim , booktitle =. The

  26. [34]

    Papadimitriou and Mihalis Yannakakis , journal =

    Christos H. Papadimitriou and Mihalis Yannakakis , journal =. Optimization, approximation, and complexity classes , volume =

  27. [35]

    Submodular functions, matroids, and certain polyhedra , year =

    Edmonds, Jack , booktitle =. Submodular functions, matroids, and certain polyhedra , year =

  28. [36]

    Fair Allocation of Indivisible Goods , year =

    Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet , booktitle =. Fair Allocation of Indivisible Goods , year =

  29. [37]

    Collective choice under dichotomous preferences , volume =

    Anna Bogomolnaia and Herv. Collective choice under dichotomous preferences , volume =. Journal of Economic Theory , number =

  30. [38]

    Fair allocation of indivisible goods and chores , volume =

    Aziz, Haris and Caragiannis, Ioannis and Igarashi, Ayumi and Walsh, Toby , journal =. Fair allocation of indivisible goods and chores , volume =

  31. [39]

    Umang Bhaskar and A. R. Sricharan and Rohit Vaish , booktitle = proc #. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources , year =

  32. [40]

    Approximating Maximin Shares with Mixed Manna , year =

    Rucha Kulkarni and Ruta Mehta and Setareh Taki , booktitle = proc #. Approximating Maximin Shares with Mixed Manna , year =

  33. [41]

    Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences , year =

    Hadi Hosseini and Sujoy Sikdar and Rohit Vaish and Lirong Xia , booktitle = proc #. Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences , year =

  34. [42]

    Fair and Efficient Allocations under Lexicographic Preferences , year =

    Hadi Hosseini and Sujoy Sikdar and Rohit Vaish and Lirong Xia , booktitle = proc #. Fair and Efficient Allocations under Lexicographic Preferences , year =

  35. [43]

    Weighted Notions of Fairness with Binary Supermodular Chores , year =

    Viswanathan, Vignesh and Zick, Yair , journal =. Weighted Notions of Fairness with Binary Supermodular Chores , year =

  36. [44]

    On Representatives of Subsets , volume =

    Hall, Phillip , journal =. On Representatives of Subsets , volume =

  37. [45]

    Approximating

    Garg, Jugal and Husi\'. Approximating

  38. [46]

    Fair Chore Division under Binary Supermodular Costs , year =

    Siddharth Barman and Vishnu Narayan and Paritosh Verma , booktitle = proc #. Fair Chore Division under Binary Supermodular Costs , year =

  39. [47]

    Fair Allocation of Two Types of Chores , year =

    Haris Aziz and Jeremy Lindsay and Angus Ritossa and Mashbat Suzuki , booktitle = proc #. Fair Allocation of Two Types of Chores , year =

  40. [48]

    Kelso and Vincent P

    Alexander S. Kelso and Vincent P. Crawford , journal =. Job Matching, Coalition Formation, and Gross Substitutes , volume =

  41. [49]

    Combinatorial Auctions with Decreasing Marginal Utilities , year =

    Lehmann, Benny and Lehmann, Daniel and Nisan, Noam , booktitle = proc #. Combinatorial Auctions with Decreasing Marginal Utilities , year =

  42. [50]

    On the PTAS for Maximin Shares in an Indivisible Mixed Manna , year =

    Kulkarni, Rucha and Mehta, Ruta and Taki, Setareh , booktitle = proc #. On the PTAS for Maximin Shares in an Indivisible Mixed Manna , year =

  43. [51]

    arXiv , author =:2006.04428 , primaryclass =

    Envy-free Relaxations for Goods, Chores, and Mixed Items , year =. arXiv , author =:2006.04428 , primaryclass =

    2006 arXiv

  44. [52]

    and Shah, Nisarg , issn =

    Kurokawa, David and Procaccia, Ariel D. and Shah, Nisarg , issn =. Leximin Allocations in the Real World , volume =. ACM Transactions of Economics and Computation , number =

  45. [53]

    Single-Value Combinatorial Auctions and Algorithmic Implementation in Undominated Strategies , volume =

    Babaioff, Moshe and Lavi, Ron and Pavlov, Elan , issn =. Single-Value Combinatorial Auctions and Algorithmic Implementation in Undominated Strategies , volume =. Journal of the ACM , number =

  46. [54]

    and Yazdanbod, Sadra , booktitle =

    Cole, Richard and Devanur, Nikhil and Gkatzelis, Vasilis and Jain, Kamal and Mai, Tung and Vazirani, Vijay V. and Yazdanbod, Sadra , booktitle =. Convex Program Duality, Fisher Markets, and Nash Social Welfare , year =

  47. [55]

    Strategyproof Multi-Item Exchange under Single-Minded Dichotomous Preferences , volume =

    Aziz, Haris , issn =. Strategyproof Multi-Item Exchange under Single-Minded Dichotomous Preferences , volume =. Autonomous Agents and Multi-Agent Systems , number =

  48. [56]

    On maximum weighted Nash welfare for binary valuations , volume =

    Warut Suksompong and Nicholas Teh , issn =. On maximum weighted Nash welfare for binary valuations , volume =. Mathematical Social Sciences , pages =

  49. [57]

    Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations , year =

    Barman, Siddharth and Verma, Paritosh , booktitle = proc #. Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations , year =

  50. [58]

    Implementation in multidimensional dichotomous domains , volume =

    Mishra, Debasis and Roy, Souvik , journal =. Implementation in multidimensional dichotomous domains , volume =

  51. [59]

    Roth and Tayfun S

    Alvin E. Roth and Tayfun S. Pairwise kidney exchange , volume =. Journal of Economic Theory , number =

  52. [60]

    Mathematical Social Sciences , pages =

    Ortega, Josu. Mathematical Social Sciences , pages =

  53. [61]

    Truthful and Fair Mechanisms for Matroid-Rank Valuations , year =

    Siddharth Barman and Paritosh Verma , booktitle = proc #. Truthful and Fair Mechanisms for Matroid-Rank Valuations , year =

  54. [62]

    Finding Fair and Efficient Allocations , year =

    Siddharth Barman and Sanath Kumar Krishnamurthy and Rohit Vaish , journal = proc #. Finding Fair and Efficient Allocations , year =

  55. [63]

    Lo, Jacky and Wilson, Mark C , title =

  56. [64]

    and Mathieu, Claire and Nguyen, C

    Azar, Yossi and Birnbaum, Benjamin and Karlin, Anna R. and Mathieu, Claire and Nguyen, C. Thach , booktitle = proc #. Improved Approximation Algorithms for Budgeted Allocations , year =

  57. [65]

    Budgeted Allocations in the Full-Information Setting , year =

    Srinivasan, Aravind , booktitle = proc #. Budgeted Allocations in the Full-Information Setting , year =

  58. [66]

    Approximation Algorithms for Budget-Constrained Auctions , year =

    Garg, Rahul and Kumar, Vijay and Pandit, Vinayaka , booktitle = proc #. Approximation Algorithms for Budget-Constrained Auctions , year =

  59. [67]

    Auctions with Budget Constraints , year =

    Andelman, Nir and Mansour, Yishay , booktitle =. Auctions with Budget Constraints , year =

  60. [68]

    An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem , year =

    Kalaitzis, Christos , booktitle = proc #. An Improved Approximation Guarantee for the Maximum Budgeted Allocation Problem , year =

  61. [69]

    On the Configuration LP for Maximum Budgeted Allocation , volume =

    Kalaitzis, Christos and Madry, Aleksander and Newman, Alantha and Pol\'a. On the Configuration LP for Maximum Budgeted Allocation , volume =. Mathematical Programming , number =

  62. [70]

    Fair and Efficient Allocations of Chores under Bivalued Preferences , type =

    Jugal Garg and Aniket Murhekar and John Qin , institution =. Fair and Efficient Allocations of Chores under Bivalued Preferences , type =

  63. [71]

    How to Fairly Allocate Easy and Difficult Chores , volume =

    Soroush Ebadian and Dominik Peters and Nisarg Shah , journal =. How to Fairly Allocate Easy and Difficult Chores , volume =

  64. [72]

    The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes

    Budish, Eric , journal =. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. , volume =

  65. [73]

    Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings , volume =

    Garg, Jugal and Kulkarni, Pooja and Kulkarni, Rucha , journal =. Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings , volume =

  66. [74]

    Approximating the nash social welfare with budget-additive valuations , year =

    Garg, Jugal and Hoefer, Martin and Mehlhorn, Kurt , booktitle = proc #. Approximating the nash social welfare with budget-additive valuations , year =

  67. [75]

    Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation , volume =

    Eric Budish and G. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation , volume =. Operations Research , number =

  68. [76]

    , journal =

    Goldman, Jonathan and Procaccia, Ariel D. , journal =. Spliddit: Unleashing Fair Division Algorithms , volume =

  69. [77]

    Matroid Theory , year =

    James Oxley , edition =. Matroid Theory , year =

  70. [78]

    Submodular Function Maximization , year =

    Krause, Andreas and Golovin, Daniel , booktitle =. Submodular Function Maximization , year =

  71. [79]

    ACM Transactions on Economics and Computation , title =

    Chakraborty, Mithun and Igarashi, Ayumi and Suksompong, Warut and Zick, Yair , issn =. ACM Transactions on Economics and Computation , title =

  72. [80]

    Almost Envy-Freeness with General Valuations , type =

    Benjamin Plaut and Tim Roughgarden , institution =. Almost Envy-Freeness with General Valuations , type =

  73. [81]

    and Wang, Junxing , booktitle = proc #

    Procaccia, Ariel D. and Wang, Junxing , booktitle = proc #. Fair Enough: Guaranteeing Approximate Maximin Shares , year =

  74. [82]

    The Unreasonable Fairness of Maximum Nash Welfare , volume =

    Caragiannis, Ioannis and Kurokawa, David and Moulin, Herv\'. The Unreasonable Fairness of Maximum Nash Welfare , volume =. ACM Trans. Econ. Comput. , month = sep, number =

  75. [83]

    2026 , booktitle = proc #

    Bei, Xiaohui and Feng, Yuda and Hu, Yang and Li, Shi and Zhang, Ruilong , title =. 2026 , booktitle = proc #

    2026

  76. [84]

    On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP , volume =

    Chakrabarty, Deeparnab and Goel, Gagan , journal =. On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP , volume =

  77. [85]

    Nash Social Welfare, Matrix Permanent, and Stable Polynomials , year =

    Nima Anari and Shayan Oveis Gharan and Amin Saberi and Mohit Singh , booktitle = proc #. Nash Social Welfare, Matrix Permanent, and Stable Polynomials , year =

  78. [86]

    The Unreasonable Fairness of Maximum

    Caragiannis, Ioannis and Kurokawa, David and Moulin, Herv\'. The Unreasonable Fairness of Maximum

  79. [87]

    , publisher =

    Schrijver, A. , publisher =

  80. [88]

    Greedy Algorithms for Maximizing Nash Social Welfare , year =

    Barman, Siddharth and Krishnamurthy, Sanath Kumar and Vaish, Rohit , booktitle = proc #. Greedy Algorithms for Maximizing Nash Social Welfare , year =

  81. [89]

    and Psomas, Alexandros and Shah, Nisarg , booktitle = proc #

    Halpern, Daniel and Procaccia, Ariel D. and Psomas, Alexandros and Shah, Nisarg , booktitle = proc #. Fair Division with Binary Valuations: One Rule to Rule Them All , year =

  82. [90]

    Maximizing Nash product social welfare in allocating indivisible goods , volume =

    Andreas Darmann and Joachim Schauer , journal =. Maximizing Nash product social welfare in allocating indivisible goods , volume =

  83. [91]

    Lipton, R. J. and Markakis, E. and Mossel, E. and Saberi, A. , booktitle = proc #. On Approximately Fair Allocations of Indivisible Goods , year =

  84. [92]

    and Wang, Junxing , journal =

    Kurokawa, David and Procaccia, Ariel D. and Wang, Junxing , journal =. Fair Enough:

  85. [93]

    Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations , year =

    Siddharth Barman and Paritosh Verma , booktitle = proc #. Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations , year =

  86. [94]

    Truthful and Fair Mechanisms for Matroid-Rank Valuations , volume =

    Siddharth Barman and Paritosh Verma , journal =. Truthful and Fair Mechanisms for Matroid-Rank Valuations , volume =

  87. [95]

    Faster Matroid Intersection , year =

    Chakrabarty, Deeparnab and Tat Lee, Yin and Sidford, Aaron and Singla, Sahil and Chiu-wai Wong, Sam , booktitle = proc #. Faster Matroid Intersection , year =

  88. [96]

    Dividing Good and Great Items Among Agents with Bivalued Submodular Valuations , year =

    Cyrus Cousins and Vignesh Viswanathan and Yair Zick , booktitle = proc #. Dividing Good and Great Items Among Agents with Bivalued Submodular Valuations , year =

  89. [97]

    The Good, the Bad and the Submodular:

    Cyrus Cousins and Vignesh Viswanathan and Yair Zick , booktitle = proc #. The Good, the Bad and the Submodular:

  90. [98]

    and Spielman, Daniel A

    Daitch, Samuel I. and Spielman, Daniel A. , booktitle = proc #. Faster Approximate Lossy Generalized Flow via Interior Point Algorithms , year =

  91. [99]

    Groupwise Maximin Fair Allocation of Indivisible Goods , year =

    Siddharth Barman and Arpita Biswas and Sanath Kumar Krishna Murthy and Yadati Narahari , booktitle = proc #. Groupwise Maximin Fair Allocation of Indivisible Goods , year =

  92. [100]

    Approximating the Nash Social Welfare with Indivisible Items , year =

    Cole, Richard and Gkatzelis, Vasilis , booktitle = proc #. Approximating the Nash Social Welfare with Indivisible Items , year =

  93. [101]

    Fair Public Decision Making , year =

    Conitzer, Vincent and Freeman, Rupert and Shah, Nisarg , booktitle = proc #. Fair Public Decision Making , year =

  94. [102]

    A constant-factor approximation algorithm for

    Wenzheng Li and Jan Vondrak , booktitle = proc #. A constant-factor approximation algorithm for

  95. [103]

    On Allocating Goods to Maximize Fairness , year =

    Chakrabarty, Deeparnab and Chuzhoy, Julia and Khanna, Sanjeev , booktitle = proc #. On Allocating Goods to Maximize Fairness , year =

  96. [104]

    Maximizing

    Pallavi Jain and Rohit Vaish , booktitle = proc #. Maximizing

  97. [105]

    Euiwoong Lee , journal =

  98. [106]

    Approximating

    Garg, Jugal and Husi\'. Approximating. Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC) , numpages =

  99. [107]

    Tractable Fragments of the Maximum

    Garg, Jugal and Husi. Tractable Fragments of the Maximum. 2021 , bdsk-url-1 =. doi:10.48550/ARXIV.2112.10199 , institution =

    2021 doi arXiv

  100. [108]

    Lenstra, J. K. and Shmoys, D. B. and Tardos, \'. Approximation Algorithms for Scheduling Unrelated Parallel Machines , volume =. Math. Program. , month = feb, number =

  101. [109]

    On (1, ) -Restricted Assignment Makespan Minimization , year =

    Deeparnab Chakrabarty and Sanjeev Khanna and Shi Li , booktitle = proc #. On (1, ) -Restricted Assignment Makespan Minimization , year =

  102. [110]

    Almost (Weighted) Proportional Allocations for Indivisible Chores , year =

    Li, Bo and Li, Yingkai and Wu, Xiaowei , booktitle =. Almost (Weighted) Proportional Allocations for Indivisible Chores , year =

  103. [111]

    Weighted Maxmin Fair Share Allocation of Indivisible Chores , year =

    Aziz, Haris and Chan, Hau and Li, Bo , booktitle = proc #. Weighted Maxmin Fair Share Allocation of Indivisible Chores , year =

  104. [112]

    Fairness behind a veil of ignorance:

    Heidari, Hoda and Ferrari, Claudio and Gummadi, Krishna and Krause, Andreas , booktitle =. Fairness behind a veil of ignorance:

  105. [113]

    Bounds and Applications of Concentration of Measure in Fair Machine Learning and Data Science , year =

    Cousins, Cyrus , publisher =. Bounds and Applications of Concentration of Measure in Fair Machine Learning and Data Science , year =

  106. [114]

    An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning , year =

    Cousins, Cyrus , booktitle = proc #. An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning , year =

  107. [115]

    Uncertainty and the Social Planner's Problem:

    Cousins, Cyrus , booktitle =. Uncertainty and the Social Planner's Problem:

  108. [116]

    Revisiting Fair-

    Cousins, Cyrus , booktitle =. Revisiting Fair-

  109. [117]

    Fair division and collective welfare , year =

    Moulin, Herv. Fair division and collective welfare , year =

  110. [118]

    Arnold , publisher =

    Barry C. Arnold , publisher =

  111. [119]

    2024 , bdsk-url-1 =

    On the Hardness of Fair Allocation under Ternary Valuations , url =. 2024 , bdsk-url-1 =. arXiv , author =:2403.00943 , primaryclass =

    2024 arXiv

  112. [120]

    Maximizing

    Akrami, Hannaneh and Chaudhury, Bhaskar Ray and Hoefer, Martin and Mehlhorn, Kurt and Schmalhofer, Marco and Shahkarami, Golnoosh and Varricchio, Giovanna and Vermande, Quentin and van Wijland, Ernest , copyright =. Maximizing. 2022 , bdsk-url-1 =. doi:10.48550/ARXIV.2207.1094...

    2022 doi

  113. [121]

    Tight approximation algorithms for

    Barman, Siddharth and Bhaskar, Umang and Krishna, Anand and Sundaram, Ranjani G , journal =. Tight approximation algorithms for

  114. [122]

    The hardness of approximation:

    Erez Petrank , journal =. The hardness of approximation:

  115. [123]

    Parameterized and approximation complexity of Partial VC Dimension , volume =

    Cristina Bazgan and Florent Foucaud and Florian Sikora , journal =. Parameterized and approximation complexity of Partial VC Dimension , volume =

  116. [124]

    Fair division of indivisible goods: Recent progress and open questions , volume =

    Georgios Amanatidis and Haris Aziz and Georgios Birmpas and Aris Filos-Ratsikas and Bo Li and Herv. Fair division of indivisible goods: Recent progress and open questions , volume =. Artificial Intelligence , pages =

  117. [125]

    Paola Alimonti and Viggo Kann , journal =. Some

  118. [126]

    Approximation Hardness of Short Symmetric Instances of

    Piotr Berman and Marek Karpinski and Alexander Scott , journal =. Approximation Hardness of Short Symmetric Instances of

  119. [127]

    Karp , booktitle =

    R. Karp , booktitle =. Reducibility among combinatorial problems , year =

  120. [128]

    Garey and D

    M. Garey and D. Johnson , publisher =. Computers and Intractability:

  121. [129]

    Structured Preferences , year =

    Edith Elkind and Martin Lackner and Dominik Peters , booktitle =. Structured Preferences , year =

  122. [130]

    Brooks, R. L. , journal =. On colouring the nodes of a network , volume =

  123. [131]

    Almost envy-freeness with general valuations , volume =

    Benjamin Plaut and Tim Roughgarden , journal =. Almost envy-freeness with general valuations , volume =

  124. [132]

    Papadimitriou and M

    C. Papadimitriou and M. Yannakakis , journal = jacm, number =. The complexity of restricted spanning tree problems , volume =

  125. [133]

    Gonzalez , journal =

    T. Gonzalez , journal =. Clustering to Minimize the Maximum Intercluster Distance , volume =

  126. [134]

    G. Cs. Popularity and Perfectness in One-sided Matching Markets with Capacities , type =

  127. [135]

    Edwin Romeijn , booktitle =

    Dolores Romero Morales and H. Edwin Romeijn , booktitle =. The Generalized Assignment Problem and Extensions , year =

  128. [136]

    A Survey of the Generalized Assignment Problem and Its Applications , volume =

    Temel. A Survey of the Generalized Assignment Problem and Its Applications , volume =. INFOR: Information Systems and Operational Research , number =

  129. [137]

    The Submodular Welfare Problem with Demand Queries , volume =

    Feige, Uriel and Vondr\'ak, Jan , journal =. The Submodular Welfare Problem with Demand Queries , volume =

  130. [138]

    Goemans and Vahab Mirrokni and Maxim Sviridenko , booktitle = proc #

    Lisa Fleischer and Michel X. Goemans and Vahab Mirrokni and Maxim Sviridenko , booktitle = proc #. Tight Approximation Algorithms for Maximum General Assignment Problems , year =

  131. [139]

    A PTAS for the multiple knapsack problem , year =

    Chekuri, Chandra and Khanna, Sanjeev , booktitle = proc #. A PTAS for the multiple knapsack problem , year =

  132. [140]

    Shmoys and

    David B. Shmoys and. An Approximation Algorithm for the Generalized Assignment Problem , volume =. Mathematical Programming , number =

  133. [141]

    Some Optimal Inapproximability Results , volume =

    H. Some Optimal Inapproximability Results , volume =. Journal of the ACM , number =

  134. [142]

    Proof Verification and Hardness of Approximation Problems , volume =

    Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario , journal =. Proof Verification and Hardness of Approximation Problems , volume =

  135. [143]

    Probabilistic Checking of Proofs: A New Characterization of NP , volume =

    Arora, Sanjeev and Safra, Shmuel , journal =. Probabilistic Checking of Proofs: A New Characterization of NP , volume =

  136. [144]

    On the Power of Unique 2-Prover 1-Round Games , year =

    Khot, Subhash , booktitle = proc #. On the Power of Unique 2-Prover 1-Round Games , year =

  137. [145]

    Vertex Cover Might Be Hard to Approximate to Within 2 - , volume =

    Khot, Subhash and Regev, Oded , journal =. Vertex Cover Might Be Hard to Approximate to Within 2 - , volume =

  138. [146]

    Optimal Inapproximability Results for

    Khot, Subhash and Kindler, Guy and Mossel, Elchanan and O'Donnell, Ryan , journal =. Optimal Inapproximability Results for

  139. [147]

    Optimal algorithms and inapproximability results for every CSP? , year =

    Raghavendra, Prasad , booktitle = proc #. Optimal algorithms and inapproximability results for every CSP? , year =

  140. [148]

    Optimal Long Code Test with One Free Bit , year =

    Bansal, Nikhil and Khot, Subhash , booktitle = proc #. Optimal Long Code Test with One Free Bit , year =

  141. [149]

    Conditional hardness of precedence constrained scheduling on identical machines , year =

    Svensson, Ola , booktitle = proc #. Conditional hardness of precedence constrained scheduling on identical machines , year =

  142. [150]

    Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems , year =

    Bansal, Nikhil and Khot, Subhash , booktitle = proc #. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems , year =

  143. [151]

    Voudouris , booktitle = proc #

    Georgios Amanatidis and Georgios Birmpas and Aris Filos-Ratsikas and Alexandros A. Voudouris , booktitle = proc #. Fair Division of Indivisible Goods: A Survey , year =

  144. [152]

    Gaussian Bounds for Noise Correlation of Functions , volume =

    Mossel, Elchanan , journal =. Gaussian Bounds for Noise Correlation of Functions , volume =

  145. [153]

    Analysis of Boolean Functions , year =

    O'Donnell, Ryan , publisher =. Analysis of Boolean Functions , year =

  146. [154]

    A Note on Approximating Weighted Nash Social Welfare with Additive Valuations , volume =

    Yuda Feng and Shi Li , eid = 17, issn =. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations , volume =. TheoretiCS , keywords =

  147. [155]

    Approximation Resistant Predicates from Pairwise Independence , volume =

    Per Austrin and Elchanan Mossel , journal =. Approximation Resistant Predicates from Pairwise Independence , volume =

  148. [156]

    Birkhoff , journal =

    G. Birkhoff , journal =. Tres observaciones sobre el

  149. [157]

    Dependent rounding and its applications to approximation algorithms , volume =

    Rajiv Gandhi and Samir Khuller and Srinivasan Parthasarathy and Aravind Srinivasan , date-modified =. Dependent rounding and its applications to approximation algorithms , volume =. Journal of the ACM , number =. 2006 , bdsk-url-1 =

    2006

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.