Pith. sign in

REVIEW 3 major objections 4 minor 44 references

Existence of 2-EFX Allocations of Chores

T0 review · 3 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 This paper proves that every chore division instance with additive disutilities admits a 2-EFX allocation, improving the universal guarantee from 4-EFX.

desk verdict 2-EFX for all additive chores is a genuine advance, but the main theorem leans on Mahara's price-EF1 existence result as an unproved black box and the algorithm has a few fixable presentation bugs. read the letter →

arxiv 2507.19461 v1 pith:6ELT2HEF submitted 2025-07-25 cs.GT

Jugal Garg , Aniket Murhekar This is my paper · ORCID
classification cs.GT MSC 91B32
keywords fairdivisionchoresEFX2-EFXadditivedisutilitieschoreswapsprice-EF1Paretooptimality
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 proves that for any set of indivisible chores and any additive disutility functions, there is an allocation in which no agent would still envy another agent's bundle after removing any one of their own chores by more than a factor of two (a 2-EFX allocation). This improves the previously known universal guarantee of 4-EFX and matches the best approximations previously known only in restricted cases. The proof works through a general two-step framework: start from an allocation that is envy-free up to one chore and Pareto-optimal, then perform at most 2n local swaps between envious and envied agents in a carefully chosen round-robin order. The framework also reproduces, with simpler proofs, the known 4-EFX guarantee, the (2-1/k)-EFX result for bivalued disutilities, and exact EFX when the number of chores is at most twice the number of agents.

What carries the argument

The load-bearing object is the $\lambda$-EFX-friendly allocation: a partition of agents into $N_0$ and $N_H$ where agents in $N_0$ already satisfy the $\lambda$-EFX inequalities, and every agent in $N_H$ has one high-disutility chore $j_i$ such that, for all agents, the bundle $S_i = X_i \setminus \{j_i\}$ has disutility at most $(\lambda-1)$ times the disutility of any high chore or any $N_0$ bundle. The paper proves that any such allocation can be converted to a $\lambda$-EFX allocation by two phases of chore swaps: first redistribute the high chores $H = \{j_i : i \in N_H\}$ among $N_H$ in a round-robin order from least to most disliked, then process agents in the same order, letting an envious agent $i$ swap its high chore for the entire bundle of the agent it envies most. The round-robin choice of $j_i$ ensures that once an agent is $\lambda$-EFX, later swaps cannot make it envious again; each swap also preserves the friendly conditions, so at most $2n$ operations suffice. A weaker variant, weakly $\lambda$-EFX-friendly, relaxes the high-chore condition using low-disutility chores already present in each bundle and yields the improved bounds for bivalued instances and for instances with at most twice as many chores as agents.

What would settle it

A concrete counterexample would be an explicit additive chore instance, such as one with 4 agents and 5 chores, in which every allocation has some agent $i$ and chore $j \in X_i$ with $d_i(X_i\setminus\{j\}) > 2 d_i(X_h)$ for some other agent $h$; an exhaustive enumeration of all allocations of such an instance would settle whether the theorem holds.

Watch

Extended reading notes

Core claim

The central claim is that for every chore division instance with additive disutility functions, a 2-EFX allocation exists: no agent envies another agent's bundle by more than a factor of two after removing any single chore from her own bundle. The proof obtains such an allocation by combining a recently established starting point with a new conversion algorithm. The starting point is an integral allocation $X$ and prices $p$ such that each agent receives only chores minimizing the disutility-to-price ratio and the allocation is price-EF1, meaning that after discarding the highest-priced chore of any bundle, its price is no larger than that of any other bundle; such an allocation implies both EF1 and Pareto-optimality. For $\lambda = 2$, scaling each agent's disutilities to prices turns this starting allocation into a 2-EFX-friendly allocation, and the paper's swap algorithm converts it into a genuinely 2-EFX allocation in at most $2n$ swaps. The same conversion argument is proved for general $\lambda$, yielding a unified framework for approximate-EFX allocations.

Load-bearing premise

The proof depends on the just-established theorem that every additive chore instance has an integral allocation that is price-EF1 and Pareto-optimal; the paper does not prove that theorem, so the 2-EFX result stands or falls with it.

Editorial extensions

