Simultaneous EF1 and approximate MMS allocations for submodular valuations

Assaf Fine; Uriel Feige

arxiv: 2606.06451 · v1 · pith:W2224U5Anew · submitted 2026-06-04 · 💻 cs.GT

Simultaneous EF1 and approximate MMS allocations for submodular valuations

Uriel Feige , Assaf Fine This is my paper

Pith reviewed 2026-06-27 23:01 UTC · model grok-4.3

classification 💻 cs.GT

keywords fair divisionindivisible goodssubmodular valuationsmaximin shareEF1MMSenvy-freeness

0 comments

The pith

Allocations can be both constant-factor MMS and EF1 for agents with submodular valuations.

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

The paper proves that when allocating indivisible items to agents whose valuations are submodular, there exist allocations that meet both a constant-factor maximin-share guarantee and the EF1 envy-freeness condition. These two fairness classes do not in general imply each other, so simultaneous satisfaction is nontrivial. The result extends the same style of guarantee that was already known for additive valuations to the strictly larger class of submodular valuations.

Core claim

We design allocations that simultaneously satisfy ρ-MMS for constant ρ and EF1 (in fact also EFL) when agents have submodular valuations.

What carries the argument

An allocation construction that extends the techniques and constants known to work for additive valuations to the submodular case while preserving both the constant-factor MMS bound and the EF1 property.

If this is right

Agents with submodular valuations receive allocations that are fair according to both share-based and comparison-based criteria at once.
The same constant factors established for additive valuations remain valid after the extension.
Existence holds for arbitrary numbers of agents and items under submodular preferences.
The result applies equally to the stronger EFL notion in addition to EF1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same simultaneous guarantees may hold for other valuation classes that lie between additive and submodular.
If the construction is algorithmic rather than purely existential, it would yield polynomial-time methods for producing the allocations.
Real-world settings with diminishing marginal returns could adopt the same dual fairness standard without extra computational cost.

Load-bearing premise

The methods and constants that produce simultaneous fairness for additive valuations continue to work when valuations are submodular.

What would settle it

A concrete instance with submodular valuations in which no allocation is both EF1 and ρ-MMS for any fixed constant ρ.

read the original abstract

There are two common classes of fairness notions that are considered when allocating $m$ indivisible items to $n$ agents of equal entitlements. One is that of share-based fairness notions, with the maximin share (MMS) and its relaxations to $\rho$-MMS being prominent representatives of this class. The other is that of comparison-based fairness notions, with envy-freeness (EF) and its relaxations such as EF1 being prominent representatives of this class. In general, no class offers good guarantees for the other class. In this work, we design allocations that simultaneously satisfy notions from both classes, and specifically, are $\rho$-MMS for constant $\rho$ and EF1 (in fact, also EFL). Such results were previously known when agents have additive valuations, and we prove such results for the more general class of submodular valuations.

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.

Desk Editor's Note private letter to a colleague

Extends simultaneous EF1 and constant-ρ MMS existence to submodular valuations with no visible flaws in the claim.

read the letter

The main thing to know is that this paper shows allocations exist that are both EF1 and ρ-MMS for constant ρ when valuations are submodular, extending the prior additive case.

The new contribution is the generalization itself. The abstract makes clear that the result also gives EFL, and that the constants stay independent of n and m. That is useful because submodular functions cover diminishing returns settings that come up often.

The paper states the two fairness classes cleanly and notes why combining them is not automatic. It does a reasonable job positioning the work against the additive literature.

Soft spots are limited. The abstract gives no proof steps, so soundness rests on the full argument, but the stress-test found no internal inconsistency or assumption that would break when moving from additive to submodular. No circularity or invented entities appear.

This is for people working on fair division of indivisible goods in algorithmic game theory. A reader interested in simultaneous guarantees across share-based and comparison-based notions would get direct value. It deserves a serious referee because the extension is non-trivial in a standard setting.

I recommend sending it to peer review.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to prove the existence of allocations of m indivisible items to n agents with submodular valuations that simultaneously satisfy EF1 (and EFL) and ρ-MMS for some constant ρ independent of n and m. This extends prior results known only for additive valuations by showing that the same combined guarantees hold in the more general submodular setting.

