Pith. sign in

REVIEW 1 major objections 6 minor 66 references

Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities

T0 review · 1 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Capacitated Nash social welfare admits a (6+ε)-approximation under submodular one-sided valuations and a 1.33-approximation under subadditive two-sided valuations, both in strongly polynomial time, while two-sided Nash welfare is APX-hard…

desk verdict Solid constant-factor results for capacitated Nash welfare; the one-sided proof's suspicious step is actually fine once you track the parameter definitions. read the letter →

arxiv 2411.14007 v3 pith:ONODBIEH submitted 2024-11-21 cs.GT

Salil Gokhale , Harshul Sagar , Rohit Vaish , Vignesh Viswanathan , Jatin Yadav This is my paper · ORCID
classification cs.GT MSC 68W2591B32
keywords Nashsocialwelfarefairdivisioncapacityconstraintssubmodularvaluationssubadditiveapproximationalgorithmstwo-sidedmatchingmin-costflow
topics P versus NP
open problems P versus NP
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

The paper's goal is to show that capacity constraints do not make Nash social welfare maximization intractable in either of the two standard allocation models. For one-sided allocations of indivisible items with per-agent capacities, it claims a $(6+\varepsilon)$-approximation whenever valuations are submodular, running in strongly polynomial time with polynomially many value queries; for two-sided worker-firm matchings with firm capacities, it claims a $1.33$-approximation whenever firms have subadditive valuations. If both claims hold, these are the first constant-factor results for the capacitated one-sided submodular setting and a large improvement over the prior $\sqrt{\mathrm{OPT}}$ bound for the two-sided setting. The paper also proves that two-sided Nash welfare is APX-hard at factor $1.0000759$, so the approximation effort has a matching lower-bound direction.

What carries the argument

One-sided: the algorithm runs in three phases—a maximum-weight matching that fixes a set $H$ of items, a local search over the remaining items using only full and partial swaps so that every bundle has size $c_i-1$, and a final rematching of $H$. The analysis works with endowed valuations $\bar v_i(S)=v_i(S)+v_i(\ell(i))$ that add each agent's favourite remaining item, defines swap prices $p_{jk}=\max\{0,(v_i(R_i)-v_i(R_i-j+k))/v_i(R_i-j+k)\}$, and uses the price bound $\sum p\le 1$ plus an AM-GM bound to show the intermediate mapping $T$ has NSW at least $\mathrm{OPT}/6(1+\varepsilon)$. Two-sided: Lemma 4.2 shows subadditivity gives $\mathrm{NSW}(\mu)\le 1.33(\prod_i v_i(j_i)\prod_j w_j(\mu_j))^{1/(m+n)}$, reducing the objective to favourite-worker values and worker values; a min-cost flow network with a main and a secondary copy of each firm then maximizes the product in the bound in strongly polynomial time.

What would settle it

Concretely, expand Lemma 3.9's AM-GM chain with $n=2,m=3,\varepsilon=0.2$: the printed inequality $(6+4(m/n)\hat{\varepsilon})^n\le 6^n(1+\varepsilon)^n$ requires $1+(m/n)((1+\varepsilon)^n-1)\le 1+\varepsilon$, which is false, so verifying whether a corrected bound can keep the constant independent of $m$ is the direct test of the one-sided theorem.

Watch

Extended reading notes

Core claim

The paper's central claim is that capacity constraints do not push Nash social welfare maximization out of the constant-factor regime. In the one-sided model, where each agent may receive at most $c_i$ items, it gives a $(6+\varepsilon)$-approximation for monotone submodular valuations, in strongly polynomial time and with polynomially many value queries; this is the first constant-factor result for the capacitated submodular setting. In the two-sided model, where firms have capacities over workers and workers rank firms cardinally, it gives a $1.33$-approximation when firms have monotone subadditive valuations, improving on the earlier $\sqrt{\mathrm{OPT}}$ bound for additive valuations and matching a much broader domain. The same flow-based construction yields a PTAS when the number of firms is constant, and a weighted version of the configuration LP gives an $e^{1/e}+\epsilon$ approximation for additive valuations. Complementing these, the paper proves two-sided Nash welfare is APX-hard, inapproximable within $1.0000759$ unless P=NP, even with additive valuations and no capacities.

