Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Exploring Relations among Fairness Notions in Discrete Fair Division

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper delivers a near-complete map of which of the 22 fairness notions in discrete fair division imply which, proved or refuted pair by pair across goods, chores, and mixed manna.

desk verdict A useful, systematic implication map for 22 fairness notions, but the near-complete picture is for the authors' redefined variants, not the standard definitions. read the letter →

arxiv 2502.02815 v3 pith:NSJXRVXX submitted 2025-02-05 cs.GT

Jugal Garg , Eklavya Sharma This is my paper · ORCID
classification cs.GT MSC 91B32
keywords fairdivisionindivisibleitemsfairnessnotionimplicationsEFXproportionalitymaximinshareanypriceinferenceengine
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

Fair division of indivisible items among agents has produced many competing fairness notions — envy-based relaxations such as EF1 and EFX (envy-free up to one, or up to any, item), proportionality relaxations such as PROP1 and PROPx, and share-based benchmarks such as the maximin share and the anyprice share — and it has been unclear how they relate. This paper tries to settle the relation problem: for 22 notions, it treats an implication as the claim that every allocation satisfying one notion also satisfies another, and then, for almost every ordered pair, either proves the implication or constructs an allocation that is fair under the first notion but not the second. The result is a near-complete hierarchy, summarized in implication diagrams for goods, chores, and mixed manna under additive valuations, with additional diagrams for submodular, subadditive, and general valuations. A reader should care because the map tells practitioners and theorists when a guarantee for a weaker notion automatically transfers to a stronger one and where the notions genuinely diverge; the paper also supplies an inference engine that derives many of the relations automatically and can be reused outside fair division.

What carries the argument

The load-bearing object is the implication relation itself: a notion $F_1$ implies $F_2$ when every $F_1$-fair allocation is also $F_2$-fair, so the whole contribution is a directed graph whose vertices are fairness notions and whose edges are proved implications, with counterexamples marking the missing edges. To get the graph at scale, the paper first proves a batch of implications and non-implications by hand, then feeds them to an inference engine that computes the transitive closure of implications and propagates counterexamples upward along implication chains, producing the final directed acyclic graphs. Two definitional moves carry much of the weight: the paper extends every notion — including EFX, PROPx, PROPm, and PROPavg — to the general mixed-manna, unequal-entitlements setting, and it adopts a slightly strengthened PROP1 with strict inequalities plus corrected versions of PROPm and PROPavg, so that the map's edges (for instance EFX implies PROPavg and PROPx implies PROPavg) are statements about these generalized definitions rather than about the originals.

What would settle it

Walk through all pairs of the 22 notions in the additive-goods, equal-entitlements setting and compare each with the goods diagram: any pair that is neither connected by a path in the diagram nor matched by a counterexample from the paper's tables — other than the single acknowledged open question of whether MXS implies EEF1 for more than two agents — refutes the near-completeness claim. A second check is to rebuild one engine-derived edge by hand: the non-implication EEFX $\not\Rightarrow$ PROPavg rests on Example 89, so verifying that instance really is APS-fair (hence EEFX-fair) and not PROPm-fair under the paper's own definitions tests whether the inference engine propagates soundly.

Watch

Extended reading notes

Core claim

The paper's central claim is that the fairness-notion landscape for discrete fair division is almost fully understood: with a few explicitly listed exceptions, every pair of the 22 notions it considers is either known to be related by an implication or known not to be, via a counterexample. For the main setting — additive valuations with equal entitlements — the implication graph for goods is closed except for one open edge (whether MXS implies EEF1 for more than two agents), the chore graph has no open edges, and the mixed-manna graph has none; the unequal-entitlements settings each carry at most three open pairs, and several binary-marginal settings are fully resolved. The same near-completeness is claimed for submodular goods (one open edge), subadditive goods (one open edge), and general goods (complete). The paper also attaches a feasibility label to each notion — feasible, infeasible, or open — and its diagrams show that for additive goods and chores with equal entitlements the only feasibilities in doubt are EFX and PMMS, two of the field's most studied open problems.

Load-bearing premise

The hierarchy is drawn for the paper's own generalized definitions of the fairness notions — EFX as in Definition 3, PROP1 with strict inequalities, and corrected PROPx, PROPm, and PROPavg — so a reader using the original definitions from the cited literature cannot take every edge of the map at face value; some edges were proved only for these variants, and at least one counterexample (Example 116) depends on the strict-inequality convention.

Editorial extensions

If this is right

  • A researcher proving an existence or algorithmic result for a weaker notion can immediately extend it to every stronger notion on the map, and a proven infeasibility for a strong notion rules out feasibility for everything above it.
  • For additive goods and chores with equal entitlements, the only fairness notions whose feasibility remains open are EFX and PMMS, so the map isolates where the field's hardest existence questions concentrate.
  • The strict-inequality definitions of PROP1, PROPx, PROPm, and PROPavg mean the map's edges involving proportional notions are statements about these strict variants; the paper notes that nearly all of its results hold for both strict and non-strict versions and flags where they do not, as in Example 116, which relies on strictness.
  • The inference engine needs only a few hand-proved base relations when a new notion is added — adding PROPavg required five results, and the engine inferred the rest — so the map can be extended incrementally as new fairness notions appear.
  • The engine itself is a general tool for conditional predicate implications: given a partially ordered family of settings, it outputs all implications and counterexamples that follow by transitive closure, a capability the paper demonstrates on fair division but describes as applicable more broadly.

Reading between the lines

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

  • My inference: because the map's edges are drawn for the paper's generalized definitions, exporting its conclusions to the standard definitions from the literature requires re-checking the affected lemmas; the paper flags where strictness matters, but the printed diagrams themselves are statements about its own variants.
  • My inference: the conditional-predicate machinery is not tied to fair division — any domain whose predicates, implications, and counterexamples can be conditioned on a partially ordered family of settings admits the same transitive-closure engine, a direction the paper suggests but does not develop.
  • My inference: the map makes a research-program prediction — since EFX and PMMS are the only open feasibility vertices for additive goods, an infeasibility proof for either would cascade downward into infeasibility for every notion above it in the diagram, giving a clean way to refute whole families at once.
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

3 major / 4 minor

Summary. The paper studies implications among 22 fairness notions in discrete fair division, across goods, chores, and mixed manna, with additive and several non-additive valuation classes. It manually proves a set of implications and counterexamples, then uses a custom inference engine to compute transitive closures and derive a near-complete implication DAG for many settings. The main deliverables are the implication diagrams in Fig. 1 and Appendix H, plus the web-based inference engine.

Significance. If correct, this would be a very useful reference map for fair-division researchers: the scale of the comparison (110 pairs per setting, many settings), the explicit counterexamples, and the reproducible inference engine are real strengths. Several proofs in Appendix C are self-contained, and the authors are careful to state feasibility/open-problem status for the notions. However, the hierarchy is built on deliberately modified definitions of PROP1, PROPx, PROPm, PROPavg, and EFX, and I found concrete chores counterexamples that fail as written. The core additive-goods part may be salvageable, but the chores and subadditive parts need correction and re-verification before the near-complete-picture claim can be accepted.