Significance. If the central existence result holds, it meaningfully broadens the applicability of simultaneous share-based and comparison-based fairness guarantees beyond additive valuations, which is a standard strengthening in fair division. The work is credited for targeting a natural generalization and for asserting constructive or existence proofs that preserve constant-factor approximations.

major comments (1)

[Abstract] Abstract (final paragraph): the claim that additive-case techniques extend to submodular valuations while preserving constant ρ-MMS and EF1 is asserted without any derivation steps, lemmas, key equations, or verification; the provided text supplies no argument supporting that the extension preserves both guarantees simultaneously.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review. Below we respond to the single major comment.

read point-by-point responses

Referee: [Abstract] Abstract (final paragraph): the claim that additive-case techniques extend to submodular valuations while preserving constant ρ-MMS and EF1 is asserted without any derivation steps, lemmas, key equations, or verification; the provided text supplies no argument supporting that the extension preserves both guarantees simultaneously.

Authors: Abstracts in theoretical computer science papers are concise summaries of results and contributions; they are not intended to contain derivation steps, lemmas, or full proofs. The manuscript abstract correctly states the main theorem: simultaneous EF1/EFL and constant-ρ MMS allocations exist for submodular valuations, extending the additive case. The actual extension, including the adaptation of techniques and verification that both guarantees are preserved, is established rigorously in the body of the paper via the sequence of definitions, lemmas, and theorems that constitute the proof. We are happy to add a brief high-level pointer sentence to the abstract if the referee finds it helpful for readability. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is an existence proof extending prior additive-valuation results (cited as previously known) to submodular valuations while preserving constant-factor MMS and EF1. No equations, fitted parameters, self-definitional steps, or load-bearing self-citations appear in the abstract or description. The central claim does not reduce to its inputs by construction; it is a constructive extension with independent content. This matches the default expectation of no circularity (score 0-2).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, invented entities, or non-standard axioms beyond the domain definition of submodularity itself.

axioms (1)

domain assumption Valuations are monotone submodular
The paper works exclusively with this class as stated in the abstract.

pith-pipeline@v0.9.1-grok · 5675 in / 1165 out tokens · 31641 ms · 2026-06-27T23:01:10.460892+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

31 extracted references · 25 canonical work pages · 1 internal anchor

[1]

InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, David P

Breaking the 3/4 Barrier for Approximate Maximin Share. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, David P. Woodruff (Ed.). SIAM, 74–91.https: //doi.org/10.1137/1.9781611977912.4 Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki

work page doi:10.1137/1.9781611977912.4 2024
[2]

A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving

Simplification and Improvement of MMS Approximation. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China. ijcai.org, 2485–2493.https://doi.org/10.24963/IJCAI.2023/276 Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weiden- bach...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.24963/ijcai.2023/276 2023
[3]

Algorithms13, 4 (2017), 52:1–52:28.https://doi.org/10.1145/3147173 Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos

Approximation Algorithms for Computing Maximin Share Allocations.ACM Trans. Algorithms13, 4 (2017), 52:1–52:28.https://doi.org/10.1145/3147173 Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos

work page doi:10.1145/3147173 2017
[4]

Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor. Comput. Sci.841 (2020), 94–109.https://doi.org/10.1016/J.TCS.2020.07.006 Arash Ashuri and Vasilis Gkatzelis

work page doi:10.1016/j.tcs.2020.07.006 2020
[5]

InProceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.)

Simultaneously Satisfying MXS and EFL. InProceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.). ACM, 689–718.https: //doi.org/10.1145/3736252.3742613 Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, and Yadati Narahari

work page doi:10.1145/3736252.3742613 2025
[6]

Groupwise Maximin Fair Allocation of Indivisible Goods. InProceedings of the Thirty-Second AAAI Confer- ence on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelli- gence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018...

work page doi:10.1609/aaai.v32i1.11463 2018
[7]

Economics and Comput.8, 1 (2020), 5:1–5:28.https: //doi.org/10.1145/3381525 Siddharth Barman and Mashbat Suzuki

Approximation Algorithms for Max- imin Fair Division.ACM Trans. Economics and Comput.8, 1 (2020), 5:1–5:28.https: //doi.org/10.1145/3381525 Siddharth Barman and Mashbat Suzuki