Load-bearing premise

The load-bearing premise is that the arithmetic-mean/geometric-mean estimate in the one-sided proof can be repaired to give a constant independent of $m$, since the printed version requires $1+(m/n)((1+\varepsilon)^n-1)\le 1+\varepsilon$, which fails when $m>1$.

Editorial extensions

If this is right

  • For the one-sided model under submodular valuations, capacities are no longer a barrier to constant-factor approximation: a $(6+\varepsilon)$ polynomial-time, value-query algorithm exists.
  • For the two-sided model under subadditive valuations, a single min-cost flow gives a $1.33$-approximation, improving the previous $\sqrt{\mathrm{OPT}}$ bound even for additive valuations.
  • Two-sided Nash welfare is computationally easier than utilitarian welfare in this setting, since utilitarian welfare retains an $e/(e-1)-\varepsilon$ hardness while Nash welfare has a constant-factor algorithm.
  • With a constant number of firms, the same flow construction yields a PTAS, and exhaustive search covers the small $m$ regime.
  • The weighted additive case inherits an $e^{1/e}+\epsilon$ approximation from the adapted configuration LP, and in the unweighted additive case the two methods combine to roughly $1.163$.

Reading between the lines

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

  • If the AM-GM bound in Lemma 3.9 cannot be repaired, the one-sided result is not a uniform $6+\varepsilon$ in $m$; a direct numerical test with $m>1$ and small $\varepsilon$ settles which constant the proof actually supports.
  • The two-sided argument uses subadditivity only through $v_i(\mu_i)\le |\mu_i|v_i(j_i)$, so the same min-cost-flow construction should work for any valuation class satisfying a top-worker bound, including possibly matroid or lower-quota variants of the matching problem.
  • The one-sided algorithm's reliance on swaps rather than one-way transfers is the natural bridge to matroid constraints, where exchange axioms play the role of the two-way transfer; the paper names matroid constraints as future work.
  • The weighted configuration-LP result depends on a separation oracle whose knapsack dynamic program may encounter negative $\alpha'_j$ values, so the $e^{1/e}+\epsilon$ guarantee should be treated as contingent on that oracle's correctness being pinned down.
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 / 6 minor

Summary. The paper studies capacity-constrained Nash social welfare (NSW) maximization in two preference models. For the one-sided model with submodular valuations, it gives a (6+ε)-approximation algorithm via a matching-based local search that uses two-way swaps to respect capacities (Theorem 3.1). For the two-sided model with subadditive firm valuations, it gives a 1.33-approximation via a single minimum-cost flow computation (Theorem 4.1). It also provides an e^{1/e+ε}-approximation for weighted two-sided NSW with additive valuations by adapting a configuration LP of Feng and Li (Theorem 5.1), a PTAS for a constant number of firms (Corollary 4.3), and an APX-hardness result (Theorem 6.1). The analysis builds on prior work by Garg et al. and Jain and Vaish.

Significance. These are strong results. The one-sided result is the first constant-factor approximation for capacitated submodular NSW; the two-sided result improves the prior sqrt(OPT) bound while covering subadditive valuations, and it exhibits a computational separation between Nash and utilitarian welfare. The two-sided proof is particularly clean: the min-cost-flow integrality argument and the subadditivity-based bound (Lemma 4.2) are correct and elegant. The one-sided proof adapts the local-search framework of Garg et al. with swap operations that preserve feasibility, and the high-level structure is sound. The paper ships reproducible, self-contained arguments for the main theorems, which is a significant strength. Several local corrections and clarifications are needed, but they do not undermine the central results.