If this is right

  • For every additive chore instance, the universal approximate-EFX guarantee improves from 4-EFX to 2-EFX, closing the gap to the restricted cases previously known.
  • Any polynomial-time algorithm for computing a price-EF1 and Pareto-optimal starting allocation would immediately give a polynomial-time algorithm for a constant-factor EFX allocation, because the swap phase runs in linearly many operations.
  • The framework reproduces the known 4-EFX result, the $(2-1/k)$-EFX bound for bivalued disutilities, and exact EFX when $m \le 2n$, giving a single proof for all of them.
  • Since the conversion applies to any $\lambda$-EFX-friendly allocation, the search for better approximations reduces to constructing friendlier starting allocations, not to designing instance-specific swap rules.

Reading between the lines

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

  • Editorial inference: the swap phase is so generic that the bottleneck for polynomial-time constant-factor EFX is exactly the construction of the price-EF1 starting allocation; progress on that single subproblem would settle the algorithmic question for all constants.
  • Editorial inference: the round-robin ordering only needs the monotonicity that earlier pickers receive chores they dislike at least as little as later pickers, so weighted or adaptive ordering rules might extend the framework to goods, weighted agents, or stronger fairness notions in restricted domains.
  • Editorial inference: because the friendly conditions are stated per agent and only compare each agent's own bundle to the bundles of others, the same conversion may compose with other market-based starting points, such as earning-restricted equilibria, to yield better factors than 2 in structured instances.
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. This paper studies approximate envy-free allocations of indivisible chores with additive disutilities. It introduces the notion of a λ-EFX-friendly allocation and proves (Theorem 3) that Algorithm 1 converts any such allocation into a λ-EFX allocation in polynomial time using at most 2n swaps. The main application starts from Mahara's recent theorem on the existence of an integral MPB allocation that is price-EF1 (and hence EF1 and PO), proves that such an allocation is 2-EFX-friendly (Lemma 3), and concludes that 2-EFX allocations always exist (Theorem 5). The same framework is used to re-derive 4-EFX for general instances, (2−1/k)-EFX for bivalued instances, and EFX when the number of chores is at most twice the number of agents. The paper closes with a discussion of open questions.

Significance. The central existence result, if correct, is a substantial improvement over the previous best-known constant-factor guarantee of 4-EFX and answers a natural open question on the existence of 2-EFX allocations. The framework is simple and algorithmic, reducing the problem to finding a λ-EFX-friendly starting allocation; this is a genuine conceptual contribution. The paper also gives streamlined proofs of several known results, which is useful for the community. At the same time, the main theorem is entirely conditional on the external result [39], and the proof of the core swap lemma has a gap in its base case. These issues are fixable in revision, but they are load-bearing.