major comments (3)
  1. [Appendix D.3 (Examples 81 and 83; Table 3)] The chores versions of these counterexamples are invalid. In Example 81 with t=-1, v1(A1)=-4 while w1 v1([m])=-11/2, so A satisfies the first disjunct of PROP (Definition 4) and hence of PROPx (Definition 16); moreover A itself is EFX for agent 1 because agent 1 does not envy agent 2, so A is also MXS-fair to agent 1. Thus the row 'EF1 implies neither MXS nor PROPx' is not witnessed for chores. Similarly, in Example 83 with t=-1, v1(A1)=-5 >= -13/2, so A is PROPx, contradicting the claim that 'MXS does not imply PROPx' for negative bivalued marginals. Since Table 3 explicitly marks these rows as holding for both positive and negative bivalued marginals, the chores DAG (Fig. 1b) currently rests on unsupported non-implications. Please supply valid chores counterexamples or remove the negative-sign claims.
  2. [Appendix E.4 (Example 116; Table 3)] This counterexample is false as written. With v(S)=ceil(|S|/4) and A=(2,5), we have v1(A1)=ceil(2/4)=1 and v1([7])/2=ceil(7/4)/2=1, so agent 1 is PROP-fair and therefore PROP1-fair by the first disjunct of Definition 5, even under the strict version. The note that the strict inequality is 'crucial' is therefore incorrect. Consequently the claimed non-implication GAPS+EF1 does not imply PROP1 for subadditive valuations is unproved, and any DAG edge derived from this counterexample in Fig. 13 needs re-examination.
  3. [Appendix B.4 and B.6 (Definitions 5, 16, 17; Fig. 1)] The relation map is stated for modified versions of several literature notions, and this limits transfer to the notions a reader may expect. PROP1 uses strict inequalities (Definition 5), PROPx/PROPm/PROPavg are altered for mixed manna, and PROPavg in Definition 17 averages over |T| instead of n-1 specifically to force PROPx implies PROPavg. The paper itself explains in Appendix B.6.2 that the original PROPavg of [44] does not satisfy that implication. Hence Fig. 1's edges involving PROPavg and PROP1 are not claims about the original published notions in general. The abstract and Section 1.1 should state this caveat prominently, or the paper should include a dictionary of which edges survive for the standard definitions; otherwise the 'near-complete picture' can be misread as applying to the literature's notions.
minor comments (4)
  1. [Table 3 and footnotes] The shorthand 'bival *' and the asterisk explanations are hard to parse; please expand the affected settings explicitly in each row or provide a clearer legend.
  2. [Lemma 82 proof] In the t=-1 case, the sentence 'agent 1 doesn't have an M1S-certificate for A' appears to concern agent 2; as written it is confusing and should be rephrased.
  3. [Example 116] The example should either be corrected to a genuine non-implication or deleted; the current text is internally inconsistent with Definition 5, and the claimed role of strict inequalities needs to be re-established.
  4. [Appendix H / inference inputs] After fixing the counterexamples above, the inference engine inputs and all affected DAGs (especially Fig. 1b and Fig. 13) should be regenerated, since the engine propagates any incorrect non-implication through transitive closure.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the implication hierarchy is built from explicit proofs and counterexamples; the main caveats are transparent definitional variants and a few non-load-bearing self-citations.

full rationale

The paper's derivation chain is not circular. Section 4.1 lists manually proved implications and counterexamples with proofs in Appendices C-E; Section 4.2 and Section 5 feed these into an inference engine that only computes transitive closure and conditional counterexample propagation, so the DAGs in Fig. 1 and Appendix H are logical consequences of the manually established base facts rather than fitted outputs. The modified definitions (strict PROP1 in Definition 5, subset-based EFX in Definition 3, and repaired PROPx/PROPm/PROPavg in Definitions 16-17) are disclosed explicitly; in particular, Appendix B.6.2 states that PROPavg is changed from [44]'s sum(T)/(n-1) to sum(T)/|T| precisely so that PROPx implies PROPavg. This is a transparent definitional design choice, not a hidden equivalence, and the paper notes where the strict PROP1 variant is 'crucial' (Example 116). The only self-citation load is small: Lemma 33 is quoted from the authors' own [28] and Example 83 from [27], but these are individual edges, not the central organizing claim, and the paper reproves other previously known results it relies on (e.g., Lemma 42 gives a full proof of MMS implies EEFX). Thus no prediction reduces by construction and no load-bearing argument reduces to an unverified self-citation; the main limitation is that the near-complete picture applies to the paper's explicitly stated variants, which is a scope caveat rather than circularity.

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

The paper introduces no fitted parameters and no new postulated entities. Its central claim rests on the adopted definitions of fairness notions and on standard mathematical facts. The main modeling choice is how EFX and proportionality relaxations are generalized to mixed manna and non-additive valuations; the paper openly discusses these choices in Appendix B.

assumptions (5)
  • ad hoc to paper Definition 3 (generalized EFX) is adopted as the definition of EFX for non-additive and mixed-manna settings.
    Implications such as Lemma 21 and Lemma 38 are proved for this definition; equivalence to original EFX holds only under submodularity or strict positive/negative marginals (Lemmas 4 to 9).
  • ad hoc to paper Definitions 5, 16, and 17 (PROP1, PROPx, PROPm, PROPavg) use strict inequalities and modified conditions.
    The paper changes PROPavg's averaging set from n-1 to |T| and uses strict greater-than, which makes PROPx imply PROPavg; the original definitions have counterexamples (Appendix B.6).
  • domain assumption Valuation functions are normalized set functions with vi(empty) = 0, and instances are tuples (N, M, V, w) as defined in Section 2.
    This is the standard fair division model used throughout the paper; all results are conditioned on this model.
  • standard math Linear programming strong duality holds for the APS primal-dual equivalence.
    Used in Lemma 12 to prove that Definitions 14 and 15 of APS are equivalent.
  • standard math Submodular functions have the property that positive marginal value of a set implies a positive marginal item (Lemmas 6 and 8).
    These lemmas justify reducing subset-based EFX and PROPx definitions to single-item checks in submodular settings.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exploring Relations among Fairness Notions in Discrete Fair Division." pith.science (2026). https://pith.science/paper/NSJXRVXX

@misc{pith2026250202815,
  author       = {Pith},
  title        = {Pith review of: Exploring Relations among Fairness Notions in Discrete Fair Division},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NSJXRVXX}},
  note         = {Machine review of arXiv:2502.02815}
}
abstract

Fair allocation of indivisible items among agents is a fundamental and extensively studied problem. However, fairness does not have a single universally accepted definition, leading to many competing fairness notions. Some of these notions are considered stronger or more desirable, but they are also more difficult to guarantee. In this work, we examine 22 different fairness notions and organize them into a hierarchy. Formally, we say that a notion $F_1$ implies another notion $F_2$ if every $F_1$-fair allocation is also $F_2$-fair. We give a near-complete picture of implications among fairness notions: for almost every pair of notions, we either prove an implication or give a counterexample demonstrating that the implication does not hold. Although some of these results are already known, many are new. We examine multiple settings, including the allocation of goods, chores, and mixed manna, and different valuation classes like additive, submodular, and subadditive. We believe this work clarifies the relative strengths and applicability of these notions, providing a foundation for future research in fair division. Moreover, we develop an inference engine to automate part of our work. It is available as a user-friendly web application and may have broader applications beyond fair division.