major comments (1)
  1. [Section 5.1 and Appendix A.1] The approximate separation oracle for the dual of the configuration LP is under-specified with respect to zero and negative values. The quantities α'_j = (α_j - ζ_j ln w_j(i))/η_i can be negative because ln w_j(i) may be negative, and the text states "assume ln 0 = -∞" in the sorting step for η_i = 0. The dynamic program is described as finding the minimum sum of α'_j values subject to cardinality and rounded-value constraints, but the text does not justify that the DP remains correct with negative item costs, nor does it explain how infinite entries (from w_j(i) = 0 with positive ζ_j) are excluded from the DP and from the sorting rule. This is a gap in the proof of Theorem 5.1 as written; it should be repaired by a formal treatment of arbitrary real costs and by spelling out the convention for zero-valuation pairs.
minor comments (6)
  1. [Section 3, "Accuracy parameter" and Lemma 3.9] The symbol ε is used both for the target approximation and for the local-search threshold, making the definition ε = -1 + (1+ε)^{1/m} self-referential. Use a fresh symbol (e.g., δ) for the local-search parameter. The final inequality (6 + 4(m/n)ε̂)^n ≤ 6^n(1+ε)^n is valid with δ = -1 + (1+ε)^{1/m}, because (m/n)((1+δ)^n - 1) ≤ ε follows from monotonicity of ((1+x)^k - 1)/k for 0 ≤ k ≤ m; the attribution to Bernoulli is inaccurate and should be corrected.
  2. [Corollary 4.3 proof] The proof uses the inequality log(x)/(1+x) < 1/x^{0.75} for all x > 9, which is false (e.g., at x = 10, the left side is about 0.209 and the right side is about 0.178). The PTAS conclusion is still true, but a correct proof should verify log(x)/(1+x) < log(1+ε) directly from x > 1/ε^2 rather than through the false intermediate bound.
  3. [Section 5.2] The exponent in "e^{m/(e(m+n))}" should be n/(e(m+n)), since ∑_{i∈F} η_i = n/(m+n) when η_i = 1/(m+n) for all firms. As written, the claimed equality with e^{1/(e(x+1))} is algebraically incorrect.
  4. [Lemma 3.7] The stated inequality v(R-j) ≥ ∑_{k∈R}(v(R) - v(R-k)) is not true for arbitrary submodular valuations; for example, the additive valuation v(S)=|S| with R={a,b} gives 1 ≥ 2. The lemma relies on the endowed-valuation property v(∅)>0, and this hypothesis should be stated explicitly in the lemma.
  5. [Lemma 3.3 and Section 4] In the proof of Lemma 3.3, the chain "vi(J) ≤ (|J|+1)vi(∅)" appears to mix the endowed and non-endowed valuations; the tilde over v should be used consistently and the inequality should be justified via the endowed-valuation definition. Also, the two-sided flow network in Section 4 requires n ≤ m for feasibility; this follows from the positive-NSW assumption but is worth stating explicitly.
  6. [Theorem 5.1 statement] The approximation ratio in Theorem 5.1, typeset as "e(∑_{i∈F} η_i)/e+ϵ", is garbled; it should read e^{(∑_{i∈F} η_i)/e + ε}.

Circularity Check

1 steps flagged · score 1.0 of 10

No significant circularity: the central one-sided and two-sided theorems are derived from external lemmas and independent matching/flow arguments; the only self-referential passage is a non-load-bearing parameter-definition typo.

  1. self definitional [Section 3, paragraph 'Accuracy parameter' immediately before Algorithm 1]
    "Accuracy parameter. Our local search subroutine will use the parameter ε = −1 + (1 + ε)1/m such that the minimum multiplicative increase in NSW required to perform a swap is 1 + ε."

    The local-search threshold is defined using the same symbol ε as the target approximation, so as typeset it is a fixed-point equation rather than a definition; for m>1 its only nonnegative solution is ε=0, which trivializes the swap condition and is inconsistent with the subsequent use of ε̂=(1+ε)^n−1 in Lemma 3.9. The later bound (1+(m/n)ε̂)^n ≤ (1+ε)^n is only meaningful if the two ε's are distinct variables. This is a self-referential notation defect rather than a load-bearing reduction: introducing a fresh symbol δ=(1+ε)^{1/m}−1 fixes the proof, and no other part of the derivation depends on the confusion.

full rationale