work page doi:10.1145/3381525 2020
[8]

InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.)

Compatibility of Fairness and Nash Welfare under Subadditive Valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.). SIAM, 1724–1746.https://doi.org/10.1137/1.9781611978971.61 XiaolinBu, ZihaoLi, ShengxinLiu, JiaxinSong, andBia...

work page doi:10.1137/1.9781611978971.61 2026
[9]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy119, 6 (2011), 1061–1103. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang

2011
[10]

Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

work page doi:10.1145/3355902 2019
[11]

ACM71, 1 (2024), 4:1–4:27.https://doi.org/10.1145/3616009 25 George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa

EFX Exists for Three Agents.J. ACM71, 1 (2024), 4:1–4:27.https://doi.org/10.1145/3616009 25 George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa

work page doi:10.1145/3616009 2024
[12]

InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22,

Maximin Share Guarantees for Few Agents with Subadditive Valuations. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22,

2025
[13]

ijcai.org, 3788–3795.https://doi.org/10.24963/IJCAI.2025/ 421 Xiequan Fan, Ion Grama, and Quansheng Liu

work page doi:10.24963/ijcai.2025/ 2025
[14]

Exponential inequalities for martingales with applications.Electron. J. Probab.20 (2015), 1–22.https://doi.org/10.1214/EJP.v20-3496 Uriel Feige. 2025a. From multi-allocations to allocations, with subadditive valuations.CoRR abs/2506.21493 (2025).https://doi.org/10.48550/ARXIV.2506.21493arXiv:2506.21493 Uriel Feige. 2025b. The residual maximin share.CoRRab...

work page doi:10.1214/ejp.v20-3496 2015
[15]

doi:10.1145/3736252.3742519 , title =

Fair allocations with subadditive and XOS valuations. In Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.). ACM, 160–185.https://doi.org/10.1145/3736252.3742514 Uriel Feige and Alexey Norkin

work page doi:10.1145/3736252.3742514 2025
[16]

Improved maximin fair allocation of indivisible items to three agents.CoRRabs/2205.05363 (2022).https://doi.org/10.48550/ARXIV.2205.05363 arXiv:2205.05363 Uriel Feige, Ariel Sapir, and Laliv Tauber

work page doi:10.48550/arxiv.2205.05363 2022
[17]

A Tight Negative Example for MMS Fair Allo- cations. InWeb and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings (Lecture Notes in Computer Science), Michal Feld- man, Hu Fu, and Inbal Talgam-Cohen (Eds.). Springer, 355–372.https://doi.org/10.1007/ 978-3-030-94676-0_20 Duncan K. Foley

2021
[18]

Resource Allocation and the Public Sector.Yale Economic Essays7 (1967), 45–98. David A. Freedman

1967
[19]

Hoffmann-Jørgensen and G

On tail probabilities for martingales.Ann. Probab.3, 1 (1975), 100–118. https://doi.org/10.1214/aop/1176996452 Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami

work page doi:10.1214/aop/1176996452 1975
[20]

Selling to a

Fair Allocation of Indivisible Goods: Improvements and Generalizations. InProceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, Éva Tardos, Edith Elkind, and Rakesh Vohra (Eds.). ACM, 539–556. https://doi.org/10.1145/3219166.3219238 Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddig...

work page doi:10.1145/3219166.3219238 2018
[21]

Intell.303 (2022), 103633.https://doi.org/10.1016/J.ARTINT.2021.103633 Laurent Gourvès and Jérôme Monnot

Fair allocation of indivisible goods: Beyond additive valuations.Artif. Intell.303 (2022), 103633.https://doi.org/10.1016/J.ARTINT.2021.103633 Laurent Gourvès and Jérôme Monnot

work page doi:10.1016/j.artint.2021.103633 2022
[22]

On maximin share allocations in matroids.Theor. Comput. Sci.754 (2019), 50–64.https://doi.org/10.1016/J.TCS.2018.05.018 Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei

work page doi:10.1016/j.tcs.2018.05.018 2019
[23]

InProceedings of the 2026 Annual 26 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, Jan- uary 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.)