major comments (3)
  1. [Section 4.1, Theorem 5 / Lemma 3] The main theorem is entirely dependent on Mahara's theorem [39], namely the existence of an integral MPB allocation (X,p) that is pEF1 for every additive chore instance. The paper supplies no proof or even a precise statement of this external theorem, and the cited work is a very recent preprint. If [39] turns out to establish only EF1+PO without the MPB/price-EF1 structure, Lemma 3 has no input and Theorem 5 collapses. The authors should either provide a self-contained proof of the specific consequence they need or clearly delimit the dependency and confirm the exact form of [39].
  2. [Section 3.1, Lemma 2, base case] The proof of the base case claims that agent 1 is λ-EFX in X^0 and hence 'no swap takes place in iteration 1.' The displayed inequality proves this only for h∈NH, where d1(j1)≤d1(jh) holds; for h∈N0 no bound of the form d1(j1)≤d1(X^0_h) is available. The claim is false in general: for λ=2, take N0={2}, NH={1}, d1(S1)=1, d1(j'_1)=100, and d1(X_2)=10. The allocation is 2-EFX-friendly, but agent 1 is not 2-EFX toward agent 2 because removing the disutility-1 chore from X^0_1 leaves 100 > 20 = 2·d1(X_2). The idea used for later iterations (allow a swap and then prove the invariant) appears to repair this, but as written the induction in Lemma 2 and the proof of Theorem 3 have a gap.
  3. [Section 3.2, Theorem 4] The proof of Theorem 4 is only a sketch. It states that invariants (i)–(iii) of Lemma 2 hold with a weaker condition on \hat d_i(X_i^i) after 'carefully revisiting' the proof, but it does not supply the modified invariant or the required case analysis. This matters because Theorem 4 is the engine behind the bivalued (Theorem 7) and small-chores (Theorem 8) applications, and because the weak definition changes which quantities are controlled. The authors should give a complete proof or a sufficiently detailed proof outline that explicitly handles the base case and all cases of invariant (iii).
minor comments (4)
  1. [Algorithm 1, Lines 4–8] The pseudocode selects j_i and removes it from H' but never assigns it to X_i. As written, agents in NH are left with only S_i after Phase 1. Add an assignment such as X_i ← X_i ∪ {j_i} inside the loop.
  2. [Section 4.2, second case] In the N_L=∅ case, the sentence 'For h∈NH, it implies d_i(Y_i)≤4·d_i(Z_k)=4·d_i(j_k)' should refer to j_h, not j_k.
  3. [Theorem 8] The constructed allocation Y does not satisfy the condition S_i∩L_i≠∅ of Definition 4 for agents with |Y_i|=1 (where S_i=∅), and it can also fail for agents in [r] when an earlier phase-1 pick removes their global-minimum chore. The condition should be stated for agents with |S_i|>0, with single-chore agents handled separately, or the proof should verify a weaker condition.
  4. [Definition 1 and surrounding text] The notation p^{-X}(X_i) is used before it is defined; it should either be defined at first use or replaced by \hat p(X_i), which is introduced earlier in the same section.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central 2-EFX result reduces to Mahara's external pEF1+MPB theorem, not to any input fitted or renamed by this paper.

full rationale

The central derivation chain is: Mahara's theorem [39] supplies an integral MPB allocation (X,p) that is pEF1 (external, by a different author, not by the present authors). Lemma 3 verifies, using only the MPB inequality d_ij ≥ p_j for j not in X_i and the pEF1 inequality p(S_i) ≤ ρ, that this allocation is 2-EFX-friendly; the proof is a direct calculation with the four listed observations and does not invoke the 2-EFX conclusion it aims to establish. Theorem 3 and Lemma 2 then show that Algorithm 1 converts any λ-EFX-friendly allocation into a λ-EFX allocation via at most 2n swaps; this is an independent algorithmic argument whose proof does not use the target 2-EFX statement as an assumption. The uses of self-citations ([30], [21,25]) are for benchmarks, for the ER-equilibrium existence theorem used in the separate re-derivation of 4-EFX, and for bivalued pEF1 algorithms; none of these is needed for Theorem 5. The absence of a proof of Mahara's theorem in this paper is a verification or correctness gap, not circularity: the cited theorem has stated assumptions (additive disutilities) that do not include the target result and is external to the authors' own prior work. No fitted input is renamed as a prediction, and no uniqueness or existence theorem is imported from the authors' own prior work to forbid alternatives. The paper's framework is self-contained once the external pEF1+MPB starting point is granted.

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

The central 2-EFX theorem uses no fitted parameters and no new postulated entities. The only load-bearing external input is Mahara's theorem, which is cited but not proved here; it is treated as a domain-level axiom. The other axioms are standard for the model.

assumptions (3)
  • domain assumption Mahara's theorem: for any additive chore division instance, there exists an integral MPB allocation (X,p) that is pEF1, hence EF1 and PO.
    Loaded in Lemma 3 as the starting point for the 2-EFX-friendly allocation. The main theorem is conditional on this external result (cited as [39], arXiv:2507.09544), whose proof is not included here.
  • domain assumption Positive additive disutilities d_ij > 0 for all agents i and chores j.
    Used throughout, e.g., to infer d_i(X_h) >= d_i(j_h) from j_h in X_h and to allow per-agent scaling of disutilities to prices.
  • domain assumption Existence of earning-restricted equilibria under P_i e_i <= P_j c_j (Theorem 2 of [30]).
    Used in the 4-EFX reproduction in Section 4.2, not in the main 2-EFX theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Existence of 2-EFX Allocations of Chores." pith.science (2026). https://pith.science/paper/6ELT2HEF

@misc{pith2026250719461,
  author       = {Pith},
  title        = {Pith review of: Existence of 2-EFX Allocations of Chores},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6ELT2HEF}},
  note         = {Machine review of arXiv:2507.19461}
}
abstract