This is a theory paper with no fitted data, so the fitted-input and renamed-prediction patterns do not apply. The one-sided result is an adaptation of Garg et al. [2023a]'s external matching-and-local-search framework; the capacity-specific modifications (two-way swaps, prices, endowed valuations) are proved from submodularity and the external Lemma 3.7, with the Phase-3 matching argument importing Lemma 3.11 from the same external source. The two-sided 1.33 result is self-contained: it constructs an integral min-cost flow, uses cost optimality to compare favorite-worker products, and applies the AM-GM bound in Lemma 4.2; it does not invoke any result of the present paper. The weighted section modifies the external configuration LP and rounding of Feng and Li [2024], and the hardness section imports an external APX-hardness lemma from Garg and Murhekar [2021]. Self-citations (Jain and Vaish [2024], Viswanathan and Zick [2023], Fitzsimmons et al. [2024]) supply problem definitions, motivation, and baselines, but no step of the main proofs reduces to them. The AM-GM step flagged by the reader is valid for n≤m (the function ((1+δ)^k−1)/k is increasing in k), even though the paper attributes it to Bernoulli's inequality; the weighted separation oracle in Appendix A.1 requires care with negative α'_j values but is a standard DP repair, not a circular argument. Apart from the non-load-bearing self-referential ε notation, I find no derivation step equivalent to its input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; the constants arise from closed-form analysis. The axioms are standard valuation assumptions plus two cited lemmas; the suspicious Bernoulli step and the negative-weight knapsack DP are the fragile premises.

assumptions (4)
  • domain assumption Endowed valuations vi(S) = vi(S)+vi(ℓ(i)) remain submodular and satisfy the price bound of Lemma 3.4.
    The one-sided analysis assumes this standard property of submodular valuations, and it is used in Lemmas 3.4 and 3.6.
  • ad hoc to paper The AM-GM/Bernoulli step in Lemma 3.9 yields (6+4(m/n)ε̂)^n ≤ 6^n(1+ε)^n.
    As typeset, the relation between ε̂ and ε does not justify the final bound; this is load-bearing for the (6+ε) constant.
  • domain assumption Feng and Li's rounding lemma: E[ln vi(μi)] ≥ Σ y_{i,S} ln vi(S) - 1/e.
    The weighted LP analysis invokes Lemma 4 of Feng and Li [2024] without reproducing its proof.
  • ad hoc to paper The knapsack DP in Appendix A.1 works with possibly negative α'_j values.
    The separation oracle minimizes Σ α'_j over sets, but α'_j can be negative when worker log-valuations are large; no shift is described.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities." pith.science (2026). https://pith.science/paper/ONODBIEH

@misc{pith2026241114007,
  author       = {Pith},
  title        = {Pith review of: Approximating One-Sided and Two-Sided Nash Social Welfare With Capacities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ONODBIEH}},
  note         = {Machine review of arXiv:2411.14007}
}
abstract

We study the problem of maximizing Nash social welfare, which is the geometric mean of agents' utilities, in two well-known models. The first model involves one-sided preferences, where a set of indivisible items is allocated among a group of agents (commonly studied in fair division). The second model deals with two-sided preferences, where a set of workers and firms, each having numerical valuations for the other side, are matched with each other (commonly studied in matching-under-preferences literature). We study these models under capacity constraints, which restrict the number of items (respectively, workers) that an agent (respectively, a firm) can receive. We develop constant-factor approximation algorithms for both problems under a broad class of valuations. Specifically, our main results are the following: (a) For any $\epsilon > 0$, a $(6+\epsilon)$-approximation algorithm for the one-sided problem when agents have submodular valuations, and (b) a $1.33$-approximation algorithm for the two-sided problem when the firms have subadditive valuations. The former result provides the first constant-factor approximation algorithm for Nash welfare in the one-sided problem with submodular valuations and capacities, while the latter result improves upon an existing $\sqrt{OPT}$-approximation algorithm for additive valuations. Our result for the two-sided setting also establishes a computational separation between the Nash and utilitarian welfare objectives. We also complement our algorithms with hardness-of-approximation results. Additionally, for the case of additive valuations, we modify the configuration LP of Feng and Li [ICALP 2024] to obtain an $(e^{1/e}+\epsilon)-$ approximation algorithm for weighted two-sided Nash social welfare under capacity constraints.