Im- proved Maximin Share Guarantee for Additive Valuations. InProceedings of the 2026 Annual 26 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, Jan- uary 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.). SIAM, 2239–2290.https: //doi.org/10.1137/1.9781611978971.81 Xin Huang and Shengwei Zhou

work page doi:10.1137/1.9781611978971.81 2026
[24]

Procaccia, and Junxing Wang

An FPTAS for 7/9-Approximation to Maximin Share Allocations.CoRRabs/2511.13056 (2025).https://doi.org/10.48550/ARXIV.2511.13056 arXiv:2511.13056 David Kurokawa, Ariel D. Procaccia, and Junxing Wang

work page doi:10.48550/arxiv.2511.13056 2025
[25]

ACM65, 2 (2018), 8:1–8:27.https://doi.org/10.1145/3140756 Benny Lehmann, Daniel Lehmann, and Noam Nisan

Fair Enough: Guaranteeing Approx- imate Maximin Shares.J. ACM65, 2 (2018), 8:1–8:27.https://doi.org/10.1145/3140756 Benny Lehmann, Daniel Lehmann, and Noam Nisan

work page doi:10.1145/3140756 2018
[26]

Activity-dependent structural plastic- ity

Combinatorial auctions with decreasing marginal utilities.Games Econ. Behav.55, 2 (2006), 270–296.https://doi.org/10.1016/J. GEB.2005.02.006 Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

work page doi:10.1016/j 2006
[27]

InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S

On approxi- mately fair allocations of indivisible goods. InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer (Eds.). ACM, 125–131.https://doi.org/10.1145/988772.988792 Simon Mackenzie and Mashbat Suzuki

work page doi:10.1145/988772.988792 2004
[28]

Benjamin Plaut and Tim Roughgarden

Counterexamples to EFX for Submodular and Sub- additive Valuations.CoRRabs/2605.06451 (2026). Benjamin Plaut and Tim Roughgarden

Pith/arXiv arXiv 2026
[29]

Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math.34, 2 (2020), 1039–1068.https://doi.org/10.1137/19M124397X Gilad Ben Uziahu and Uriel Feige

work page doi:10.1137/19m124397x 2020
[30]

On Fair Allocation of Indivisible Goods to Submod- ular Agents.CoRRabs/2303.12444 (2023).https://doi.org/10.48550/ARXIV.2303.12444 arXiv:2303.12444 Hal R. Varian

work page doi:10.48550/arxiv.2303.12444 2023
[31]

A Missing proofs from Section 3 A.1 ECE outputs an EF1 allocation Here we prove Proposition 3.4

Equity, Envy, and Efficiency.Journal of Economic Theory9, 1 (1974), 63–91. A Missing proofs from Section 3 A.1 ECE outputs an EF1 allocation Here we prove Proposition 3.4. Proof.Since a new itemeis always allocated to an agent that no other agent envies, ifˆAis EF1 just beforeeis allocated, then after allocatingeto such an agent the updated partial alloca...

1974

[1] [1]

InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, David P

Breaking the 3/4 Barrier for Approximate Maximin Share. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, David P. Woodruff (Ed.). SIAM, 74–91.https: //doi.org/10.1137/1.9781611977912.4 Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki

work page doi:10.1137/1.9781611977912.4 2024

[2] [2]

A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving

Simplification and Improvement of MMS Approximation. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China. ijcai.org, 2485–2493.https://doi.org/10.24963/IJCAI.2023/276 Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weiden- bach...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.24963/ijcai.2023/276 2023

[3] [3]

Algorithms13, 4 (2017), 52:1–52:28.https://doi.org/10.1145/3147173 Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos

Approximation Algorithms for Computing Maximin Share Allocations.ACM Trans. Algorithms13, 4 (2017), 52:1–52:28.https://doi.org/10.1145/3147173 Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos

work page doi:10.1145/3147173 2017

[4] [4]

Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination.Theor. Comput. Sci.841 (2020), 94–109.https://doi.org/10.1016/J.TCS.2020.07.006 Arash Ashuri and Vasilis Gkatzelis

work page doi:10.1016/j.tcs.2020.07.006 2020

[5] [5]

InProceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.)

Simultaneously Satisfying MXS and EFL. InProceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.). ACM, 689–718.https: //doi.org/10.1145/3736252.3742613 Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, and Yadati Narahari