Figures

Figures reproduced from arXiv: 2502.02815 by the authors.

Figure 1
Figure 1. Implications between fairness notions for additive valuations over goods and over chores [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Screenshot from the inference engine’s web interface for fair division. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Valuation function type and marginal values represented as digraphs where there is a [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: Additive valuations, mixed manna. EF = GPROP = PPROP PROP = EEF = MEFS EF1 = EFX = GAPS = GMMS = PAPS = PMMS APS = MMS = PROP1 = PROPx = PROPm = PROPavg = EEF1 = EEFX = MXS = M1S [PITH_FULL_IMAGE:figures/full_fig_p068_4.png]
Figure 5
Figure 5. Figure 5: Additive valuations, marginals in {−1, 0, 1}. We get the same DAG when marginals are in {0, −1} or {0, 1}. 68 [PITH_FULL_IMAGE:figures/full_fig_p068_5.png]
Figure 6
Figure 6. Figure 6: Additive valuations, goods, unequal entitlements. [PITH_FULL_IMAGE:figures/full_fig_p069_6.png]
Figure 7
Figure 7. Figure 7: Additive valuations, goods, two agents, unequal entitlements. [PITH_FULL_IMAGE:figures/full_fig_p069_7.png]
Figure 8
Figure 8. Figure 8: Additive valuations, chores, unequal entitlements. [PITH_FULL_IMAGE:figures/full_fig_p070_8.png]
Figure 9
Figure 9. Figure 9: Additive valuations, two agents. We get the same DAG for goods, chores, and mixed [PITH_FULL_IMAGE:figures/full_fig_p070_9.png]
Figure 10
Figure 10. Figure 10: Submodular valuations, goods [PITH_FULL_IMAGE:figures/full_fig_p071_10.png]
Figure 11
Figure 11. Figure 11: Submodular valuations, goods, two agents. [PITH_FULL_IMAGE:figures/full_fig_p072_11.png]
Figure 12
Figure 12. Figure 12: Submodular valuations with binary marginals (a.k.a. matroid rank valuations), goods. [PITH_FULL_IMAGE:figures/full_fig_p072_12.png]
Figure 13
Figure 13. Figure 13: Subadditive valuations, goods. 73 [PITH_FULL_IMAGE:figures/full_fig_p073_13.png]
Figure 14
Figure 14. Figure 14: General (monotonic) valuations, goods. GPROP PPROP PROP GAPS APS GMMS PAPS MMS PMMS EFX PROPx PROPavg PROPm PROP1 EF EEF MEFS EEFX MXS EF1 EEF1 M1S [PITH_FULL_IMAGE:figures/full_fig_p074_14.png]
Figure 15
Figure 15. Figure 15: General valuations with positive marginals. This setting is almost the same as Fig. [PITH_FULL_IMAGE:figures/full_fig_p074_15.png]

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. A Polynomial-Time Rule Satisfying Full Justified Representation

    cs.GT 2026-08 conditional novelty 7.0 of 10

    FJR-GJCR is a polynomial-time approval-based multiwinner rule satisfying Full Justified Representation, and MES committees are shown to be not always extendable to satisfy FJR.

  2. Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

    cs.GT 2025-07 reject novelty 7.0 of 10

    The paper proves a three-agent EFX/PMMS separation and claims PMMS existence for binary-valued and pair-demand valuations, plus EFX for personalized bivalued valuations.

Reference graph

Works this paper leans on

161 extracted references · 65 canonical work pages · cited by 2 Pith papers

  1. [7]

    Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination

    Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, 841:94–109, 2020. doi:10.1016/j.tcs.2020.07.006

    doi:10.1016/j.tcs.2020.07.006 2020

  2. [44]

    Proportional allocation of indivisible goods up to the least valued good on average

    Yusuke Kobayashi and Ryoga Mahara. Proportional allocation of indivisible goods up to the least valued good on average. SIAM Journal on Discrete Mathematics , 39(1):533–549, 2025. doi:10.1137/24M1631407

    work page doi:10.1137/24m1631407 2025

  3. [1]

    Breaking the 3 /4 barrier for approximate maximin share

    Hannaneh Akrami and Jugal Garg. Breaking the 3 /4 barrier for approximate maximin share. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 74–91, 2024. doi:10.113 7/1.9781611977912.4

    2024

  4. [2]

    Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations

    Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami. Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations. Advances in Neural Information Processing Systems , 36:58821–58832, 2023

    2023

  5. [3]

    Epistemic EFX allocations exist for monotone valuations

    Hannaneh Akrami and Nidhi Rathi. Epistemic EFX allocations exist for monotone valuations. In AAAI Conference on Artificial Intelligence , volume 39, pages 13520–13528, 2025. doi: 10.1609/aaai.v39i13.33476

    work page doi:10.1609/aaai.v39i13.33476 2025

  6. [4]

    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, 322:103965, 2023. doi:10.1016/j.artint.2023. 103965

    work page doi:10.1016/j.artint.2023 2023

  7. [5]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. Maximum Nash welfare and other stories about EFX. Theoret- ical Computer Science , 863:69–85, 2021. doi:10.1016/j.tcs.2021.02.020

    doi:10.1016/j.tcs.2021.02.020 2021

  8. [6]

    Comparing approximate relaxations of envy-freeness

    Georgios Amanatidis, Georgios Birmpas, and Vangelis Markakis. Comparing approximate relaxations of envy-freeness. In International Joint Conference on Artificial Intelligence , pages 42–48, 2018. doi:10.24963/ijcai.2018/6

    work page doi:10.24963/ijcai.2018/6 2018

Show all 161 references
  1. [8]

    Computing approximately proportional allocations of indivisible goods: Beyond additive and monotone valuations, 2025

    Martin Jupakkal Andersen, Ioannis Caragiannis, Anders Bo Ipsen, and Alexander Søltoft. Computing approximately proportional allocations of indivisible goods: Beyond additive and monotone valuations, 2025. arXiv:2508.12453

    2025 arXiv

  2. [9]

    Knowl- edge, fairness, and social constraints

    Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and J´ erˆ ome Lang. Knowl- edge, fairness, and social constraints. In AAAI Conference on Artificial Intelligence , 2018. doi:10.1609/aaai.v32i1.11590

    2018 doi

  3. [10]

    Fair allocation of indivisible goods and chores

    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, 2021. doi:10.100 7/s10458-021-09532-8

    2021

  4. [11]

    A polynomial-time algorithm for com- puting a Pareto optimal and almost proportional allocation

    Haris Aziz, Herv´ e Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for com- puting a Pareto optimal and almost proportional allocation. Operations Research Letters , 48(5):573–578, 2020. doi:10.1016/j.orl.2020.07.005

    2020 doi

  5. [12]

    Fair and truthful mechanisms for dichotomous valuations

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. AAAI Conference on Artificial Intelligence , 35(6):5119–5126, 2021. doi:10.160 9/aaai.v35i6.16647

    2021

  6. [13]

    Fair-share allocations for agents with arbitrary entitlements

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair-share allocations for agents with arbitrary entitlements. Mathematics of Operations Research, 2023. doi:10.1287/moor.2021.0199. 14

    2023

  7. [14]

    Achieving pro- portionality up to the maximin item with indivisible goods

    Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin. Achieving pro- portionality up to the maximin item with indivisible goods. AAAI Conference on Artificial Intelligence, 35(6):5143–5150, 2021. doi:10.1609/aaai.v35i6.16650

    2021 doi

  8. [15]

    PROPm alloca- tions of indivisible goods to multiple agents

    Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, and Daniel Schoepflin. PROPm alloca- tions of indivisible goods to multiple agents. In Interntional Joint Conference on Artificial Intelligence (IJCAI) , volume 1, pages 24–30, 2021. doi:10.24963/ijcai.2021/4

    2021 doi

  9. [16]

    Groupwise maximin fair allocation of indivisible goods

    Siddharth Barman, Arpita Biswas, Sanath Krishnamurthy, and Yadati Narahari. Groupwise maximin fair allocation of indivisible goods. In AAAI Conference on Artificial Intelligence ,

  10. [17]

    Finding fair and efficient allocations

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Economics and Computation , pages 557–574, 2018. doi:10.1145/3219166.32 19176

    2018 doi

  11. [18]

    Narayan, and Paritosh Verma

    Siddharth Barman, Vishnu V. Narayan, and Paritosh Verma. Fair chore division under binary supermodular costs, 2023. doi:10.48550/arXiv.2302.11530

    2023 doi arXiv

  12. [19]

    Existence and computation of maximin fair alloca- tions under matroid-rank valuations

    Siddharth Barman and Paritosh Verma. Existence and computation of maximin fair alloca- tions under matroid-rank valuations. In International Conference on Autonomous Agents and MultiAgent Systems, pages 169–177, 2021

    2021

  13. [20]

    Almost full EFX exists for four agents

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In AAAI Conference on Artificial Intelligence , volume 36(5), pages 4826–4833, 2022

    2022

  14. [21]

    Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indivis- ible chores and mixed resources. In APPROX 2021, 2021. doi:10.4230/LIPIcs.APPROX/RA NDOM.2021.1

    2021 doi

  15. [22]

    Fair division under cardinality constraints

    Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In In- ternational Joint Conference on Artificial Intelligence (IJCAI) , pages 91–97, 2018. doi: 10.24963/ijcai.2018/13

    2018 doi

  16. [23]

    Fair division of a graph

    Sylvain Bouveret, Katar ´ ına Cechl´ arov´ a, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In International Joint Conference on Artificial Intelligence , pages 135–141, 2017. doi:10.24963/ijcai.2017/20

    2017 doi

  17. [24]

    Characterizing conflicts in fair division of indivisible goods using a scale of criteria

    Sylvain Bouveret and Michel Lema ˆ ıtre. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems (AAMAS) , 30(2):259–290, 2016. doi:10.1007/s10458-015-9287-3

    2016 doi

  18. [25]

    Brams and A.D

    S.J. Brams and A.D. Taylor. Fair Division: From Cake-cutting to Dispute Resolution . Cam- bridge University Press, 1996

    1996

  19. [26]

    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(6):1061–1103, 2011. doi:10.1086/66 4613

    2011 doi

  20. [27]

    New fairness concepts for allocating indivisible items, 2022

    Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio. New fairness concepts for allocating indivisible items, 2022. URL: https://arxiv.org/abs/2206 .01710, arXiv:2206.01710. 15

    2022 arXiv

  21. [28]

    New fairness concepts for allocating indivisible items

    Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio. New fairness concepts for allocating indivisible items. InInternational Joint Conference on Artificial Intelligence (IJCAI) , volume 3, pages 2554–2562, 2023. doi:10.24963/ijcai.2023/284

    2023 doi

  22. [29]

    Procaccia, Nisarg Shah, and Junxing Wang

    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(3):12:1–12:32, 2019. doi:10.1145/3355902

    2019 doi

  23. [30]

    Weighted envy- freeness in indivisible item allocation

    Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. Weighted envy- freeness in indivisible item allocation. ACM Transactions on Economics and Computation , 9(3):18:1–18:39, 2021. doi:10.1145/3457166

    2021 doi

  24. [31]

    Weighted fairness notions for indivisible items revisited

    Mithun Chakraborty, Erel Segal-Halevi, and Warut Suksompong. Weighted fairness notions for indivisible items revisited. ACM Trans. Econ. Comput., 12(3):9:1–9:45, 2024. doi:10.114 5/3665799

    2024

  25. [32]

    EFX exists for three agents.Journal of the ACM , 71(1):4:1–4:27, 2024

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents.Journal of the ACM , 71(1):4:1–4:27, 2024. doi:10.1145/3616009

    2024 doi

  26. [33]

    A little charity guarantees almost envy-freeness

    Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM Journal on Computing , 50(4):1336–1358, 2021. doi:10.1137/20M1359134

    2021 doi

  27. [34]

    Fair public decision making

    Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In ACM Conference on Economics and Computation , pages 629–646, 2017. doi:10.1145/3033274.30 85125

    2017 doi

  28. [35]

    Fair interval scheduling of indivisible chores, 2024

    Sarfaraz Equbal, Rohit Gurjar, Yatharth Kumar, Swaprava Nath, and Rohit Vaish. Fair interval scheduling of indivisible chores, 2024. doi:10.48550/arXiv.2402.04353

    2024 doi arXiv

  29. [36]

    Fair allocation of indivisible goods to asymmetric agents

    Alireza Farhadi, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods to asymmetric agents. Journal of Artificial Intelligence Research , 64:1–20, 2019. doi: 10.1613/...

    2019 doi

  30. [37]

    On maximizing welfare when utility functions are subadditive

    Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 39(1):122–142, 2009. doi:10.1137/070680977

    2009 doi

  31. [38]

    Maximin fair allocations with two item values, 2022

    Uriel Feige. Maximin fair allocations with two item values, 2022. URL: https://www.wisdom .weizmann.ac.il/~feige/mypapers/MMSab.pdf

    2022

  32. [39]

    Low communication protocols for fair allocation of indivisible goods

    Uriel Feige. Low communication protocols for fair allocation of indivisible goods. In ACM Conference on Economics and Computation , pages 358–382. Association for Computing Ma- chinery, 2025. doi:10.1145/3736252.3742553

    2025

  33. [40]

    A tight negative example for MMS fair allocations

    Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In Web and Internet Economics (WINE) , pages 355–372. Springer, 2021. doi:10.1007/978-3 -030-94676-0_20

    2021 doi

  34. [41]

    EF1 for mixed manna with unequal entitlements, 2024

    Jugal Garg and Eklavya Sharma. EF1 for mixed manna with unequal entitlements, 2024. arXiv:2410.12966v1. 16

    2024 arXiv

  35. [42]

    Fair allocation of indivisible goods: Improvements and generalizations

    Mohammad Ghodsi, Mohammadtaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In ACM Conference on Economics and Computation (EC) , pages 539–556. Association for Computing Machinery, 2018. ...

    2018

  36. [43]

    Near fairness in matroids

    Laurent Gourv` es, J´ erˆ ome Monnot, and Lydia Tlilane. Near fairness in matroids. In ECAI 2014, pages 393–398, 2014. doi:10.3233/978-1-61499-419-0-393

    2014 doi

  37. [45]

    Approximating APS under submodular and XOS valuations with binary marginals

    Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. Approximating APS under submodular and XOS valuations with binary marginals. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages 1057–1065, 2024. URL: https://ifaamas.csc.li v.ac.uk/Proceedings...

    2024

  38. [46]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approx- imate maximin shares. Journal of the ACM , 65(2):1–27, 2018. doi:10.1145/3140756

    2018 doi

  39. [47]

    Almost (weighted) proportional allocations for indivisible chores

    Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In ACM Web Conference (WWW) , pages 122–131, 2022. doi:10.1145/3485447.35 12057

    2022 doi

  40. [48]

    R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In ACM conference on Electronic Commerce , pages 125–131, 2004. doi: 10.1145/988772.988792

    2004

  41. [49]

    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

  42. [50]

    (almost) envy-free, proportional and efficient allocations of an indivisible mixed manna

    Vasilis Livanos, Ruta Mehta, and Aniket Murhekar. (almost) envy-free, proportional and efficient allocations of an indivisible mixed manna. InInternational Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages 1678–1680, 2022. URL: https://www.ifaa mas.org/Pro...

    2022

  43. [51]

    Existence of fair and efficient allocation of indivisible chores, 2025

    Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores, 2025. arXiv: 2507.09544

    2025

  44. [52]

    Bidding and allocation in combinatorial auctions

    Noam Nisan. Bidding and allocation in combinatorial auctions. In ACM conference on Elec- tronic Commerce, pages 1–12. Association for Computing Machinery, 2000. doi:10.1145/35 2871.352872

  45. [53]

    Almost envy-freeness with general valuations

    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

  46. [54]

    cpigjs: Conditional predicate implication graph in JavaScript, and its appli- cation to fair division, 2024

    Eklavya Sharma. cpigjs: Conditional predicate implication graph in JavaScript, and its appli- cation to fair division, 2024. Web app: https://sharmaeklavya2.github.io/cpigjs/fair Div/, source code: https://github.com/sharmaeklavya2/cpigjs/

    2024

  47. [55]

    Almost envy-free allocations of indivisible goods or chores with entitlements

    Max Springer, MohammadTaghi Hajiaghayi, and Hadi Yami. Almost envy-free allocations of indivisible goods or chores with entitlements. AAAI Conference on Artificial Intelligence , 38(9):9901–9908, 2024. doi:10.1609/aaai.v38i9.28851. 17

    2024 doi

  48. [56]

    Steinhaus

    H. Steinhaus. Sur la division pragmatique. Econometrica, 17:315–319, 1949. doi:10.2307/19 07319

    1949 doi

  49. [57]

    How to cut a cake fairly

    Walter Stromquist. How to cut a cake fairly. The American Mathematical Monthly, 87(8):640– 644, 1980. doi:10.1080/00029890.1980.11995109

    1980

  50. [58]

    Equity, envy, and efficiency

    Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory , 9(1):63–91, 1974. doi:10.1016/0022-0531(74)90075-1. 18 A Details on Fair Division Settings A.1 Valuation Function Type A function u : 2M → R is

    1974 doi

  51. [60]

    Equivalently, for every set S ⊆ M , we have u(S) = P j∈S u({j})

    additive if for any two disjoint sets S, T⊆ M , we have u(S ∪ T ) = u(S) +u(T ). Equivalently, for every set S ⊆ M , we have u(S) = P j∈S u({j})

  52. [61]

    subadditive if for any two disjoint sets S, T⊆ M , we have u(S ∪ T ) ≤ u(S) + u(T )

  53. [62]

    superadditive if for any two disjoint sets S, T⊆ M , we have u(S ∪ T ) ≥ u(S) + u(T )

  54. [63]

    submodular if for any S, T⊆ M , we have u(S ∪ T ) + u(S ∩ T ) ≤ u(S) + u(T )

  55. [64]

    supermodular if for any S, T⊆ M , we have u(S ∪ T ) + u(S ∩ T ) ≥ u(S) + u(T )

  56. [65]

    cancelable [20] if for any T ⊆ M and S1, S2 ⊆ M \ T , we have u(S1 ∪ T ) > u(S2 ∪ T ) = ⇒ u(S1) > u(S2)

  57. [66]

    unit-demand if u(∅) = 0, and for any ∅ ̸= S ⊆ M , we have u(S) ≥ 0 and u(S) := maxj∈S u({j})

  58. [67]

    , ak, such that u(S) = maxk j=1 aj(S) for all S ⊆ M

    XOS (aka fractionally subadditive ) [52, 37] if there exist additive functions a1, . . ., ak, such that u(S) = maxk j=1 aj(S) for all S ⊆ M . Note that when |M | = 1, u belongs to all of these classes simultaneously. See Fig. 3a for relations between valuation function types. ...

  59. [68]

    goods: vi(j | S) ≥ 0 for all S ⊆ M , j ∈ M \ S, and i ∈ N

  60. [69]

    chores: vi(j | S) ≤ 0 for all S ⊆ M , j ∈ M \ S, and i ∈ N

  61. [70]

    positive: vi(j | S) > 0 for all S ⊆ M , j ∈ M \ S, and i ∈ N

  62. [71]

    negative: vi(j | S) < 0 for all S ⊆ M , j ∈ M \ S, and i ∈ N

  63. [72]

    bivalued: There exist constants a, b∈ R such that vi(j | S) ∈ {a, b} for all S ⊆ M , j ∈ M \ S, and i ∈ N

  64. [73]

    binary: vi(j | S) ∈ {0, 1} for all S ⊆ M , j ∈ M \ S, and i ∈ N

  65. [74]

    negative binary : vi(j | S) ∈ {0, −1} for all S ⊆ M , j ∈ M \ S, and i ∈ N . We can break up the class of bivalued instances into positive bivalued, negative bivalued, binary, negative binary, and mixed bivalued (mixed means that exactly one of a and b is positive and the othe...

  66. [75]

    vi(Ai) wi ≥ max({vi(Aj \ S) : S ⊆ Aj and vi(S) > 0}) wj

  67. [76]

    This definition also hints towards how to handle goods with non-additive valuations

    min({vi(Ai \ S) : S ⊆ Ai and vi(S) < 0}) wi ≥ vi(Aj) wj . This definition also hints towards how to handle goods with non-additive valuations. Even if every good in j’s bundle has (marginal) value zero to agent i, some subset of j’s bundle must have positive (marginal) value. ...

  68. [77]

    Definition 15 (APS (dual))

    gives another equivalent definition of APS, called the dual definition. Definition 15 (APS (dual)) . Let I := ([ n], [m], (vi)n i=1, w) be a fair division instance. For an agent i and any z ∈ R, let Sz := {S ⊆ [m] : vi(S) ≥ z}. Then agent i’s AnyPrice share, denoted by APSi, i...

  69. [78]

    They prove this only for goods, but their proof can be easily adapted to the case of mixed manna

    show that the primal and dual definitions of APS are equivalent. They prove this only for goods, but their proof can be easily adapted to the case of mixed manna. Lemma 12. Definitions 14 and 15 are equivalent. Proof. Let pAPSi and dAPSi be agent i’s AnyPrice shares given by t...

  70. [79]

    vi(Ai ∪ S) > wi · vi([m]) for every S ⊆ [m] \ Ai such that vi(S | Ai) > 0

  71. [80]

    We identify special cases where our definition of PROPx (Definition 16) is equivalent to well- known definitions of PROPx under those special cases

    vi(Ai \ S) > wi · vi([m]) for every S ⊆ Ai such that vi(S | Ai \ S) < 0. We identify special cases where our definition of PROPx (Definition 16) is equivalent to well- known definitions of PROPx under those special cases. Lemma 13. In the fair division instance I := ([n], [m],...

  72. [81]

    Intuitively, each agent should get 1 good each, and that should be considered fair

    Consider three goods of values 100, 10, and 1. Intuitively, each agent should get 1 good each, and that should be considered fair

  73. [82]

    Intuitively, the allocation ({−1000, 10, 1}, {−1000}, {−1000}) should not be fair, and the allocation ({−1000, 10}, {−1000, 1}, {−1000}) should be fair

    Consider 5 items of values −1000, −1000, −1000, 10, 1. Intuitively, the allocation ({−1000, 10, 1}, {−1000}, {−1000}) should not be fair, and the allocation ({−1000, 10}, {−1000, 1}, {−1000}) should be fair. In both allocations, removing a chore makes an agent PROP-satisfied, ...

  74. [83]

    ∀(I, A) ∈ Ω, for every agent i in I, A is F2-fair to i whenever A is F1-fair to i

    showed that for equal entitlements and goods with additive valuations, a PROPm allocation always exists and can be computed in polynomial time. It can be verified that their result also works for our definition of PROPm (Definition 17). B.6.2 Defining PROPavg PROPavg was first...

  75. [84]

    vi is doubly strictly monotone, i.e., [m] = G∪C, vi(g | ·) > 0 for every g ∈ G, and vi(c | ·) < 0 for every c ∈ C

  76. [85]

    Agents have equal entitlements, vi is submodular, and all items are goods for agent i

  77. [86]

    vi is submodular and all items are chores for agent i. Proof. Suppose i is EFX-satisfied but not EF1-satisfied. Suppose i EF1-envies j. Since i EF1-envies j, we get that for all t ∈ Aj, we have vi(Ai) wi < vi(Aj \ {t}) wj . Since i is EFX-satisfied, we get that for all t ∈ Aj ...

  78. [87]

    A is EFX-fair to agent i

  79. [88]

    vi(g | Ai) > 0 for all g ∈ G \ Ai

  80. [89]

    Algorithm 1 improvei(Z): Here Z is an allocation for the fair division instance ([ n], G∪ C, (vj)n j=1, w)

    vi(c | Ai \ {c}) < 0 for all c ∈ Ai ∩ C. Algorithm 1 improvei(Z): Here Z is an allocation for the fair division instance ([ n], G∪ C, (vj)n j=1, w). 1: while true do 2: if ∃g ∈ G ∩ Zj for some j ∈ [n] \ {i} such that vi(g | Zi) = 0 then 3: Zi = Zi ∪ {g}. 4: Zj = Zj \ {g}. 5: e...

  81. [90]

    If X is EFX-fair to agent 1, then Y is also EFX-fair to agent 1

  82. [91]

    |Y1 ∩ G| − |Y1 ∩ C| > |X1 ∩ G| − |X1 ∩ C|

  83. [92]

    The first invariant ensures that bB is also EFX-fair to agent 1

    v1(Y1) = v1(X1). The first invariant ensures that bB is also EFX-fair to agent 1. The second invariant ensures that improve1 terminates. Then using Observation 23, we get that bB is EF1-fair to agent 1. The third invariant ensures that v1( bB1) = v1(B1) ≤ v1(A1), which makes b...

  84. [93]

    vi is doubly strictly monotone, i.e., [m] = G∪C, vi(g | ·) > 0 for every g ∈ G, and vi(c | ·) < 0 for every c ∈ C. Proof. Suppose allocation A is PROPm-fair to i but not PROP1-fair to i. Then

  85. [94]

    vi(Ai) < wivi([m]) (by PROP1 unfairness)

  86. [95]

    vi(Ai \ {c}) ≤ wivi([m]) for all c ∈ Ai (by PROP1 unfairness)

  87. [96]

    vi(Ai ∪ {g}) ≤ wivi([m]) for all g ∈ [m] \ Ai (by PROP1 unfairness)

  88. [97]

    vi(Ai \ {c}) > wivi([m]) for all c ∈ Ai such that vi(c | Ai \ {c}) < 0 (by PROPm fairness)

  89. [98]

    Definition 17 for the definition of T )

    T = ∅ or vi(Ai)+max(T ) > wivi([m]) (by PROPm fairness; c.f. Definition 17 for the definition of T ). By 2 and 4, we get vi(c | Ai \ {c}) ≥ 0 for all c ∈ Ai. We now show that vi(Ai) ≥ 0. If vi is doubly strictly monotone, then Ai only contains goods, so vi(Ai) ≥ 0. Now suppose...

  90. [99]

    v1(g | A2 \ {g}) ≤ 0 for all g ∈ A2

  91. [100]

    v1(g | A1) > 0 for some g ∈ A2

  92. [101]

    v1 is submodular. Proof. If A is PROP-fair to agent 1, then we are done, so assume A is not PROP-fair to agent

  93. [102]

    Since v1(A1) < w1v1([m]), we get v1(A2) > w2v1([m])

    By subadditivity of v1, we get v1([m]) ≤ v1(A1) + v1(A2). Since v1(A1) < w1v1([m]), we get v1(A2) > w2v1([m]). Hence, v1(A1)/w1 < v1([m]) < v1(A2)/w2, so agent 1 envies agent 2. Since A is EF1-fair to agent 1, there are two cases: Case 1: ∃c ∈ A1 such that v1(A1 \ {c}) w1 ≥ v1...

  94. [103]

    Lemma 37 (EEFX =⇒ PROPx, Lemma 2.1 of [47])

    Hence, v1(g∗ | Ai) > 0 if v1 is submodular, and thus, A is PROP1-fair to agent 1. Lemma 37 (EEFX =⇒ PROPx, Lemma 2.1 of [47]). Consider a fair division instance ([n], [m], (vi)n i=1, w) where the items are chores to agent i and vi is subadditive. If an allocation A is epistemi...

  95. [104]

    The items are goods to agent i (i.e., vi(g | R) ≥ 0 for all R ⊆ [m] and g ∈ [m] \ R)

  96. [105]

    vi is additive and wi ≤ wj for all j ∈ [n] \ {i}. Proof. Suppose agent i is not EFX-satisfied by A, i.e., she EFX-envies some agent j. Then ∃S ⊆ Ai ∪ Aj where either

  97. [106]

    S ⊆ Aj, vi(S | Ai) > 0, and vi(Ai) wi < vi(Aj \ S) wj

  98. [107]

    If all items are goods, case 2 doesn’t occur

    S ⊆ Ai, vi(S | Ai \ S) < 0, and vi(Ai \ S) wi < vi(Aj) wj . If all items are goods, case 2 doesn’t occur. Case 1: S ⊆ Aj Let B be the allocation obtained by transferring S from Aj to Ai. Formally, let Bi := Ai ∪ S, Bj := Aj \ S, and Bk := Ak for all k ∈ [n] \ {i, j}. Then vi(B...

  99. [108]

    The items are goods to agent 1

  100. [109]

    v1 is additive and w1 ≤ w2. Proof. If agent 1 doesn’t envy agent 2, she is EFX-satisfied. Otherwise, she is EFX-satisfied because of Lemma 40. Theorem 2 in [28] states that an MMS allocation is also an EEFX allocation (for additive valuations over goods and equal entitlements)...

  101. [110]

    All items are goods to agent i

  102. [111]

    vi is additive. Proof. We will show that agent i’s leximin n-partition is her MXS-certificate for A, which would prove that A is MXS-fair to agent i. Without loss of generality, assume i = 1. Let P be a leximin n-partition of v1 (c.f. Definition 19) such that v1(P1) ≤ v1(P2) ≤...

  103. [112]

    agents have equal entitlements and vi’s marginals are triboolean, i.e., vi(t | S) ∈ {−1, 0, 1} for all S ⊆ [m] and t ∈ [m] \ S

  104. [113]

    vi’s marginals are binary, i.e., vi(t | S) ∈ {0, 1} for all S ⊆ [m] and t ∈ [m] \ S

  105. [114]

    vi’s marginals are negative binary, i.e., vi(t | S) ∈ {0, −1} for all S ⊆ [m] and t ∈ [m] \ S. Proof. Suppose agents have equal entitlements and vi’s marginals are triboolean. Since i is EF1- satisfied, for any other agent j, either vi(Ai) ≥ vi(Aj), or vi(Ai) ≥ vi(Aj \ {g}) fo...

  106. [115]

    Allocation A is PROP1-fair to i

  107. [116]

    Allocation A is PROPx-fair to i

  108. [117]

    vi(Ai) ≥ ⌊wivi([m])⌋. Proof. Partition [m] into goods M+ := {g ∈ [m] : vi(g) > 0}, chores M− := {c ∈ [m] : vi(c) < 0}, and neutral items M0 := {t ∈ [m] : vi(t) = 0}. Case 1: Ai has all goods and no chores. Then vi(Ai) ≥ max(0, vi([m])). If vi([m]) ≥ 0, then vi(Ai) ≥ vi([m]) ≥ ...

  109. [118]

    wi ≤ wj for all j ∈ [n] \ {i}

  110. [119]

    vi(c) ∈ {0, −1} for all c ∈ [m]. Proof. Consider any subset S of agents. On restricting A to S, we get an allocation B that is EF1-fair to i. B is also PROP1-fair to i by Lemmas 34, 35 and 36, and APS-fair to i by Lemmas 56 and 57. Hence, A is groupwise-APS-fair to i. Remark 6...

  111. [120]

    wi < 1/(n − 1) and vi has {0, 1} marginals

  112. [121]

    vi has {−1, 0} marginals. Proof. Let B be agent i’s M1S-certificate for A. Let k := vi(Bi). Then vi(Ai) ≥ k and B is EF1-fair to i. If vi(Ai) ≥ wivi([m]), then A is PROP-fair to i, and we are done. Now let k ≤ vi(Ai) < wivi([m]). Define sets J0, JG, and JC as follows: J0 := j ...

  113. [122]

    Agent 1 is not EEF1-satisfied by A, since in any EEF1-certificate B, some agent j ∈ {2, 3} receives at most one chore of value 70, and agent 1 would EF1-envy j

    Agents 2 and 3 have disutility at most 20 in A, so A is MEFS-fair and PROP-fair to them. Agent 1 is not EEF1-satisfied by A, since in any EEF1-certificate B, some agent j ∈ {2, 3} receives at most one chore of value 70, and agent 1 would EF1-envy j. D.3 Two Equally-Entitled Ag...

  114. [123]

    APS1 = 4 and APS2 = APS3 = 1

  115. [124]

    X is APS ⇐ ⇒X is groupwise-APS (GAPS) ⇐ ⇒X is PROP1

  116. [125]

    WMMS1 = 3 and WMMS2 = WMMS3 = 15/14

  117. [126]

    Therefore,

    X is WMMS ⇐ ⇒X is groupwise-WMMS (GWMMS) ⇐ ⇒X is EFX ⇐ ⇒X is M1S. Therefore,

  118. [127]

    M1S+PROP1 is infeasible for this instance

  119. [128]

    GWMMS+EFX doesn ’t imply PROP1

  120. [129]

    GAPS doesn ’t imply M1S. Proof. By Lemma 57, APS 1 = ⌊ 7×7 12 ⌋ = 4 and APS 2 = APS3 = ⌊ 5×7 24 ⌋ = 1. By Lemmas 56 and 57, an allocation is APS iff it is PROP1. Any GAPS allocation is also APS by definition. We will now show that any APS allocation is also GAPS. Formally, let...

  121. [130]

    APS 1 = ⌊ 14×6 19 ⌋ = 4 and APS 2 = ⌊ 5×6 19 ⌋ = 1

    c = (5 , 1, 1) and S = {1, 2}: bI has 6 goods and entitlement vector (14 /19, 5/19). APS 1 = ⌊ 14×6 19 ⌋ = 4 and APS 2 = ⌊ 5×6 19 ⌋ = 1. Hence, bA is APS for bI

  122. [131]

    c = (5, 1, 1) and S = {1, 3}: Similar to the S = {1, 2} case

  123. [132]

    APS 3 = APS3 = 1, so bA is APS for bI

    c = (5, 1, 1) and S = {2, 3}: bI has 2 goods and entitlement vector (1/2, 1/2). APS 3 = APS3 = 1, so bA is APS for bI

  124. [133]

    APS 1 = ⌊ 14×6 19 ⌋ = 4 and APS 2 = ⌊ 5×6 19 ⌋ = 1

    c = (4 , 2, 1) and S = {1, 2}: bI has 6 goods and entitlement vector (14 /19, 5/19). APS 1 = ⌊ 14×6 19 ⌋ = 4 and APS 2 = ⌊ 5×6 19 ⌋ = 1. Hence, bA is APS for bI

  125. [134]

    APS 1 = ⌊ 14×5 19 ⌋ = 3 and APS 2 = ⌊ 5×5 19 ⌋ = 1

    c = (4 , 2, 1) and S = {1, 3}: bI has 5 goods and entitlement vector (14 /19, 5/19). APS 1 = ⌊ 14×5 19 ⌋ = 3 and APS 2 = ⌊ 5×5 19 ⌋ = 1. Hence, bA is APS for bI. 55

  126. [135]

    APS 2 = APS3 = ⌊ 1×3 2 ⌋ = 1

    c = (4, 2, 1) and S = {2, 3}: bI has 3 goods and entitlement vector (1/2, 1/2). APS 2 = APS3 = ⌊ 1×3 2 ⌋ = 1. Hence, bA is APS for bI

  127. [136]

    Hence, any APS allocation for I is also GAPS

    c = (4, 1, 2): Similar to the c = (4, 2, 1) case. Hence, any APS allocation for I is also GAPS. For any allocation X, define f (X) := 3 min j=1 |Xj| wj . Then WMMSi = wi maxX f (X) for all i ∈ [3]. If |X1| ≤2, then f (X) ≤ |X1|/w1 ≤ 24/7 = 3 + 3/7. If |X2| ≤1 or |X3| ≤1, f (X)...

  128. [137]

    If |X1| ≤2, then f (X) ≤ |X1|/w1 ≤ 38/14 = 2 + 10 /14

    S = {1, 2}: bI has 5 goods and entitlement vector (14 /19, 5/19). If |X1| ≤2, then f (X) ≤ |X1|/w1 ≤ 38/14 = 2 + 10 /14. If |X2| ≤1, then f (X) ≤ |X2|/w2 ≤ 19/5 = 3 + 10 /14. Otherwise, |X1| = 3 and |X2| = 2, so f (X) = min(3/w1, 2/w2) = min(57/14, 38/5) = 57/14 = 4+1 /14. Hen...

  129. [139]

    Then WMMS 1 = WMMS2 = 2

    S = {2, 3}: bI has 4 goods and entitlement vector (1 /2, 1/2). Then WMMS 1 = WMMS2 = 2. Hence, bA is WMMS for bI. Hence, any WMMS allocation for I is also GWMMS. Any GWMMS allocation is EFX by Lemma 41, and any EFX allocation is M1S by Lemma 21. We will now show that any M1S a...

  130. [140]

    Lemma 98

    also proves that EF1+PROP1 allocations may not exist for unequal entitlements, We use a different counterexample in Lemma 97, which allows us to also prove other non-implications. Lemma 98. Consider a fair division instance I := ([3], [7], (vi)3 i=1, w), where the entitlement ...

  131. [141]

    Let X be an allocation. Then

  132. [142]

    APS1 = −4 and APS2 = APS3 = −2. 56

  133. [143]

    X is APS ⇐ ⇒X is PROP1

  134. [144]

    WMMS1 = −5 and WMMS2 = WMMS3 = −35/18

  135. [145]

    X is WMMS ⇐ ⇒X is groupwise-WMMS ⇐ ⇒(|X1| = 5 and |X2| = |X3| = 1)

  136. [146]

    Therefore,

    X is EFX ⇐ ⇒X is M1S ⇐ ⇒(|X1| = 3 and |X2| = |X3| = 2). Therefore,

  137. [147]

    PROP1+WMMS is infeasible for this instance

  138. [148]

    M1S+WMMS is infeasible for this instance

  139. [149]

    GWMMS doesn ’t imply PROP1 or M1S. Proof. Note that ⌊−x⌋ = −⌈x⌉ for all x ∈ R. By Lemma 57, −APS1 = ⌈ 9×7 16 ⌉ = 4, and −APS2 = −APS3 = ⌈ 7×7 32 ⌉ = 2. By Lemmas 56 and 57, an allocation is APS iff it is PROP1. For any allocation X, define f (X) := 3 max j=1 |Xj| wj . Then −WM...

  140. [150]

    Let X be an allocation for bI

    S = {1, 2}: bI has 6 chores and entitlement vector bw := (18/25, 7/25). Let X be an allocation for bI. Let bf (X) := max 2 j=1 |Xj|/ bwj. If |X1| ≥6, then bf (X) ≥ 6/ bw1 = 25/3 = 8 + 1 /3. If |X2| ≥2, then bf (X) ≥ 2/ bw2 = 50/7 = 7 + 1/7. Otherwise, |X1| = 5 and |X2| = 1, so...

  141. [151]

    S = {1, 3}: Similar to the S = {1, 2} case

  142. [152]

    Then −WMMS1 = −WMMS2 =

    S = {2, 3}: bI has 2 chores and entitlement vector (1/2, 1/2). Then −WMMS1 = −WMMS2 =

  143. [153]

    Hence, A is GWMMS

    Hence, bA is WMMS for bI. Hence, A is GWMMS. Suppose X is M1S. Let A be agent 1’s M1S certificate. Then |X1| ≤ |A1| and A is EF1-fair to agent 1. Suppose |A1| ≥4. Then |A2| ≤1 or |A3| ≤1. Without loss of generality, let |A2| ≤1. Then |A1| −1 w1 ≥ 3 w1 = 5 + 1 3 > 5 − 3 7 = 1 w...

  144. [154]

    |X| ≤1 = ⇒ bv(g | X) = 2 + ε

  145. [155]

    |X| = 2 = ⇒ bv(g | X) ∈ {1 + ε, 2 + ε}

  146. [156]

    |X| = 3 = ⇒ bv(g | X) ∈ {ε, 1 + ε}

  147. [157]

    Hence, bv(g | X) decreases with |X|, so bv is submodular

    |X| = 4 = ⇒ bv(g | X) = ε. Hence, bv(g | X) decreases with |X|, so bv is submodular. The MMS is less than 6 because for every set in C, its complement is not in C. The APS is 6 + 3ε by the dual definition of APS (Definition 15), by setting xS = 1/4 when S ∈ C. For identical va...

  148. [158]

    Hence, A is not M1S-fair to agent 1

    If one good is removed from their bundle, its value can drop by at most 8, so B is not EF1-fair to agent 1, which is a contradiction. Hence, A is not M1S-fair to agent 1. Lemma 120 (GMMS ̸=⇒ APS). Let there be 15 items of sizes 65/96, 31/96, 31/96, 31/96, 23/96, 23/96, 23/96, ...

  149. [159]

    S = ∅ =⇒ vi(g | S) = 1 + ε

  150. [160]

    |S| = 1 = ⇒ vi(g | S) ∈ {1/2 + ε, 1 + ε}

  151. [161]

    |S| = 2 = ⇒ vi(g | S) ∈ {ε, 1/2 + ε}

  152. [162]

    Hence, vi(g | S) decreases with |S|, so vi is submodular

    |S| = 3 = ⇒ vi(g | S) = ε. Hence, vi(g | S) decreases with |S|, so vi is submodular. Suppose agent 1 is MMS-satisfied by an allocation A. Then |A1| ≥2. If |A1| ≥3, then |A1| ≤1, so v2(A2) ≤ 1 +ε, and hence, A is not MMS-fair to agent 2. If |A1| = 2, then A1 ∈ {{1, 2}, {3, 4}}....

  153. [2018]

    doi:10.1609/aaai.v32i1.11463

    doi

Pith tools

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