Figures

Figures reproduced from arXiv: 2411.14007 by the authors.

Figure 1
Figure 1. MIN-COST-FLOW network used in the proof of Theorem 4.1. The edge labels show the cost per unit flow and the lower and upper bounds on the flow. Lemma 4.2. Let I = ⟨F, W, V, W, C⟩ be an instance of CAPACITATED TWO-SIDED NSW with subaddi￾tive valuations and let µ be any feasible many-to-one matching for I. Let ji ∈ arg maxj∈µi vi(j) be firm i’s favourite worker in µi . Then, NSW(µ) ≤ 1.33  ∏i∈F vi(ji) ∏j∈W wj(µj)  1… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 58 canonical work pages

  1. [1]

    School Choice: A Mechanism Design Approach

    Atila Abdulkadiro g lu and Tayfun S \"o nmez. School Choice: A Mechanism Design Approach . American Economic Review, 93 0 (3): 0 729--747, 2003

    work page 2003

  2. [2]

    Maximizing Nash Social Welfare in 2-Value Instances

    Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, and Ernest van Wijland. Maximizing Nash Social Welfare in 2-Value Instances . In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, pages 4760--4767, 2022

    work page 2022

  3. [3]

    Fair Division of Indivisible Goods: Recent Progress and Open Questions

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Herv \'e Moulin, Alexandros A Voudouris, and Xiaowei Wu. Fair Division of Indivisible Goods: Recent Progress and Open Questions . Artificial Intelligence, page 103965, 2023

    2023

  4. [4]

    Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities

    Nima Anari, Tung Mai, Shayan Oveis Gharan, and Vijay V Vazirani. Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2274--2290, 2018

    work page 2018

  5. [5]

    Fair and Truthful Mechanisms for Dichotomous Valuations

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and Truthful Mechanisms for Dichotomous Valuations . In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, pages 5119--5126, 2021

    work page 2021

  6. [6]

    Finding Fair and Efficient Allocations

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding Fair and Efficient Allocations . In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557--574, 2018 a

    work page 2018

  7. [7]

    Greedy Algorithms for Maximizing Nash Social Welfare

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy Algorithms for Maximizing Nash Social Welfare . In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 7--13, 2018 b

    work page 2018

  8. [8]

    Tight Approximation Algorithms for p -Mean Welfare Under Subadditive Valuations

    Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G Sundaram. Tight Approximation Algorithms for p -Mean Welfare Under Subadditive Valuations . In Proceedings of the 28th Annual European Symposium on Algorithms, 2020

    work page 2020