work page doi:10.1145/3736252.3742613 2025

[6] [6]

Groupwise Maximin Fair Allocation of Indivisible Goods. InProceedings of the Thirty-Second AAAI Confer- ence on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelli- gence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018...

work page doi:10.1609/aaai.v32i1.11463 2018

[7] [7]

Economics and Comput.8, 1 (2020), 5:1–5:28.https: //doi.org/10.1145/3381525 Siddharth Barman and Mashbat Suzuki

Approximation Algorithms for Max- imin Fair Division.ACM Trans. Economics and Comput.8, 1 (2020), 5:1–5:28.https: //doi.org/10.1145/3381525 Siddharth Barman and Mashbat Suzuki

work page doi:10.1145/3381525 2020

[8] [8]

InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.)

Compatibility of Fairness and Nash Welfare under Subadditive Valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.). SIAM, 1724–1746.https://doi.org/10.1137/1.9781611978971.61 XiaolinBu, ZihaoLi, ShengxinLiu, JiaxinSong, andBia...

work page doi:10.1137/1.9781611978971.61 2026

[9] [9]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy119, 6 (2011), 1061–1103. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang

2011

[10] [10]

Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

The Unreasonable Fairness of Maximum Nash Welfare.ACM Trans. Economics and Comput.7, 3 (2019), 12:1–12:32.https://doi.org/10.1145/3355902 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

work page doi:10.1145/3355902 2019

[11] [11]

ACM71, 1 (2024), 4:1–4:27.https://doi.org/10.1145/3616009 25 George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa

EFX Exists for Three Agents.J. ACM71, 1 (2024), 4:1–4:27.https://doi.org/10.1145/3616009 25 George Christodoulou, Vasilis Christoforidis, Symeon Mastrakoulis, and Alkmini Sgouritsa

work page doi:10.1145/3616009 2024

[12] [12]

InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22,

Maximin Share Guarantees for Few Agents with Subadditive Valuations. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22,

2025

[13] [13]

ijcai.org, 3788–3795.https://doi.org/10.24963/IJCAI.2025/ 421 Xiequan Fan, Ion Grama, and Quansheng Liu

work page doi:10.24963/ijcai.2025/ 2025

[14] [14]

Exponential inequalities for martingales with applications.Electron. J. Probab.20 (2015), 1–22.https://doi.org/10.1214/EJP.v20-3496 Uriel Feige. 2025a. From multi-allocations to allocations, with subadditive valuations.CoRR abs/2506.21493 (2025).https://doi.org/10.48550/ARXIV.2506.21493arXiv:2506.21493 Uriel Feige. 2025b. The residual maximin share.CoRRab...

work page doi:10.1214/ejp.v20-3496 2015

[15] [15]

doi:10.1145/3736252.3742519 , title =

Fair allocations with subadditive and XOS valuations. In Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, Itai Ashlagi and Aaron Roth (Eds.). ACM, 160–185.https://doi.org/10.1145/3736252.3742514 Uriel Feige and Alexey Norkin

work page doi:10.1145/3736252.3742514 2025

[16] [16]

Improved maximin fair allocation of indivisible items to three agents.CoRRabs/2205.05363 (2022).https://doi.org/10.48550/ARXIV.2205.05363 arXiv:2205.05363 Uriel Feige, Ariel Sapir, and Laliv Tauber

work page doi:10.48550/arxiv.2205.05363 2022

[17] [17]

A Tight Negative Example for MMS Fair Allo- cations. InWeb and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings (Lecture Notes in Computer Science), Michal Feld- man, Hu Fu, and Inbal Talgam-Cohen (Eds.). Springer, 355–372.https://doi.org/10.1007/ 978-3-030-94676-0_20 Duncan K. Foley

2021

[18] [18]

Resource Allocation and the Public Sector.Yale Economic Essays7 (1967), 45–98. David A. Freedman

1967

[19] [19]

Hoffmann-Jørgensen and G

On tail probabilities for martingales.Ann. Probab.3, 1 (1975), 100–118. https://doi.org/10.1214/aop/1176996452 Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami

work page doi:10.1214/aop/1176996452 1975

[20] [20]

Selling to a