We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of $4$-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of $2$-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) $2$-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) $4$-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 36 canonical work pages

  1. [30]

    Constant-factor EFX exists for chores

    Jugal Garg, Aniket Murhekar, and John Qin. Constant-factor EFX exists for chores. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC ’25, page 1580–1589, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400715105. doi: 10.1145/3717823.3718305. URL https://doi.org/10.1145/3717823. 3718305. 18

    arXiv 2025

  2. [39]

    Existence of fair and efficient allocation of indivisible chores, 2025

    Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores, 2025. URL https://arxiv.org/abs/2507.09544

    arXiv 2025

  3. [1]

    Approximate EFX and exact tEFX allocations for indivisible chores: Improved algorithms, 2024

    Mahyar Afshinmehr, Matin Ansaripour, Alireza Danaei, and Kurt Mehlhorn. Approximate EFX and exact tEFX allocations for indivisible chores: Improved algorithms, 2024. URL https://arxiv.org/abs/2410.18655

    arXiv 2024

  4. [2]

    EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number

    Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle number. In Proceedings of the 24th ACM Conference on Economics and Computation (EC) , page 61, 2023. 16

    work page 2023

  5. [3]

    Voudouris, and Xiaowei Wu

    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

    work page 2023

  6. [4]

    Pushing the frontier on approximate EFX allocations

    Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate EFX allocations. In Conf. Economics and Computation (EC) , 2024

    work page 2024

  7. [5]

    Fair allocation of indivisible goods and chores

    Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), page 53–59, 2019

    work page 2019

  8. [6]

    Algorithmic fair allocation of indivisible items: a survey and new questions

    Haris Aziz, Bo Li, Herv´ e Moulin, and Xiaowei Wu. Algorithmic fair allocation of indivisible items: a survey and new questions. SIGecom Exch., 20(1):24–40, 2022

    work page 2022

