Pith. sign in

REVIEW 1 major objections 4 minor 2 cited by

When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that with just two agents and eight goods, monotone submodular valuations can make fairness (EF1) and Pareto optimality mutually incompatible, and even approximate efficiency is impossible beyond a constant factor.

desk verdict Main counterexample is real and settles the EF1/PO question for submodular valuations; the positive common-envelope theorem has a pair of genuine proof gaps that need repair. read the letter →

arxiv 2607.17811 v1 pith:MC6BWKXK submitted 2026-07-20 cs.GT

Simon Mackenzie , Mashbat Suzuki This is my paper · ORCID
classification cs.GT MSC 91B3205B35
keywords fairdivisionEF1envy-freenessuptoonegoodParetooptimalitysubmodularvaluationssubadditiveweightedmatroidrankNashsocialwelfare
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

In fair division of indivisible goods, the benchmark fairness notion of envy-freeness up to one good (EF1) is always attainable, and for additive valuations it can always be combined with Pareto optimality (PO). This paper answers the long-standing open question of whether that compatibility survives when valuations are submodular, the discrete analogue of diminishing returns. It shows the answer is no: there is a two-agent instance with only eight goods and monotone submodular valuations in which every EF1 allocation is Pareto-dominated, so no allocation is both EF1 and PO. In fact, the obstruction is quantitative: for ε=1/6, every EF1 allocation can be improved for both agents by a factor of 24/23, meaning no EF1 allocation is even α-Pareto optimal for any α>23/24. The paper goes on to map the boundary of this impossibility, showing that a market/weighted-welfare route fails even for weighted matroid rank valuations while a common-envelope condition restores EF1+PO, and proving a tight 1/√2 threshold for two-agent subadditive instances.

What carries the argument

The driving object is a pair of type-symmetric valuation tables on 3 A-goods and 5 B-goods, with a small parameter ε. The tables are engineered so that the values rise quickly and flatten: any four goods are worth at least 3, and no bundle exceeds 3+6ε. The ε-terms are arranged with opposite symmetries in the two agents' tables, so the EF1 condition selects exactly the four balanced splits, while the same ε-terms make each balanced split strictly dominated by an unbalanced split. For the positive side, the central object is the common-envelope condition: a common monotone set function g and agent-specific downward-closed certificate families C_i, with v_i(S)=max{g(T): T⊆S, T∈C_i}; the proof selects a leximin-optimal disjoint certificate allocation and then assigns residual goods along acyclic envy graph edges, preserving EF1 and leximin optimality.

What would settle it

Set ε=1/6, reconstruct the two count valuations on the eight goods, and run two explicit checks: (a) compute all A- and B-marginal values and verify every entry is nonnegative with each row and column nonincreasing; (b) enumerate all 256 allocations and confirm the EF1 allocations are exactly the four balanced splits and that each is strictly Pareto-dominated by the displayed unbalanced split. Any violated inequality in (a) or any extra or missing EF1 split in (b) refutes the construction.

Watch

Extended reading notes

Core claim

The central discovery is that EF1 and Pareto optimality are not compatible for monotone submodular valuations, even with two agents and eight goods. Concretely, the paper constructs an instance with three A-goods and five B-goods, where both agents are indifferent among goods of the same type, so valuations reduce to two 4×6 tables parameterized by ε∈(0,1/6]. In any EF1 allocation, each agent must receive exactly four goods—the only four balanced splits are EF1—but each of those splits is strictly dominated by an unbalanced allocation, with both agents gaining by at least the factor (3+6ε)/(3+5ε). Setting ε=1/6 makes that factor 24/23, so for every α>23/24 no EF1 allocation is α-Pareto optimal. Because every submodular valuation is subadditive, the same construction strengthens the known subadditive incompatibility, ruling out EF1 with approximate efficiency instead of merely with exact weak-PO. The paper then proves that the obstruction is methodological: for common-weight matroid rank valuations, EF1 and fractional Pareto optimality are incompatible, so positive-welfare-weight and Fisher-market approaches cannot work in a black-box way, yet a common-envelope condition (certificates under a common monotone envelope) guarantees EF1+PO for any number of agents.

