Pith. sign in

REVIEW 3 major objections 4 minor 82 references

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

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

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

Pith's one-line read PMMS allocations exist for three restricted valuation classes, and PMMS can fail where EFX holds.

desk verdict Separation result and bivalued section are genuinely useful; pair-demand proof is broken as written and the binary termination argument has a gap. read the letter →

arxiv 2507.14957 v2 pith:SJAH2HYM submitted 2025-07-20 cs.GT cs.AIcs.DS

Jaros{l}aw Byrka , Franciszek Malinka , Tomasz Ponitka This is my paper · ORCID
classification cs.GTcs.AIcs.DS
keywords fairdivisionindivisiblegoodspairwisemaximinshareenvy-freeuptoanygoodbivaluedvaluationsbinary-valuedpair-demandMMS-feasible
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper studies two fairness standards for dividing indivisible items: EFX, the condition that no agent should envy another after removing any single item, and PMMS, a stricter pairwise condition tied to the cut-and-choose guarantee. Its central claim is that PMMS allocations always exist for three restricted valuation classes—personalized bivalued, binary-valued MMS-feasible, and pair-demand—and can be computed in polynomial time. It also constructs a three-agent instance with one additive and two monotone valuations where no PMMS allocation exists, while EFX is known to always exist there. The paper therefore isolates PMMS as strictly harder than EFX and gives new existence results for PMMS in settings where the EFX question is still open.

What carries the argument

The load-bearing machinery differs by theorem. For personalized bivalued valuations, it is a personalized Match-and-Freeze algorithm that repeatedly computes a maximum-weight maximal matching in a bipartite graph whose edge weights are $a_i/b_i$, freezing matched agents for $\lfloor a_i/b_i - 1\rfloor$ rounds; Lemma 4.1 shows the unmatched-to-matched ratio structure inside each component, and Lemma 4.3 turns the inequality $v_i(X_i) \geq v_i(X_j) - b_i$ into EFX, and into PMMS under the factored condition. For binary-valued MMS-feasible valuations, the cut-and-choose graph points each agent either at an agent whose bundle satisfies their pairwise fair-share bound or at one who violates it; Algorithm 2 reallocates along cycles or lollipops, and the lexicographic increase of $(W,E)$ forces termination in $O(n^2)$ iterations. For pair-demand valuations, the reversed round-robin algorithm gives each agent two items $g_i,h_i$, and Lemma 6.1 says that among four items the fair share is determined by the two middle-value items, making the two chosen items sufficient.

What would settle it

Construct the five-item, two-agent instance in which the fair share of the full union exceeds the fair share of the four selected items $\{g_i,h_i,x_j,y_j\}$, with the leftover item assigned unfavorably in the second round of Algorithm 3. If agent $i$'s final bundle falls below $\mu_i(X_i\cup X_j)$, that single run refutes the claimed guarantee of Theorem 4 as stated.

Watch

Extended reading notes

Core claim

On the paper's own terms, the contribution is a set of existence and non-existence theorems. Theorem 1 gives a three-agent instance with one additive and two arbitrary monotone valuations that admits no PMMS allocation, separating PMMS from EFX since EFX is guaranteed for such instances. Theorem 2 shows EFX allocations exist for personalized bivalued valuations, and PMMS allocations exist when the two item values are factored (the larger is an integer multiple of the smaller), via a modified matching algorithm. Theorem 3 shows PMMS allocations exist for binary-valued MMS-feasible valuations, where every bundle is worth 0 or 1, even without monotonicity, so the result covers chores and mixed manna, via a new cut-and-choose graph procedure. Theorem 4 shows PMMS allocations exist for pair-demand valuations, where each agent values at most their two most desired items, by a two-stage reversed round-robin algorithm. All existence proofs come with polynomial-time algorithms.

Load-bearing premise

The pair-demand proof hinges on the assumption that adding leftover items to a bundle cannot increase the fair share above what can be guaranteed by the four selected items; a five-item example shows this assumption can fail, leaving Theorem 4's general argument exposed.

Editorial extensions

If this is right

  • For personalized bivalued valuations, the paper's algorithm outputs an EFX allocation in polynomial time, and a PMMS allocation when the valuations are factored.
  • For binary-valued MMS-feasible valuations, a PMMS allocation exists and is computable in polynomial time, with no monotonicity assumption; the same algorithm therefore covers chores and mixed manna.
  • For pair-demand valuations, a PMMS allocation exists and is computable in polynomial time.
  • The three-agent counterexample shows that the known EFX guarantee for three agents with one MMS-feasible valuation does not carry over to PMMS, so any future positive result for that setting needs a new idea.
  • Because PMMS implies EFX in non-degenerate instances, the positive PMMS theorems also deliver EFX allocations there, and EFX$_{>0}$ generally.