Show all 66 references
  1. [9]

    Finding Fair and Efficient Allocations for Matroid Rank Valuations

    Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding Fair and Efficient Allocations for Matroid Rank Valuations . ACM Transactions on Economics and Computation, 9 0 (4): 0 1--41, 2021

    2021

  2. [10]

    Matroid Constrained Fair Allocation Problem

    Arpita Biswas and Siddharth Barman. Matroid Constrained Fair Allocation Problem . In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9921--9922, 2019

    2019

  3. [11]

    Handbook of Computational Social Choice

    Felix Brandt, Vincent Conitzer, Ulle Endriss, J \'e r \^o me Lang, and Ariel D Procaccia. Handbook of Computational Social Choice . Cambridge University Press, 2016

    2016

  4. [12]

    Fair Division with Allocator’s Preference

    Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao. Fair Division with Allocator’s Preference . In Proceedings of the 19th International Conference on Web and Internet Economics, pages 77--94. Springer, 2023

    2023

  5. [13]

    The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes

    Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes . Journal of Political Economy, 119 0 (6): 0 1061--1103, 2011

    2011

  6. [14]

    The Unreasonable Fairness of Maximum Nash Welfare

    Ioannis Caragiannis, David Kurokawa, Herv \'e Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare . ACM Transactions on Economics and Computation, 7 0 (3): 0 1--32, 2019

    2019

  7. [15]

    A Note on Finding Minimum Mean Cycle

    Mmanu Chaturvedi and Ross M McConnell. A Note on Finding Minimum Mean Cycle . Information Processing Letters, 127: 0 21--22, 2017

    2017

  8. [16]

    Fair and Efficient Allocations under Subadditive Valuations

    Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and Efficient Allocations under Subadditive Valuations . In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, pages 5269--5276, 2021

    2021

  9. [17]

    Fair Division of Indivisible Goods For a Class of Concave Valuations

    Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn. Fair Division of Indivisible Goods For a Class of Concave Valuations . Journal of Artificial Intelligence Research, 74: 0 111--142, 2022

    2022

  10. [18]

    Approximating the Nash Social Welfare with Indivisible Items

    Richard Cole and Vasilis Gkatzelis. Approximating the Nash Social Welfare with Indivisible Items . SIAM Journal on Computing, 47 0 (3): 0 1211--1236, 2018

    2018

  11. [19]

    Convex Program Duality, Fisher Markets, and Nash Social Welfare

    Richard Cole, Nikhil Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V Vazirani, and Sadra Yazdanbod. Convex Program Duality, Fisher Markets, and Nash Social Welfare . In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 459--460, 2017

    2017

  12. [20]

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

    Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, and Jan Vondr \'a k. A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations . In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 467--478, 2024

    2024

  13. [21]

    On Fair Division under Heterogeneous Matroid Constraints

    Amitay Dror, Michal Feldman, and Erel Segal-Halevi. On Fair Division under Heterogeneous Matroid Constraints . Journal of Artificial Intelligence Research, 76: 0 567--611, 2023

    2023

  14. [22]

    Consensus of Subjective Probabilities: The Pari-Mutuel Method

    Edmund Eisenberg and David Gale. Consensus of Subjective Probabilities: The Pari-Mutuel Method . The Annals of Mathematical Statistics, 30 0 (1): 0 165--168, 1959

    1959

  15. [23]

    A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

    Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations . In Procedings of the 51st International Colloquium on Automata, Languages, and Programming, pages 63--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024

    2024

  16. [24]

    On the Hardness of Fair Allocation under Ternary Valuations

    Zack Fitzsimmons, Vignesh Viswanathan, and Yair Zick. On the Hardness of Fair Allocation under Ternary Valuations . arXiv preprint arXiv:2403.00943, 2024

    2024 arXiv

  17. [25]

    A Fixed-Point Approach to Stable Matchings and Some Applications

    Tam \'a s Fleiner. A Fixed-Point Approach to Stable Matchings and Some Applications . Mathematics of Operations Research, 28 0 (1): 0 103--126, 2003

    2003

  18. [26]

    A Matroid Approach to Stable Matchings with Lower Quotas

    Tam \'a s Fleiner and Naoyuki Kamiyama. A Matroid Approach to Stable Matchings with Lower Quotas . Mathematics of Operations Research, 41 0 (2): 0 734--744, 2016

    2016

  19. [27]

    Two-Sided Matching Meets Fair Division

    Rupert Freeman, Evi Micha, and Nisarg Shah. Two-Sided Matching Meets Fair Division . In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pages 203--209, 2021

    2021

  20. [28]

    College Admissions and the Stability of Marriage

    David Gale and Lloyd S Shapley. College Admissions and the Stability of Marriage . The American Mathematical Monthly, 69 0 (1): 0 9--15, 1962

    1962

  21. [29]

    Computing fair and efficient allocations with few utility values

    Jugal Garg and Aniket Murhekar. Computing fair and efficient allocations with few utility values. In Proceedings of the 14th International Symposium on Algorithmic Game Theory, page 345–359, 2021

    2021

  22. [30]

    Approximating the Nash Social Welfare with Budget-Additive Valuations

    Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the Nash Social Welfare with Budget-Additive Valuations . In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2326--2340, 2018

    2018

  23. [31]

    Approximating Nash Social Welfare by Matching and Local Search

    Jugal Garg, Edin Husi \'c , Wenzheng Li, L \'a szl \'o A V \'e gh, and Jan Vondr \'a k. Approximating Nash Social Welfare by Matching and Local Search . In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1298--1310, 2023 a

    2023

  24. [32]

    Approximating Nash Social Welfare under Submodular Valuations through (un) Matchings

    Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating Nash Social Welfare under Submodular Valuations through (un) Matchings . ACM Transactions on Algorithms, 19 0 (4): 0 1--25, 2023 b

    2023

  25. [33]

    Satiation in Fisher Markets and Approximation of Nash Social Welfare

    Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Satiation in Fisher Markets and Approximation of Nash Social Welfare . Mathematics of Operations Research, 49 0 (2): 0 1109--1139, 2024

    2024

  26. [34]

    Finding Minimum-Cost Circulations by Canceling Negative Cycles

    Andrew V Goldberg and Robert E Tarjan. Finding Minimum-Cost Circulations by Canceling Negative Cycles . Journal of the ACM, 36 0 (4): 0 873--886, 1989

    1989

  27. [35]

    Near Fairness in Matroids

    Laurent Gourv \`e s, J \'e r \^o me Monnot, and Lydia Tlilane. Near Fairness in Matroids . In Proceedings of the 21st European Conference on Artificial Intelligence, pages 393--398, 2014

    2014

  28. [36]

    Towards Fair Allocation in Social Commerce Platforms

    Anjali Gupta, Shreyans J Nagori, Abhijnan Chakraborty, Rohit Vaish, Sayan Ranu, Prajit Prashant Nadkarni, Narendra Varma Dasararaju, and Muthusamy Chelliah. Towards Fair Allocation in Social Commerce Platforms . In Proceedings of the ACM Web Conference 2023, pages 3744--3754, 2023

    2023

  29. [37]

    The Stable Marriage Problem: Structure and Algorithms

    Dan Gusfield and Robert W Irving. The Stable Marriage Problem: Structure and Algorithms . MIT press, 1989

    1989

  30. [38]

    Fair Division with Two-Sided Preferences

    Ayumi Igarashi, Yasushi Kawase, Warut Suksompong, and Hanna Sumita. Fair Division with Two-Sided Preferences . Games and Economic Behavior, 147: 0 268--287, 2024

    2024

  31. [39]

    An Efficient Algorithm for the “Optimal” Stable Marriage

    Robert W Irving, Paul Leather, and Dan Gusfield. An Efficient Algorithm for the “Optimal” Stable Marriage . Journal of the ACM, 34 0 (3): 0 532--543, 1987

    1987

  32. [40]

    Maximizing Nash Social Welfare under Two-Sided Preferences

    Pallavi Jain and Rohit Vaish. Maximizing Nash Social Welfare under Two-Sided Preferences . In Proceedings of the 38th AAAI Conference on Artificial Intelligence, volume 38, pages 9798--9806, 2024

    2024

  33. [41]

    Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints

    Naoyuki Kamiyama. Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints . In Proceedings of the 8th International Symposium on Algorithmic Game Theory, pages 3--14. Springer, 2015

    2015

  34. [42]

    Popular Matchings with Ties and Matroid Constraints

    Naoyuki Kamiyama. Popular Matchings with Ties and Matroid Constraints . SIAM Journal on Discrete Mathematics, 31 0 (3): 0 1801--1819, 2017

    2017

  35. [43]

    The Nash Social Welfare Function

    Mamoru Kaneko and Kenjiro Nakamura. The Nash Social Welfare Function . Econometrica: Journal of the Econometric Society, pages 423--435, 1979

    1979

  36. [44]

    A Characterization of the Minimum Cycle Mean in a Digraph

    Richard M Karp. A Characterization of the Minimum Cycle Mean in a Digraph . Discrete Mathematics, 23 0 (3): 0 309--311, 1978

    1978

  37. [45]

    Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions

    Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions . Algorithmica, 52: 0 3--18, 2008

    2008

  38. [46]

    Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms , volume 10

    Donald Ervin Knuth. Stable Marriage and its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms , volume 10. American Mathematical Soc., 1997

    1997

  39. [47]

    APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

    Euiwoong Lee. APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items . Information Processing Letters, 122: 0 17--20, 2017

    2017

  40. [48]

    Algorithmics of Matching under Preferences , volume 2

    David Manlove. Algorithmics of Matching under Preferences , volume 2. World Scientific, 2013

    2013

  41. [49]

    Approximation Algorithms and Hardness Results for Fair Division with Indivisible Goods

    Evangelos Markakis. Approximation Algorithms and Hardness Results for Fair Division with Indivisible Goods . Trends in Computational Social Choice, pages 231--247, 2017

    2017

  42. [50]

    The Stable Marriage Problem

    David G McVitie and Leslie B Wilson. The Stable Marriage Problem . Communications of the ACM, 14 0 (7): 0 486--490, 1971

    1971

  43. [51]

    Fair Division and Collective Welfare

    Herv \'e Moulin. Fair Division and Collective Welfare . MIT press, 2004

    2004

  44. [52]

    On Achieving Leximin Fairness and Stability in Many-to-One Matchings

    Shivika Narang, Arpita Biswas, and Yadati Narahari. On Achieving Leximin Fairness and Stability in Many-to-One Matchings . In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 1705--1707, 2022

    2022

  45. [53]

    The Bargaining Problem

    John F Nash Jr. The Bargaining Problem . Econometrica: Journal of the Econometric Society, pages 155--162, 1950

    1950

  46. [54]

    Computational Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation

    Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and J \"o rg Rothe. Computational Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation . Autonomous Agents and Multi-Agent Systems, 28 0 (2): 0 256--289, 2014

    2014

  47. [55]

    Vazirani

    Noam Nisan, Tim Roughgarden, \'Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007

    2007

  48. [56]

    The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design

    Alvin E Roth and Elliott Peranson. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design . American Economic Review, 89 0 (4): 0 748--780, 1999

    1999

  49. [57]

    Two-Sided Matching

    Alvin E Roth and Marilda Sotomayor. Two-Sided Matching . Handbook of Game Theory with Economic Applications, 1: 0 485--541, 1992

    1992

  50. [58]

    o nmez, and M Utku \

    Alvin E Roth, Tayfun S \"o nmez, and M Utku \"U nver. Kidney Exchange . The Quarterly Journal of Economics, 119 0 (2): 0 457--488, 2004

    2004

  51. [59]

    Many-To-One Stable Matching: Geometry and Fairness

    Jay Sethuraman, Chung-Piaw Teo, and Liwen Qian. Many-To-One Stable Matching: Geometry and Fairness . Mathematics of Operations Research, 31 0 (3): 0 581--596, 2006

    2006

  52. [60]

    Efficient Nearly-Fair Division with Capacity Constraints

    Hila Shoshan, Noam Hazon, and Erel Segal-Halevi. Efficient Nearly-Fair Division with Capacity Constraints . In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 206--214, 2023

    2023

  53. [61]

    Constraints in Fair Division

    Warut Suksompong. Constraints in Fair Division . ACM SIGecom Exchanges, 19 0 (2): 0 46--61, 2021

    2021

  54. [62]

    The Geometry of Fractional Stable Matchings and its Applications

    Chung-Piaw Teo and Jay Sethuraman. The Geometry of Fractional Stable Matchings and its Applications . Mathematics of Operations Research, 23 0 (4): 0 874--891, 1998

    1998

  55. [63]

    Fair Reciprocal Recommendation in Matching Markets

    Yoji Tomita and Tomohiki Yokoyama. Fair Reciprocal Recommendation in Matching Markets . arXiv preprint arXiv:2409.00720, 2024

    2024 arXiv

  56. [64]

    A General Framework for Fair Allocation under Matroid Rank Valuations

    Vignesh Viswanathan and Yair Zick. A General Framework for Fair Allocation under Matroid Rank Valuations . In Proceedings of the 24th ACM Conference on Economics and Computation, pages 1129--1152, 2023

    2023

  57. [65]

    Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model

    Jan Vondr \'a k. Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model . In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 67--74, 2008

    2008

  58. [66]

    Budget-Feasible Maximum Nash Social Welfare is Almost Envy-free

    Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-Feasible Maximum Nash Social Welfare is Almost Envy-free . In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pages 465--471, 2021

    2021

Pith tools

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