Load-bearing premise

The counterexample assumes the two 4×6 valuation tables in Section 3 are monotone submodular, a fact the paper verifies only by the finite marginal grids in Appendix A.4; if any of those grid entries is negative or increases along a row or column, the instance is not submodular and the theorem does not resolve the open question.

Editorial extensions

If this is right

  • For submodular valuations, the additive-result compatibility EF1+PO breaks down already with two agents, so any positive existence theorem must restrict a proper subclass of submodular or use a different fairness notion.
  • The same eight-good construction is a subadditive counterexample where no EF1 allocation is α-PO for α>23/24, which is stronger than the earlier subadditive incompatibility that still admitted weak-PO.
  • For two-agent subadditive instances, the threshold is exactly 1/√2: for every α>1/√2 there is an instance with no EF1 α-PO allocation, matching the known EF1+1/√2-PO guarantee; for n≥3 the same bound holds for every α>1/√2, and the paper conjectures the optimal n-agent threshold is 2^{-(1-1/n)}.
  • In common-weight matroid rank settings, EF1+fPO is impossible, so any algorithm that outputs a positive weighted-welfare maximizer (including Fisher market equilibria) cannot guarantee fairness in general, ruling out black-box transfer of the additive machinery.
  • Under the common-envelope condition, EF1+PO allocations exist lexicographically optimal for any number of agents, and this covers common-weight matroid rank valuations as well as shared-submodular-g valuations of the form v_i(S)=g(S∩E_i).

Reading between the lines

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

  • Because the domination and envy gaps in the eight-good instance are bounded away from zero by multiples of ε, the incompatibility is robust: sufficiently small perturbations of the two valuation tables should preserve the failure of EF1+α-PO for α>23/24, though the paper does not state this robustness for the submodular instance.
  • The same count-table mechanism—fairness enforces balance, balance is Pareto-dominated by imbalance—may translate to other fairness relaxations (e.g., EFX or maximin share) or to submodular instances with goods and chores, since only the type-symmetric structure is used.
  • The tight 1/√2 threshold for two-agent subadditive instances and its connection to Nash social welfare suggest that the worst-case EF1+α-PO frontier coincides with the EF1+NSW approximation frontier; testing this on random subadditive instances would be a quick computational check of the paper's conjectured n-agent threshold.
  • If the conjecture that all weighted matroid rank valuations admit EF1+PO is true, the common-envelope condition is not necessary for existence, and a counterexample inside weighted matroid rank would require a more expressive common scale than an additive envelope; the leximin-certificate algorithm is a natural starting point for searching such a counterexample.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. The paper addresses a central open problem in discrete fair division: whether an envy-free-up-to-one-good (EF1) allocation that is also Pareto optimal always exists for submodular valuations. It constructs a two-agent, eight-good instance with monotone submodular valuations, verifies by explicit tables that EF1 holds only at four balanced splits, and shows that each such split is strictly Pareto dominated, thereby establishing that EF1 and weak Pareto optimality are incompatible for submodular valuations. A quantitative version shows that, for this instance, no EF1 allocation is α-PO for any α > 23/24. The paper then proves that common-weight matroid-rank valuations can fail EF1 together with fractional Pareto optimality, which blocks weighted-welfare and Fisher-market approaches; introduces a common-envelope condition and claims an EF1+PO existence theorem under it, yielding a positive result for common-weight matroid-rank valuations; and gives subadditive constructions showing that the best universal approximate-PO threshold for two agents is at most 1/√2, matching a known lower bound, with extensions to larger numbers of agents.