Reading between the lines

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

  • Editorial inference: the success of the cut-and-choose graph for binary-valued valuations suggests that PMMS existence may survive for other finite-valued MMS-feasible classes, such as valuations taking values in $\{0,1,\dots,K\}$, as long as each violated pair has a detectable gap.
  • Editorial inference: the three-agent separation indicates that PMMS is not merely a technical strengthening of EFX; any proof of PMMS existence for additive valuations will likely have to use additivity in an essential way.
  • Editorial inference: if the pair-demand fair-share monotonicity gap is repaired, the reversed round-robin argument might extend to $k$-demand valuations for $k>2$, since the same order-statistic structure appears in Lemma 6.1.
  • Editorial inference: the failure of Nash-welfare maximization for personalized bivalued EFX suggests that matching-based algorithms, rather than welfare optimization, are the right tool for personalized two-value instances.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies two fairness notions for indivisible items, EFX and the stronger PMMS condition. It claims four main results: (1) a three-agent instance with one additive and two monotone valuations admitting no PMMS allocation, separating EFX from PMMS; (2) existence and polynomial-time computation of EFX allocations for personalized bivalued valuations, and of PMMS allocations when the valuations are additionally factored; (3) existence of PMMS allocations for binary-valued MMS-feasible valuations, without assuming monotonicity; and (4) existence of PMMS allocations for pair-demand valuations via a reversed round-robin algorithm. The proofs are mostly constructive, and the paper includes a computational search for the non-existence example.

Significance. If all four results are correct, the paper makes a solid contribution: it gives the first known separation between EFX and PMMS for three agents under the standard MMS-feasibility assumption, and it extends PMMS existence to several previously open valuation classes, including non-monotone binary valuations. The algorithms are simple and claimed to run in polynomial time, which is valuable. The construction in Theorem 1 is explicit and the paper appropriately credits the independent discovery of the personalized bivalued EFX result. However, two load-bearing parts of the manuscript need repair before the results can be relied upon.

major comments (3)
  1. [Section 6, Proof of Theorem 4] The proof asserts the chain vi({gi,hi}) ≥ μi({gi,hi,xj,yj}) ≥ μi(Xi ∪ Xj). The second inequality has the wrong direction: since {gi,hi,xj,yj} ⊆ Xi ∪ Xj and the fair-share function μi is monotone with respect to supersets, one obtains μi({gi,hi,xj,yj}) ≤ μi(Xi ∪ Xj), not ≥. Consequently, the application of Lemma 6.1 does not establish PMMS. The authors need either a direct proof that vi({gi,hi}) ≥ μi(Xi ∪ Xj) for pair-demand valuations, or a different algorithm and argument. Additionally, the invocation of Lemma 6.1 requires verifying that the two-item set {gi,hi} is not one of the two excluded pairs in the lemma, which is not stated in the proof.
  2. [Appendix A, Proof of Theorem 1] The non-existence proof for the three-agent instance relies on the sentence 'We have verified computationally that none of these allocations satisfies the PMMS condition' for the 90 allocations in which every agent receives a pair of items. No code, verifiable certificate, or complete machine-checkable data is provided, and Figure 4 omits isolated nodes. Since this finite check is the entire content of the non-existence claim, the proof is not verifiable as written. The authors should provide a reproducible certificate or a fully enumerated case analysis.
  3. [Section 5, Proof of Theorem 3] The termination proof for Algorithm 2 argues that the lexicographic potential (W,E) increases, but in the cycle case it only analyzes agents in the cycle. The PMMS status of agents outside the cycle can in principle change when a bundle in the cycle is replaced, so the claim that E strictly increases needs a justification for those outside agents. For binary valuations the missing argument is short (an agent with value 1 is always PMMS-satisfied, and an agent with value 0 is not), but the proof as written leaves this load-bearing step implicit.