Show all 44 references
  1. [7]

    Fair allocation of two types of chores

    Haris Aziz, Jeremy Lindsay, Angus Ritossa, and Mashbat Suzuki. Fair allocation of two types of chores. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), page 143–151, 2023

    2023

  2. [8]

    On the proximity of markets with integral equilibria

    Siddharth Barman and Sanath Krishnamurthy. On the proximity of markets with integral equilibria. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 1748–1755, 2019

    2019

  3. [9]

    Finding fair and efficient allocations

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018

    2018

  4. [10]

    Greedy algorithms for maximizing Nash social welfare

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy algorithms for maximizing Nash social welfare. In Proceedings of the 17th International Conference on Au- tonomous Agents and MultiAgent Systems (AAMAS) , page 7–13, 2018

    2018

  5. [11]

    Parameterized guarantees for almost envy-free allocations

    Siddharth Barman, Debajyoti Kar, and Shraddha Pathak. Parameterized guarantees for almost envy-free allocations. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , page 151–159, 2024

    2024

  6. [12]

    Almost full EFX exists for four agents

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

    2022

  7. [13]

    Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On approximate envy-freeness for indi- visible chores and mixed resources. CoRR, abs/2012.06788, 2020. URL https://arxiv.org/ abs/2012.06788

    2012 arXiv

  8. [14]

    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. In Proceedings of the 17th ACM Conference on Economics and Computation (EC) , page 305–322, 2016

    2016

  9. [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. In Proceedings of the 2019 ACM Conference on Economics and Computation (EC) , page 527–545, 2019

    2019

  10. [16]

    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 Trans. Econ. Comput., 7(3), sep 2019. ISSN 2167-8375. 17

    2019

  11. [17]

    A little charity guarantees almost envy-freeness

    Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. InProceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , page 2658–2672, 2020

    2020

  12. [18]

    EFX exists for three agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. J. ACM, 2024

    2024

  13. [19]

    On the pursuit of efx for chores: non-existence and approximations

    Vasilis Christoforidis and Christodoulos Santorinaios. On the pursuit of efx for chores: non-existence and approximations. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence , IJCAI ’24, 2024. ISBN 978-1-956792-04-1. doi: 10.24963/ijca...

    2024 doi

  14. [20]

    On the pursuit of EFX for chores: Non-existence and approximations

    Vasilis Christoforidis and Christodoulos Santorinaios. On the pursuit of EFX for chores: Non-existence and approximations. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, (IJCAI) , pages 2713–2721, 2024

    2024

  15. [21]

    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. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2022

    2022

  16. [22]

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

    1967

  17. [23]

    Computing fair and efficient allocations with few utility values

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

    2023

  18. [24]

    Computing Pareto-optimal and almost envy-free allocations of indivisible goods

    Jugal Garg and Aniket Murhekar. Computing Pareto-optimal and almost envy-free allocations of indivisible goods. J. Artif. Int. Res. , 2024

    2024

  19. [25]

    Fair and efficient allocations of chores un- der bivalued preferences

    Jugal Garg, Aniket Murhekar, and John Qin. Fair and efficient allocations of chores un- der bivalued preferences. Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5043–5050, 2022

    2022

  20. [26]

    Satiation in Fisher markets and approximation of Nash social welfare

    Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Satiation in Fisher markets and approximation of Nash social welfare. Mathematics of Operations Research, 2023

    2023

  21. [27]

    New algorithms for the fair and efficient alloca- tion of indivisible chores

    Jugal Garg, Aniket Murhekar, and John Qin. New algorithms for the fair and efficient alloca- tion of indivisible chores. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI) , pages 2710–2718, 2023

    2023

  22. [28]

    Weighted EF1 and PO allocations with few types of agents or chores

    Jugal Garg, Aniket Murhekar, and John Qin. Weighted EF1 and PO allocations with few types of agents or chores. Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024

    2024

  23. [29]

    Constant-factor efx exists for chores, 2024

    Jugal Garg, Aniket Murhekar, and John Qin. Constant-factor efx exists for chores, 2024. URL https://arxiv.org/abs/2407.03318

    2024 arXiv

  24. [31]

    Fair allocation of a multiset of indivisible items

    Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy. Fair allocation of a multiset of indivisible items. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2022

    2022

  25. [32]

    EFX allocations for indivisible chores: Matching-based approach

    Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto. EFX allocations for indivisible chores: Matching-based approach. In Algorithmic Game Theory (SAGT) , pages 257–270, 2023

    2023

  26. [33]

    APX-hardness of maximizing Nash social welfare with indivisible items

    Euiwoong Lee. APX-hardness of maximizing Nash social welfare with indivisible items. In- formation Processing Letters, 122, 07 2015

    2015

  27. [34]

    Almost (weighted) proportional allocations for indivisible chores

    Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In Proceedings of the ACM Web Conference (WWW) 2022 , page 122–131, 2022

    2022

  28. [35]

    Approximately efx and po allocations for bivalued chores, 2025

    Zehan Lin, Xiaowei Wu, and Shengwei Zhou. Approximately efx and po allocations for bivalued chores, 2025. URL https://arxiv.org/abs/2501.04550

    2025 arXiv

  29. [36]

    Mixed fair division: A survey

    Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) , volume 38, pages 22641–22649, 2024

    2024

  30. [37]

    Extension of additive valuations to general valuations on the existence of EFX

    Ryoga Mahara. Extension of additive valuations to general valuations on the existence of EFX. In 29th Annual European Symposium on Algorithms (ESA) , 2021

    2021

  31. [38]

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

    Ryoga Mahara. A polynomial-time algorithm for fair and efficient allocation with a fixed number of agents, 2024. URL https://arxiv.org/abs/2411.01810

    2024 arXiv

  32. [40]

    Mas-Colell, M.D

    A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995

    1995

  33. [41]

    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

    2020

  34. [42]

    Procaccia

    Ariel D. Procaccia. Technical perspective: An answer to fair division’s most enigmatic question. Commun. ACM, 63(4):118, 2020

    2020

  35. [43]

    V., Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma

    Vishwa Prakash H. V., Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX exists for three types of agents, 2024. URL https://arxiv.org/abs/2410.13580

    2024 arXiv

  36. [44]

    Approximately EFX allocations for indivisible chores

    Shengwei Zhou and Xiaowei Wu. Approximately EFX allocations for indivisible chores. Artif. Intell., 326:104037, 2024. 19

    2024

Pith tools

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