Significance. If the proofs are completed, the paper settles a long-standing open question in a striking direction: the compatibility of EF1 and PO breaks down already for two agents with monotone submodular valuations. The core counterexample is concrete and self-contained, and the paper supplies explicit marginal grids, a complete EF1 case check, and a domination table; we independently rechecked these finite computations for the critical case ε = 1/6 and found them correct. The quantitative strengthening to α-PO for α > 23/24 is valuable because it rules out even approximate efficiency. The negative fPO results for common-weight matroid-rank valuations and for mixed manna clarify why standard market-based and weighted-welfare techniques cannot be extended in a black-box way. The common-envelope theorem, once its proof is repaired, would be a useful structural positive result. However, the proof of Theorem 4.4 as written has a genuine gap in its final leximin-optimality step, so the positive Theorem 1.2 is not yet formally supported; the gap is localized and appears to be readily repairable.

major comments (1)
  1. [Section 4.2, Theorem 4.4 proof, final paragraph] The argument that the completed allocation eA is leximin-optimal is incomplete. The proof takes an allocation B that lexicographically dominates eA, chooses one agent i with v_i(B_i) > v_i(P*_i), extracts a certificate T_i ⊆ B_i, and forms Q by replacing only P*_i with T_i while leaving all other P*_j unchanged. This Q need not be a certificate allocation, because T_i can intersect P*_j for j ≠ i; the sets P*_j are not assumed to lie inside B_j. The repair is to choose, for every agent k, a certificate T_k ⊆ B_k attaining v_k(B_k). Since B is a partition, the T_k are pairwise disjoint, and the resulting certificate allocation has utility vector exactly (v_k(B_k)), whose leximin order contradicts the leximin-optimality of P*. Until this repair is written into the proof, Theorem 1.2, via Corollary 4.5, is not formally established.
minor comments (4)
  1. [Section 3, Theorem 3.1 proof] The EF1 grid in the proof is stated as the outcome of the deletion tests, but the underlying inequality comparisons are not displayed. Because the grid is a finite computation, a short appendix table of the critical comparisons, or an explicit statement that the check is exhaustive over all (x, y), would improve verifiability; our independent check of the grid for ε = 1/6 found it correct.
  2. [Section 5, Theorems 5.1 and 5.2] The expressions such as '1√2' in the statements and surrounding prose appear to have a missing slash; they should read '1/√2'. This is a typesetting issue, but it occurs in a load-bearing threshold result and should be corrected.
  3. [Section 5, paragraph after Theorem 5.2] The claimed n-agent NSW approximation factor of 2^{-(1-1/n)} for the modified Complete Set Growing algorithm is stated with only a one-sentence justification. Since this claim motivates Conjecture 5.3 but is not used to prove a theorem, it should either be proved in the appendix or explicitly marked as a conjecture.
  4. [Section 4.2, Theorem 4.4 statement] The statement defines valuations vi(S) = max{g(T) : T ⊆ S, T ∈ Ci} and then assumes each vi is submodular. It would be helpful to state explicitly that monotonicity of g and downward closure of Ci imply each vi is monotone, and to give a brief discussion of when the submodularity assumption holds beyond the provided common-weight matroid-rank example.

Circularity Check

0 steps flagged · score 0.0 of 10

Central counterexample and positive theorems are self-contained; the only self-citations are independent prior results or context, not load-bearing assumptions.

full rationale

The paper's main negative result, Theorem 3.1, is a finite instance whose valuations are verified submodular by explicit marginal grids in Appendix A.4, with EF1 splits enumerated from the tables and every EF1 split strictly dominated by the displayed utility pairs; nothing is fitted to a subset of the data and no step assumes the target impossibility. The alpha > 23/24 strengthening is read off the same domination table, not imported from a fit. The positive common-envelope theorem, Theorem 4.4, is proved from a leximin-optimal certificate allocation, and Corollary 4.5 applies it to common-weight matroid-rank valuations; this derivation does not cite the conclusion as an input. The references to Barman and Suzuki [3] are used only for the independent lower-bound and approximation results (EF1 and 1/2-PO, and the 1/sqrt(2) Nash social welfare approximation) and to frame the tightness of Theorem 1.3; the cited paper is external peer-reviewed prior work with its own proof, not a quantity fitted inside this paper, so under the stated rules it is real evidence and does not raise the circularity score. The relabeling example cites the authors' own EFX counterexample [29] only as related work. One correctness caveat is notable but not circular: in the final paragraph of Theorem 4.4's proof, the certificate T_i extracted from B_i need not be disjoint from other P*_j, so the constructed Q might not be a valid certificate allocation; the gap is repairable by taking certificates for every agent from the dominating allocation B. The paper's derivation is therefore not circular.

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