minor comments (4)
  1. [Section 6, first paragraph] The sentence 'We being our analysis by establishing the following lemma' should read 'We begin our analysis...'.
  2. [Corollary 5.3] Corollary 5.3 states the result for 'binary-valued valuations', while Theorem 3 and the proof of Algorithm 2 require the MMS-feasibility assumption; the wording should be aligned with the theorem statement.
  3. [Figure 4 and Theorem 1 proof] The description of the graph in Figure 4 states that nodes with no adjacent edges are omitted, but the proof should specify exactly which nodes are omitted so that the triangle-free check can be reproduced from the text alone.
  4. [Lemma 4.3] The phrase 'if agent i's valuation is factored' could be read as referring to each agent's valuation individually; the intended meaning is that the valuation of the agent whose PMMS envy is being checked is factored, which is worth clarifying.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the existence and non-existence results are supported by explicit constructions, algorithms, and exhaustive case checks, with no fitted parameters or load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained against the definitions it inherits from prior work. The negative result in Theorem 1 is an explicit six-item instance whose PMMS violation is verified by a complete case analysis and a triangle-free graph, not by assuming the conclusion. The positive results in Theorems 2, 3, and 4 are proved by constructing polynomial-time algorithms and arguing they terminate with allocations satisfying the relevant fairness inequalities. No parameter is fitted to any data, no quantity is renamed as a prediction, and no uniqueness theorem from the authors' own prior work is invoked to rule out alternatives. The authors do cite their own earlier work in passing (e.g., [50, 51]), but these citations appear only in related-work surveys and are not load-bearing for any proof in this paper. The most serious concern in the manuscript is a likely mathematical error in the proof of Theorem 4, where the inequality μ_i(X_i ∪ X_j) ≤ μ_i({g_i, h_i, x_j, y_j}) appears to have the wrong direction for monotone pair-demand fair shares. That is a correctness risk, not a circularity risk: the argument does not reduce to its own assumptions; it simply appears to be invalid as written. Accordingly, the circularity score is 0.

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

The paper introduces no fitted constants; the ai,bi values in bivalued instances are part of the instance specification, not parameters chosen to make the proof work. The counterexample valuations are constructed explicitly, not fitted. No new entities such as particles or mediators are introduced.

assumptions (5)
  • domain assumption In Sections 2-4, all valuations are normalized (vi(empty)=0) and monotone, as stated in the preliminaries.
    The EFX/PMMS proofs for personalized bivalued and the separation result assume monotonicity; this is a standard modeling convention for goods.
  • domain assumption MMS-feasibility as defined in Definition 2.6 is satisfied by the binary valuations in Theorem 3, and this condition is used to bound fair shares.
    The cut-and-choose graph relies on the MMS-feasibility implication max{vi(Xs),vi(Xj)} >= mu_i(Xs union Xj).
  • ad hoc to paper The exhaustive computational check of 90 allocations in Theorem 1 is correct and complete.
    No code or certificate is provided, so the proof depends on an unverified computation.
  • ad hoc to paper In Algorithm 2, the lexicographic potential (W,E) is monotone across iterations, so previously satisfied agents remain satisfied.
    This is asserted in the termination proof but not demonstrated; outside agents' PMMS status can change when cycle bundles are reassigned.
  • ad hoc to paper In Theorem 4, mu_i(Xi union Xj) <= mu_i({gi,hi,xj,yj}), i.e., the fair share does not increase when adding items outside the chosen four.
    This is the wrong direction for the monotone fair-share function and fails for pair-demand valuations, as shown by a five-item example.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division." pith.science (2026). https://pith.science/paper/SJAH2HYM

@misc{pith2026250714957,
  author       = {Pith},
  title        = {Pith review of: Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SJAH2HYM}},
  note         = {Machine review of arXiv:2507.14957}
}
abstract

We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of EFX. Our first result constructs a three-agent instance with two monotone valuations and one additive valuation in which no PMMS allocation exists. Since EFX allocations are known to exist under these assumptions, this establishes a formal separation between EFX and PMMS. We prove existence of fair allocations for three important special cases. We show that EFX allocations exist for personalized bivalued valuations, where for each agent $i$ there exist values $a_i > b_i$ such that agent $i$ assigns value $v_i(\{g\}) \in \{a_i, b_i\}$ to each good $g$. We establish an analogous existence result for PMMS allocations when $a_i$ is divisible by $b_i$. We also prove that PMMS allocations exist for binary-valued MMS-feasible valuations, where each bundle $S$ has value $v_i(S) \in \{0, 1\}$. Notably, this result holds even without assuming monotonicity of valuations and thus applies to the fair division of chores and mixed manna. Finally, we study a class of valuations called pair-demand valuations, which extend the well-studied unit-demand valuations to the case where each agent derives value from at most two items, and we show that PMMS allocations exist in this setting. Our proofs are constructive, and we provide polynomial-time algorithms for all three existence results.