Fair Allocation of Indivisible Goods: Improvements and Generalizations. InProceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, Éva Tardos, Edith Elkind, and Rakesh Vohra (Eds.). ACM, 539–556. https://doi.org/10.1145/3219166.3219238 Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddig...

work page doi:10.1145/3219166.3219238 2018

[21] [21]

Intell.303 (2022), 103633.https://doi.org/10.1016/J.ARTINT.2021.103633 Laurent Gourvès and Jérôme Monnot

Fair allocation of indivisible goods: Beyond additive valuations.Artif. Intell.303 (2022), 103633.https://doi.org/10.1016/J.ARTINT.2021.103633 Laurent Gourvès and Jérôme Monnot

work page doi:10.1016/j.artint.2021.103633 2022

[22] [22]

On maximin share allocations in matroids.Theor. Comput. Sci.754 (2019), 50–64.https://doi.org/10.1016/J.TCS.2018.05.018 Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei

work page doi:10.1016/j.tcs.2018.05.018 2019

[23] [23]

InProceedings of the 2026 Annual 26 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, Jan- uary 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.)

Im- proved Maximin Share Guarantee for Additive Valuations. InProceedings of the 2026 Annual 26 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, Jan- uary 11-14, 2026, Kasper Green Larsen and Barna Saha (Eds.). SIAM, 2239–2290.https: //doi.org/10.1137/1.9781611978971.81 Xin Huang and Shengwei Zhou

work page doi:10.1137/1.9781611978971.81 2026

[24] [24]

Procaccia, and Junxing Wang

An FPTAS for 7/9-Approximation to Maximin Share Allocations.CoRRabs/2511.13056 (2025).https://doi.org/10.48550/ARXIV.2511.13056 arXiv:2511.13056 David Kurokawa, Ariel D. Procaccia, and Junxing Wang

work page doi:10.48550/arxiv.2511.13056 2025

[25] [25]

ACM65, 2 (2018), 8:1–8:27.https://doi.org/10.1145/3140756 Benny Lehmann, Daniel Lehmann, and Noam Nisan

Fair Enough: Guaranteeing Approx- imate Maximin Shares.J. ACM65, 2 (2018), 8:1–8:27.https://doi.org/10.1145/3140756 Benny Lehmann, Daniel Lehmann, and Noam Nisan

work page doi:10.1145/3140756 2018

[26] [26]

Activity-dependent structural plastic- ity

Combinatorial auctions with decreasing marginal utilities.Games Econ. Behav.55, 2 (2006), 270–296.https://doi.org/10.1016/J. GEB.2005.02.006 Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

work page doi:10.1016/j 2006

[27] [27]

InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S

On approxi- mately fair allocations of indivisible goods. InProceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004, Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer (Eds.). ACM, 125–131.https://doi.org/10.1145/988772.988792 Simon Mackenzie and Mashbat Suzuki

work page doi:10.1145/988772.988792 2004

[28] [28]

Benjamin Plaut and Tim Roughgarden

Counterexamples to EFX for Submodular and Sub- additive Valuations.CoRRabs/2605.06451 (2026). Benjamin Plaut and Tim Roughgarden

Pith/arXiv arXiv 2026

[29] [29]

Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math.34, 2 (2020), 1039–1068.https://doi.org/10.1137/19M124397X Gilad Ben Uziahu and Uriel Feige

work page doi:10.1137/19m124397x 2020

[30] [30]

On Fair Allocation of Indivisible Goods to Submod- ular Agents.CoRRabs/2303.12444 (2023).https://doi.org/10.48550/ARXIV.2303.12444 arXiv:2303.12444 Hal R. Varian

work page doi:10.48550/arxiv.2303.12444 2023

[31] [31]

A Missing proofs from Section 3 A.1 ECE outputs an EF1 allocation Here we prove Proposition 3.4

Equity, Envy, and Efficiency.Journal of Economic Theory9, 1 (1974), 63–91. A Missing proofs from Section 3 A.1 ECE outputs an EF1 allocation Here we prove Proposition 3.4. Proof.Since a new itemeis always allocated to an agent that no other agent envies, ifˆAis EF1 just beforeeis allocated, then after allocatingeto such an agent the updated partial alloca...

1974