The central counterexample is self-contained: it uses only explicit valuation tables and finite case checks, with ε as a free perturbation parameter. The broader results rely on standard theorems (Farkas' lemma, matroid properties) and on previously published bounds, including a self-cited SODA result for the tightness of the 1/√2 threshold. There are no invented entities.

free parameters (4)
  • ε (tie-breaking parameter) = 1/6 in Theorem 3.1; sufficiently small positive in Theorems 5.1/5.2
    Perturbation in the valuation tables that breaks ties between the ε-level terms; the main counterexample uses ε=1/6 to obtain the 23/24 approximate-efficiency factor.
  • η (outside-copy good value) = 0<η<1/(48(k-1))
    Small additive value that agents in Corollary 3.2 attach to goods outside their own copy, chosen small enough that a 1/6 improvement in the own copy dominates any outside-copy losses.
  • δ (threshold gap) = 0<4ε<δ<r-1/2
    Separates the low seed value t=1/2+δ from the high seed value r=1/√2 in the n-agent subadditive barrier, ensuring the claimed improvement factor exceeds 1/α.
  • T (number of auxiliary goods per auxiliary agent) = T≥max{3,m+1}
    Number of auxiliary goods added per auxiliary agent in Theorem 5.2 to create the tension between EF1 and efficiency.
assumptions (4)
  • standard math Farkas' lemma implies an allocation is fPO iff it maximizes some positive weighted welfare (Proposition 2.5)
    Used to characterize fPO allocations in Theorems 4.2 and 4.3.
  • standard math Weighted matroid rank valuations are gross substitutes and hence submodular (Schrijver, Paes Leme)
    Used to place the constructed common-weight matroid-rank instance in the submodular class and for Corollary 4.5.
  • domain assumption Every subadditive instance admits an EF1 allocation (Lipton et al.) and EF1 plus 1/2-PO (Barman and Suzuki)
    Prior results used to frame the approximation threshold range between 1/2 and 1.
  • domain assumption Barman and Suzuki's two-agent subadditive NSW bound of 1/√2 implies every two-agent subadditive instance admits an EF1 allocation that is 1/√2-PO
    Used to prove the tightness of Theorem 5.1's bound; this is a self-cited prior result from a published SODA paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations." pith.science (2026). https://pith.science/paper/MC6BWKXK

@misc{pith2026260717811,
  author       = {Pith},
  title        = {Pith review of: When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MC6BWKXK}},
  note         = {Machine review of arXiv:2607.17811}
}
abstract