Figures

Figures reproduced from arXiv: 2507.14957 by the authors.

Figure 1
Figure 1. Illustrations of the instances used in the proof of [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. An illustration of the alternating paths used in the proofs of [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. An illustration of the operations performed by the Cut-and-Choose-Graph Procedure [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: An illustration of the triangle-free graph considered in the proof of [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

82 extracted references · 77 canonical work pages

  1. [1]

    Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms

    M. Afshinmehr, M. Ansaripour, A. Danaei, and K. Mehlhorn. Approximate EFX and exact tefx allocations for indivisible chores: Improved algorithms. CoRR, abs/2410.18655, 2024

    work page Pith review arXiv 2024

  2. [2]

    Akrami and J

    H. Akrami and J. Garg. Breaking the 3/4 barrier for approximate maximin share. In SODA, pages 74–91. SIAM, 2024

    2024

  3. [3]

    Akrami and N

    H. Akrami and N. Rathi. Epistemic EFX allocations exist for monotone valuations. In AAAI, pages 13520–13528. AAAI Press, 2025

    2025

  4. [4]

    Akrami, B

    H. Akrami, B. R. Chaudhury, M. Hoefer, K. Mehlhorn, M. Schmalhofer, G. Shahkarami, G. Varricchio, Q. Vermande, and E. van Wijland. Maximizing nash social welfare in 2-value instances. In AAAI, pages 4760–4767. AAAI Press, 2022

    work page 2022

  5. [5]

    Akrami, J

    H. Akrami, J. Garg, E. Sharma, and S. Taki. Simplification and improvement of MMS approximation. In IJCAI, pages 2485–2493. ijcai.org, 2023. 19

    work page 2023

  6. [6]

    Akrami, N

    H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R. Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. Oper. Res., 73(2):738–751, 2025

    work page 2025

  7. [7]

    Akrami, A

    H. Akrami, A. Eden, M. Feldman, A. Fiat, and Y. G. Tzur. Fair division via resource augmentation. CoRR, abs/2502.09377, 2025

    work page arXiv 2025

  8. [8]

    Amanatidis, E

    G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi. Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms, 13(4):52:1–52:28, 2017

    work page 2017

Show all 82 references
  1. [9]

    Amanatidis, G

    G. Amanatidis, G. Birmpas, and V. Markakis. Comparing approximate relaxations of envy-freeness. In IJCAI, pages 42–48. ijcai.org, 2018

    2018

  2. [10]

    Amanatidis, E

    G. Amanatidis, E. Markakis, and A. Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. , 841:94–109, 2020

    2020

  3. [11]

    Amanatidis, G

    G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris. Maxi- mum nash welfare and other stories about EFX. Theor. Comput. Sci. , 863:69–85, 2021

    2021

  4. [12]

    Amanatidis, H

    G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., 322:103965, 2023

    2023

  5. [13]

    Amanatidis, A

    G. Amanatidis, A. Filos-Ratsikas, and A. Sgouritsa. Pushing the frontier on approximate EFX allocations. In EC, pages 1268–1286. ACM, 2024

    2024

  6. [14]

    Amanatidis, A

    G. Amanatidis, A. Lolos, E. Markakis, and V. Turmel. Online fair division for personalized 2-value instances. CoRR, abs/2505.22174, 2025

    2025 arXiv

  7. [15]

    H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation of indivisible goods and chores. Auton. Agents Multi Agent Syst. , 36(1):3, 2022

    2022

  8. [16]

    H. Aziz, J. Lindsay, A. Ritossa, and M. Suzuki. Fair allocation of two types of chores. In AAMAS, pages 143–151. ACM, 2023

    2023

  9. [17]

    Babaioff, T

    M. Babaioff, T. Ezra, and U. Feige. Fair and truthful mechanisms for dichotomous valua- tions. In AAAI, pages 5119–5126. AAAI Press, 2021

    2021

  10. [18]

    Barman and S

    S. Barman and S. K. Krishnamurthy. Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput. , 8(1):5:1–5:28, 2020

    2020

  11. [19]

    Barman and M

    S. Barman and M. Suzuki. Compatibility of fairness and nash welfare under subadditive valuations. CoRR, abs/2407.12461, 2024

    2024

  12. [20]

    Barman and P

    S. Barman and P. Verma. Existence and computation of maximin fair allocations under matroid-rank valuations. In AAMAS, pages 169–177. ACM, 2021

    2021

  13. [21]

    Barman and P

    S. Barman and P. Verma. Approximating nash social welfare under binary XOS and binary subadditive valuations. In WINE, volume 13112 of Lecture Notes in Computer Science , pages 373–390. Springer, 2021

    2021

  14. [22]

    Barman, A

    S. Barman, A. Biswas, S. K. K. Murthy, and Y. Narahari. Groupwise maximin fair alloca- tion of indivisible goods. In AAAI, pages 917–924. AAAI Press, 2018. 20

    2018

  15. [23]

    Barman, U

    S. Barman, U. Bhaskar, and N. Shah. Optimal bounds on the price of fairness for indivisible goods. In WINE, volume 12495 of Lecture Notes in Computer Science , pages 356–369. Springer, 2020

    2020

  16. [24]

    Barman, A

    S. Barman, A. Krishna, Y. Narahari, and S. Sadhukhan. Achieving envy-freeness with limited subsidies under dichotomous valuations. In IJCAI, pages 60–66. ijcai.org, 2022

    2022

  17. [25]

    Barman, V

    S. Barman, V. V. Narayan, and P. Verma. Fair chore division under binary supermodular costs. In AAMAS, pages 2863–2865. ACM, 2023

    2023

  18. [26]

    Barman, D

    S. Barman, D. Kar, and S. Pathak. Parameterized guarantees for almost envy-free alloca- tions. In AAMAS, pages 151–159. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024

    2024

  19. [27]

    X. Bei, X. Lu, P. Manurangsi, and W. Suksompong. The price of fairness for indivisible goods. Theory Comput. Syst. , 65(7):1069–1093, 2021

    2021

  20. [28]

    Benabbou, M

    N. Benabbou, M. Chakraborty, A. Igarashi, and Y. Zick. Finding fair and efficient alloca- tions for matroid rank valuations. ACM Trans. Economics and Comput. , 9(4):21:1–21:41, 2021

    2021

  21. [29]

    B. A. Berendsohn, S. Boyadzhiyska, and L. Kozma. Fixed-point cycles and approximate EFX allocations. In MFCS, volume 241 of LIPIcs, pages 17:1–17:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022

    2022

  22. [30]

    Berger, A

    B. Berger, A. Cohen, M. Feldman, and A. Fiat. Almost full EFX exists for four agents. In AAAI, pages 4826–4833. AAAI Press, 2022

    2022

  23. [31]

    Brams and A

    S. Brams and A. D. Taylor. The Win-Win Solution: Guaranteeing Fair Shares to Every- body. W. W. Norton & Company, 2000

    2000

  24. [32]

    Brustle, J

    J. Brustle, J. Dippel, V. V. Narayan, M. Suzuki, and A. Vetta. One dollar each eliminates envy. In EC, pages 23–39. ACM, 2020

    2020

  25. [33]

    X. Bu, Z. Li, S. Liu, J. Song, and B. Tao. Fair division with allocator’s preference. In WINE, volume 14413 of Lecture Notes in Computer Science , pages 77–94. Springer, 2023

    2023

  26. [34]

    X. Bu, J. Song, and Z. Yu. EFX allocations exist for binary valuations. In IJTCS-F A W, volume 13933 of Lecture Notes in Computer Science , pages 252–262. Springer, 2023

    2023

  27. [35]

    X. Bu, Z. Li, S. Liu, X. Lu, and B. Tao. Best-of-both-worlds fair allocation of indivisible and mixed goods. CoRR, abs/2410.06877, 2024

    2024 arXiv

  28. [36]

    X. Bu, Z. Li, S. Liu, J. Song, and B. Tao. Approximability landscape of welfare maximiza- tion within fair allocations. In EC, pages 412–440. ACM, 2025

    2025

  29. [37]

    Caragiannis and S

    I. Caragiannis and S. Ioannidis. Computing envy-freeable allocations with limited subsidies. In WINE, volume 13112 of Lecture Notes in Computer Science , pages 522–539. Springer, 2021

    2021

  30. [38]

    Caragiannis, N

    I. Caragiannis, N. Gravin, and X. Huang. Envy-freeness up to any item with high nash welfare: The virtue of donating items. In EC, pages 527–545. ACM, 2019

    2019

  31. [39]

    Caragiannis, D

    I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput. , 7 (3):12:1–12:32, 2019. 21

    2019

  32. [40]

    Caragiannis, J

    I. Caragiannis, J. Garg, N. Rathi, E. Sharma, and G. Varricchio. New fairness concepts for allocating indivisible items. In IJCAI, pages 2554–2562. ijcai.org, 2023

    2023

  33. [41]

    B. R. Chaudhury, J. Garg, K. Mehlhorn, R. Mehta, and P. Misra. Improving EFX guar- antees through rainbow cycle number. In EC, pages 310–311. ACM, 2021

    2021

  34. [42]

    B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput. , 50(4):1336–1358, 2021

    2021

  35. [43]

    B. R. Chaudhury, J. Garg, and K. Mehlhorn. EFX exists for three agents. J. ACM, 71(1): 4:1–4:27, 2024

    2024

  36. [44]

    Christodoulou and S

    G. Christodoulou and S. Mastrakoulis. Exact and approximate maximin share allocations in multi-graphs. CoRR, abs/2506.20317, 2025

    2025 arXiv

  37. [45]

    Christoforidis and C

    V. Christoforidis and C. Santorinaios. On the pursuit of EFX for chores: Non-existence and approximations. In IJCAI, pages 2713–2721. ijcai.org, 2024

    2024

  38. [46]

    S. Dai, X. Guo, H. Miao, G. Gao, Y. Xu, and Y. Zhang. The existence and efficiency of pmms allocations. Theoretical Computer Science, 989:114388, 2024

    2024

  39. [47]

    Deligkas, T

    A. Deligkas, T. Melissourgos, and P. G. Spirakis. Walrasian equilibria in markets with small demands. In AAMAS, pages 413–419. ACM, 2021

    2021

  40. [48]

    Ebadian, D

    S. Ebadian, D. Peters, and N. Shah. How to fairly allocate easy and difficult chores. In AAMAS, pages 372–380. International Foundation for Autonomous Agents and Multiagent Systems (IF AAMAS), 2022

    2022

  41. [49]

    Feige, A

    U. Feige, A. Sapir, and L. Tauber. A tight negative example for MMS fair allocations. In WINE, volume 13112 of Lecture Notes in Computer Science , pages 355–372. Springer, 2021

    2021

  42. [50]

    Feldman, S

    M. Feldman, S. Mauras, V. V. Narayan, and T. Ponitka. Breaking the envy cycle: Best-of- both-worlds guarantees for subadditive valuations. In EC, pages 1236–1266. ACM, 2024

    2024

  43. [51]

    Feldman, S

    M. Feldman, S. Mauras, and T. Ponitka. On optimal tradeoffs between EFX and nash welfare. In AAAI, pages 9688–9695. AAAI Press, 2024

    2024

  44. [52]

    Feldman, J

    M. Feldman, J. Garg, V. V. Narayan, and T. Ponitka. Proportionally fair makespan approximation. In AAAI, pages 13839–13846. AAAI Press, 2025

    2025

  45. [53]

    D. Foley. Resource allocation and the public sector. Yale Economic Essays , 7(1):45–98, 1967

    1967

  46. [54]

    Garg and E

    J. Garg and E. Sharma. Best-of-both-worlds fairness of the envy-cycle-elimination algo- rithm. CoRR, abs/2410.08986, 2024

    2024 arXiv

  47. [55]

    Garg and E

    J. Garg and E. Sharma. Exploring relations among fairness notions in discrete fair division. CoRR, abs/2502.02815, 2025

    2025 arXiv

  48. [56]

    Garg and S

    J. Garg and S. Taki. An improved approximation algorithm for maximin shares. Artif. Intell., 300:103547, 2021

    2021

  49. [57]

    J. Garg, P. McGlaughlin, and S. Taki. Approximating maximin share allocations. In SOSA, volume 69 of OASIcs, pages 20:1–20:11. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2019. 22

    2019

  50. [58]

    J. Garg, E. Husic, W. Li, L. A. V´ egh, and J. Vondr´ ak. Approximating nash social welfare by matching and local search. In STOC, pages 1298–1310. ACM, 2023

    2023

  51. [59]

    J. Garg, A. Murhekar, and J. Qin. New algorithms for the fair and efficient allocation of indivisible chores. In IJCAI, pages 2710–2718. ijcai.org, 2023

    2023

  52. [60]

    J. Garg, A. Murhekar, and J. Qin. Constant-factor EFX exists for chores. In STOC, pages 1580–1589. ACM, 2025

    2025

  53. [61]

    Ghodsi, M

    M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami. Fair allocation of indivisible goods: Improvements and generalizations. In EC, pages 539–556. ACM, 2018

    2018

  54. [62]

    Halpern and N

    D. Halpern and N. Shah. Fair division with subsidy. In SAGT, volume 11801 of Lecture Notes in Computer Science , pages 374–389. Springer, 2019

    2019

  55. [63]

    Halpern, A

    D. Halpern, A. D. Procaccia, A. Psomas, and N. Shah. Fair division with binary valuations: One rule to rule them all. In WINE, volume 12495 of Lecture Notes in Computer Science , pages 370–383. Springer, 2020

    2020

  56. [64]

    Hummel and A

    H. Hummel and A. Igarashi. Keeping the harmony between neighbors: Local fairness in graph fair division. In AAMAS, pages 852–860. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024

    2024

  57. [65]

    V. P. HV, P. Ghosal, P. Nimbhorkar, and N. Varma. EFX exists for three types of agents. In EC, pages 101–128. ACM, 2025

    2025

  58. [66]

    S. C. Jahan, M. Seddighin, S. M. S. Javadi, and M. Sharifi. Rainbow cycle number and EFX allocations: (almost) closing the gap. In IJCAI, pages 2572–2580. ijcai.org, 2023

    2023

  59. [67]

    Jin and B

    J. Jin and B. Tao. On pareto-optimal and fair allocations with personalized bi-valued utilities. CoRR, abs/2507.18251, 2025

    2025

  60. [68]

    Kobayashi, R

    Y. Kobayashi, R. Mahara, and S. Sakamoto. EFX allocations for indivisible chores: Matching-based approach. Theor. Comput. Sci. , 1026:115010, 2025

    2025

  61. [69]

    H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83–97, 1955

    1955

  62. [70]

    Kurokawa

    D. Kurokawa. Fair Division in Game Theoretic Settings . PhD thesis, Carnegie Mellon University, 2017

    2017

  63. [71]

    Kurokawa, A

    D. Kurokawa, A. D. Procaccia, and J. Wang. Fair enough: Guaranteeing approximate maximin shares. J. ACM, 65(2):8:1–8:27, 2018

    2018

  64. [72]

    B. Li, Y. Li, and X. Wu. Almost (weighted) proportional allocations for indivisible chores. In WWW, pages 122–131. ACM, 2022

    2022

  65. [73]

    Z. Li, S. Liu, X. Lu, B. Tao, and Y. Tao. A complete landscape for the price of envy- freeness. In AAMAS, pages 1183–1191. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024

    2024

  66. [74]

    R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In EC, pages 125–131. ACM, 2004

    2004

  67. [75]

    R. Mahara. Existence of EFX for two additive valuations. Discret. Appl. Math. , 340: 115–122, 2023. 23

    2023

  68. [76]

    Markakis and C

    E. Markakis and C. Santorinaios. Improved EFX approximation guarantees under ordinal- based assumptions. In AAMAS, pages 591–599. ACM, 2023

    2023

  69. [77]

    Plaut and T

    B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 34(2):1039–1068, 2020

    2020

  70. [78]

    Steinhaus

    H. Steinhaus. The problem of fair division. Econometrica, 16(1):101–104, 1948

    1948

  71. [79]

    Stromquist

    W. Stromquist. How to cut a cake fairly. The American Mathematical Monthly , 87(8): 640–644, 1980

    1980

  72. [80]

    A. Sun, B. Chen, and X. V. Doan. Fairness criteria for allocating indivisible chores: con- nections and efficiencies. Autonomous Agents and Multi-Agent Systems , 37(1):39, 2023

    2023

  73. [81]

    Zhang and V

    H. Zhang and V. Conitzer. Learning the valuations of a k-demand agent. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 11066–11075. PMLR, 2020

    2020

  74. [82]

    Zhou and X

    S. Zhou and X. Wu. Approximately EFX allocations for indivisible chores. Artif. Intell. , 326:104037, 2024. A Missing Proofs of Section 3 Theorem 1 (Separation between EFX and PMMS for Three Agents). There exists an instance with three agents, one with an additive valuation an...

    2024

Pith tools

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