One of the central questions in discrete fair division is whether fairness and efficiency can be achieved simultaneously. For indivisible goods, a canonical relaxation of envy-freeness is envy-freeness up to one good (EF1), while the standard efficiency benchmark is Pareto optimality (PO). In their seminal work, Caragiannis et al. showed that, for additive valuations, EF1 and PO are always compatible, and asked whether this compatibility extends to submodular valuations. This question has since become an important open problem in the study of fair division. In this paper, we settle the question in the negative. We construct an instance with two agents and eight goods, where both agents have submodular valuations, such that no EF1 allocation is even weakly Pareto optimal. Thus, the celebrated compatibility between EF1 and PO for additive valuations breaks down already for two agents under submodular valuations. We then map the boundary of this impossibility. On the negative side, we show that even for weighted matroid rank valuations, EF1 and fractional Pareto optimality (fPO) are incompatible. This rules out, in general, broad classes of weighted-welfare and Fisher-market-based approaches. On the positive side, we identify a common-envelope condition that restores compatibility. Under this condition, EF1+PO allocations exist for any number of agents. This yields new positive results showing that common-weight matroid-rank valuations always admit EF1+PO allocations. Finally, we quantify the efficiency loss that is unavoidable when insisting on EF1. Our submodular counterexample implies that there is a constant $\alpha<1$ such that no EF1 allocation is $\alpha$-\PO. For the broader class of subadditive valuations, we prove a tight two-agent bound: for any $\varepsilon>0$, there exists an instance in which no EF1 allocation is $\left(\frac{1}{\sqrt{2}}+\varepsilon\right)$-PO.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Best-of-Both-Worlds Fairness and Pareto Optimality

    cs.GT 2026-08 accept novelty 8.0 of 10

    A lottery over two-agent allocations can be simultaneously ex-ante envy-free, ex-post EFX, and ex-post Pareto optimal, but this becomes impossible for three agents with four goods.

  2. Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

    cs.GT 2026-07 accept novelty 7.0 of 10

    For two agents with strictly increasing valuations, EF1 and Pareto optimality are always compatible up to seven goods, and an eight-good submodular counterexample shows this is tight.

Reference graph

Works this paper leans on

43 extracted references · 22 canonical work pages · cited by 2 Pith papers

  1. [3]

    Compatibility of Fairness and Nash Welfare under Subadditive Valuations

    Siddharth Barman and Mashbat Suzuki. Compatibility of Fairness and Nash Welfare under Subadditive Valuations. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1724–1746. SIAM, 2026. doi: 10.1137/1.9781611978971.61. URL https://arxiv.org/abs/2407.12461

    arXiv 2026

  2. [1]

    Fair allocation of indivisible goods and chores.Autonomous Agents and Multi-Agent Systems, 36(1):3, 2022

    Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores.Autonomous Agents and Multi-Agent Systems, 36(1):3, 2022. doi: 10.1007/ s10458-021-09532-8

    work page 2022

  3. [2]

    Fair and truthful mechanisms for dichotomous valuations

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. InProceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, volume 35, pages 5119–5126, 2021. doi: 10.1609/aaai.v35i6.16647

    doi:10.1609/aaai.v35i6.16647 2021

  4. [4]

    Introspectively envy-free and efficient allocation of indivisible mixed manna, 2025

    Siddharth Barman and Paritosh Verma. Introspectively envy-free and efficient allocation of indivisible mixed manna, 2025. URLhttps://arxiv.org/abs/2509.18673. 13

    work page arXiv 2025

  5. [5]

    Finding fair and efficient allocations

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. InProceedings of the 2018 ACM Conference on Economics and Computation (EC), pages 557–574, 2018. doi: 10.1145/3219166.3219176

    arXiv 2018

  6. [6]

    Sundaram

    Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram. Tight ap- proximation algorithms for p-mean welfare under subadditive valuations. In28th Annual European Symposium on Algorithms (ESA 2020), volume 173 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page 2020

  7. [7]

    Optimal bounds on the price of fairness for indivisible goods

    Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds on the price of fairness for indivisible goods. InProceedings of the 16th International Conference on Web and Internet Economics (WINE), volume 12495 ofLecture Notes in Computer Science, pages 356–369. Springer,

    work page

  8. [8]

    The price of fairness for indivisible goods.Theory of Computing Systems, 65(7):1069–1093, 2021

    Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods.Theory of Computing Systems, 65(7):1069–1093, 2021. doi: 10.1007/ s00224-021-10039-8

    work page 2021

Show all 43 references
  1. [9]

    doi: 10.1007/978-3-030-64946-3_25

    doi

  2. [10]

    Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for in- divisible chores and mixed resources. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 ofLeibniz Inter- national Proc...

    2021 doi

  3. [11]

    Finding fair and effi- cient allocations for matroid rank valuations.ACM Transactions on Economics and Computation, 9(4):21:1–21:41, 2021

    Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding fair and effi- cient allocations for matroid rank valuations.ACM Transactions on Economics and Computation, 9(4):21:1–21:41, 2021. doi: 10.1145/3485006

    2021 doi

  4. [12]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare. InProceedings of the 2016 ACM Conference on Economics and Computation (EC), pages 305–322, 2016. doi: 10.1145/ 2940716.2940726

    2016

  5. [13]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

    Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011. doi: 10.1086/664613

    2011 doi

  6. [14]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum Nash welfare.ACM Transactions on Economics and Computation, 7(3):12:1–12:32, 2019. doi: 10.1145/3355902

    2019 doi

  7. [15]

    Envy-freeness up to any item with high Nash welfare: The virtue of donating items

    Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high Nash welfare: The virtue of donating items. InProceedings of the 2019 ACM Conference on Economics and Computation (EC), pages 527–545, 2019. doi: 10.1145/3328526.3329574

    2019

  8. [16]

    Are gross substi- tutes a substitute for submodular valuations?, 2021

    Shahar Dobzinski, Uriel Feige, Michal Feldman, and Renato Paes Leme. Are gross substi- tutes a substitute for submodular valuations?, 2021. URL https://arxiv.org/abs/2102. 13343. 14

    2021

  9. [17]

    Fair and efficient allocations under subadditive valuations

    Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and efficient allocations under subadditive valuations. InProceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 5269–5276, 2021. doi: 10.1609/aaai.v35i6.16665

    2021 doi

  10. [18]

    Computing fair and efficient allocations with few utility values.Theoretical Computer Science, 962:113932, 2023

    Jugal Garg and Aniket Murhekar. Computing fair and efficient allocations with few utility values.Theoretical Computer Science, 962:113932, 2023. doi: 10.1016/j.tcs.2023.113932

    2023

  11. [19]

    How to fairly allocate easy and dif- ficult chores

    Soroush Ebadian, Dominik Peters, and Nisarg Shah. How to fairly allocate easy and dif- ficult chores. InProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 372–380, 2022. URL https://www.ifaamas.org/ Proceedings/aamas2022...

    2022

  12. [20]

    Fair and efficient allocations of chores under bivalued preferences

    Jugal Garg, Aniket Murhekar, and John Qin. Fair and efficient allocations of chores under bivalued preferences. InProceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, volume 36, pages 5043–5050, 2022. doi: 10.1609/aaai.v36i5.20436

    2022 doi

  13. [21]

    EF1 for mixed manna with unequal entitlements, 2024

    Jugal Garg and Eklavya Sharma. EF1 for mixed manna with unequal entitlements, 2024. URL https://arxiv.org/abs/2410.12966

    2024 arXiv

  14. [22]

    Walrasian equilibrium with gross substitutes.Journal of Economic Theory, 87(1):95–124, 1999

    Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes.Journal of Economic Theory, 87(1):95–124, 1999. doi: 10.1006/jeth.1999.2531

    1999

  15. [23]

    Near fairness in matroids

    Laurent Gourvès, Jérôme Monnot, and Lydia Tlilane. Near fairness in matroids. InProceedings of the 21st European Conference on Artificial Intelligence, pages 393–398, 2014. doi: 10.3233/ 978-1-61499-419-0-393

    2014

  16. [24]

    Maximin share allocations for assign- ment valuations: Extended abstract

    Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. Maximin share allocations for assign- ment valuations: Extended abstract. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2875–2876, 2023. URL https://www.ifaamas.org/...

    2023

  17. [25]

    Kelso, Jr

    Alexander S. Kelso, Jr. and Vincent P . Crawford. Job matching, coalition formation, and gross substitutes.Econometrica, 50(6):1483–1504, 1982. doi: 10.2307/1913392

    1982 doi

  18. [26]

    Gross substitutability: An algorithmic survey.Games and Economic Behavior, 106:294–316, 2017

    Renato Paes Leme. Gross substitutability: An algorithmic survey.Games and Economic Behavior, 106:294–316, 2017. doi: 10.1016/j.geb.2017.10.016

    2017 doi

  19. [27]

    Combinatorial auctions with decreasing marginal utilities.Games and Economic Behavior, 55(2):270–296, 2006

    Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities.Games and Economic Behavior, 55(2):270–296, 2006. doi: 10.1016/j.geb.2005. 02.006

    2006 doi

  20. [28]

    Mixed fair division: A survey

    Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. Journal of Artificial Intelligence Research, 80:1373–1406, 2024. doi: 10.1613/jair.1.15800

    2024 doi

  21. [29]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004. doi: 10.1145/988772.988792

    2004

  22. [30]

    A polynomial-time algorithm for fair and efficient allocation with a fixed number of agents

    Ryoga Mahara. A polynomial-time algorithm for fair and efficient allocation with a fixed number of agents. In Vittorio Bilò, Yang Cai, and Zhiyi Huang, editors,Web and Inter- net Economics - 21st International Conference, WINE 2025, New Brunswick, NJ, USA, December 8-11, 2025,...

    2025 doi

  23. [31]

    Counterexamples to EFX for submodular and subad- ditive valuations, 2026

    Simon Mackenzie and Mashbat Suzuki. Counterexamples to EFX for submodular and subad- ditive valuations, 2026. URLhttps://arxiv.org/abs/2605.06451

    2026 arXiv

  24. [32]

    On fair and efficient allocations of indivisible goods

    Aniket Murhekar and Jugal Garg. On fair and efficient allocations of indivisible goods. InProceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, volume 35, pages 5595–5602, 2021. doi: 10.1609/aaai.v35i6.16703

    2021 doi

  25. [33]

    Existence of fair and efficient allocation of indivisible chores

    Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6742–6766. SIAM,

    2026

  26. [34]

    Springer, 2003

    Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency, volume 24 ofAlgo- rithms and Combinatorics. Springer, 2003

    2003

  27. [35]

    Fair allocation rules

    William Thomson. Fair allocation rules. In Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura, editors,Handbook of Social Choice and Welfare, volume 2, chapter 21, pages 393–506. Elsevier, 2011. doi: 10.1016/S0169-7218(10)00021-3

    2011 doi

  28. [36]

    Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, 2020. doi: 10.1137/19M124397X

    2020 doi

  29. [37]

    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. InProceedings of the 24th ACM Conference on Economics and Computation (EC), pages 1129–1152, 2023. doi: 10.1145/3580507.3597675

    2023

  30. [38]

    Yankee swap: A fast and simple fair allocation mechanism for matroid rank valuations

    Vignesh Viswanathan and Yair Zick. Yankee swap: A fast and simple fair allocation mechanism for matroid rank valuations. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 179–187, 2023. URL https://www.ifaamas. org/Pr...

    2023

  31. [39]

    Hal R. Varian. Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, 1974. doi: 10.1016/0022-0531(74)90075-1

    1974 doi

  32. [42]

    =g 1(2, 3) =1,v 2(Y′

  33. [43]

    Again, by the definition ofρ, 1> 1 α (r+2ε)≥ 1 α v1(X1), r> 1 α t≥ 1 α v2(X2), and 1> 1 α r≥ 1 α vk(Xk) (k≥3)

    =g 2(1, 2) =r,v k(Y′ k) =q T(T) =1(k≥3). Again, by the definition ofρ, 1> 1 α (r+2ε)≥ 1 α v1(X1), r> 1 α t≥ 1 α v2(X2), and 1> 1 α r≥ 1 α vk(Xk) (k≥3). SoY′ also improves every agent by a factor strictly larger than 1/α. Since every EF1 allocation X falls into one of the two c...

  34. [2020]

    doi: 10.4230/LIPIcs.ESA.2020.11

    2020 doi

  35. [2026]

    URLhttps://arxiv.org/abs/2507.09544

    doi: 10.1137/1.9781611978971.242. URLhttps://arxiv.org/abs/2507.09544

Pith tools

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