REVIEW 3 major objections 4 minor 5 references
On the existence of EFX allocations for goods
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read EFX allocations always exist when at most two agents have arbitrary set-monotonic valuations.
desk verdict A novel and plausible EFX existence theorem, but the general induction in the main proof is deferred to 'similar arguments' and the paper is not yet fully proved. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is a staged allocation algorithm that singles out one potentially 'hard' agent (Agent 1) and repeatedly enlarges that agent's bundle by one good. At each stage, the remaining bundles are chosen as best bundles of a prescribed size from the leftover goods, and the size-monotonicity of all but two agents guarantees that no two of those remaining agents envy each other up to one good. The argument splits into two cases — whether Agent 1 receives the chosen best set or the fallback set — and either terminates in an EFX allocation or produces a new allocation with a strictly larger bundle for Agent 1. Since bundle sizes are bounded, the process must stop, and the stopping condition forces EFX. A separate observation (Observation 2.2) allows the proof to assume strict valuations, claiming that an EFX allocation at a strict perturbation is also EFX at the original weak profile.
What would settle it
Exhibit any instance with m > n goods, two agents with arbitrary set-monotonic valuations, and the remaining n − 2 agents with size-monotonic valuations in which no EFX allocation exists; such an instance would directly contradict the theorem.
Extended reading notes
Core claim
The central claim is Theorem 3.3: for m > n goods and n agents, if n − 2 agents have size-monotonic valuations (larger bundles are always at least as valuable) and the remaining two agents have arbitrary set-monotonic valuations, then an EFX allocation exists. The theorem actually holds under weaker local conditions: the size-monotonic agents only need their monotonicity on a specific interval of bundle sizes determined by floor((m − 1)/(n − 1)). The proof constructs the allocation explicitly through an iterative process, and the final step shows that once the singled-out agent's bundle reaches size c while all other bundles have size c or c + 1, the allocation must be EFX.
Load-bearing premise
The proof assumes that any weak valuation profile can be perturbed into a strict one without breaking the required size-monotonicity conditions, so that the allocation found for the strict profile carries back to the original profile.
Editorial extensions
If this is right
- If the theorem is correct, EFX existence is now established for any number of agents whenever the valuation profile has at most two 'wild' agents, including profiles where every agent's valuation is distinct.
- The proof yields an EFX allocation for three agents with one arbitrary set-monotonic agent and two size-monotonic agents, a case not covered by earlier MMS-feasibility results, and it is independent of those results.
- The weakened Theorem 4.2 shows the result survives even when the two arbitrary agents are only required to be set-monotonic on a bounded interval of bundle sizes, so the construction works under conditions much weaker than the headline assumptions.
- The same techniques provide a new existence proof for the n = 2 case, different from the known argument, which the paper reports helped shape the general proof.
Reading between the lines
- A natural next target is reducing the number of non-size-monotonic agents from two to one; the iterative structure here suggests the bottleneck lies in the comparison between the two exceptional agents, not between the exceptions and the size-monotonic majority.
- The local-monotonicity weakening in Theorem 4.2 hints that full set-monotonicity is far stronger than necessary; a testable extension is whether the same construction works when the size-monotonic agents satisfy their conditions on intervals that depend on the current stage rather than on the global floor((m − 1)/(n − 1)).
- If the construction turns out to be computationally efficient, it could serve as a practical fair-division protocol for settings such as course allocation, where most participants have cardinality-based preferences but a few have idiosyncratic tastes.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the existence of envy-free-up-to-any-good (EFX) allocations for indivisible goods under general monotone valuations. The main claim is that an EFX allocation always exists when two agents have arbitrary set-monotonic valuation functions and all remaining agents have size-monotonic valuation functions. The proof is based on an iterative construction: starting from a carefully chosen allocation, if the current allocation is not EFX, the authors enlarge the bundle of a distinguished agent (Agent 1) by one good while preserving EFX among the remaining agents, and they argue that this process must terminate with an EFX allocation. Theorems 3.2 and 3.3 state weaker sufficient conditions in terms of local size-monotonicity, and the appendix contains the proofs.
Significance. If the proof is completed, this is a notable contribution to the fair-division literature. It goes beyond known existence results for EFX under general valuations, which are limited to identical valuations, two agents, or restricted classes of additive valuations. The weaker local conditions in Theorems 3.2 and 3.3 are also interesting and suggest that the full force of size monotonicity is not needed. The paper is self-contained and does not rely on unproved external results; the case-by-case verification of the constructed allocations is a strength. However, the central proof has an induction step that is only sketched, so the result as written is not fully established.
major comments (3)
- [Appendix A.2, proof of Theorem 3.3] The induction step from X^2 to X^3 and to general X^c is not fully specified. After constructing X^2 explicitly, the proof says 'Using similar arguments as before' and 'defined in a similar way as before' for c >= 3, without defining the sets G_{c-1}, H_{c-1}, W_c, Y_c, or the allocation rule for agents 3..n at step c. In particular, the size accounting m - c = (n-1) * floor((m-c)/(n-1)) + r_c is not stated for general c, and the proof that the constructed allocation satisfies properties (i)-(iv) listed before the final contradiction is omitted. The final argument that max(X^{c-1}_N) = c+1 and that X^c_1 is not envied by Agent 1 depends on these properties. As written, the proof of the main theorem is therefore incomplete.
- [Observation 2.2 and its use] The proof reduces to strict valuation profiles 'in view of Observation 2.2', but the paper never proves that an arbitrary weak profile satisfying the monotonicity conditions of Theorems 3.2 and 3.3 can be perturbed into a strict profile that (a) refines the weak order in the sense of Observation 2.2 and (b) still satisfies the same local size- and set-monotonicity conditions. This is a standard perturbation argument, but it is load-bearing because the theorems are stated for weak set-monotonic and size-monotonic valuations. The authors should either state and prove this lemma or explain why the constructed allocations remain EFX for weak profiles directly.
- [Appendix A.2, application of Theorem 3.2 to subproblems] The proof asserts that the construction for agents {2,...,n} in X^1 (and similarly for X^2, X^3, ...) 'satisfies the conditions of Theorem 3.2' and therefore inherits EFX among those agents. However, the distinguished agent (Agent 2) in the subproblem chooses a best size-ℓ bundle from E \ W_1, not from all of E as in the proof of Theorem 3.2. The same issue recurs at later steps. The proof should explicitly verify that the EFX arguments of Theorem 3.2 go through when the special agent's choices are restricted to the complement of Agent 1's bundle; this is likely true but is not shown.
minor comments (4)
- [Theorem 3.3 and elsewhere] The notation 'floor(m-1/n-1)' is ambiguous; it should be written as \left\lfloor\frac{m-1}{n-1}\right\rfloor in the statements of Theorems 3.3, 4.2, and in the appendix.
- [Footnotes 7 and 8] The convention 'n+1 ≡ 2' for r=0 is confusing. It would be clearer to state that when r=0, the range '3 <= i <= n-r+1' is empty (so all agents 3..n receive the larger bundle size).
- [Appendix A.1, proof of Theorem 3.2] In the final paragraph of the proof, the phrase 'in particular, by [ℓ-1, ℓ]-set monotonicity' is misleading: the inequality for the case |X_j \ {x_j}| = ℓ-1 follows from [ℓ, ℓ+1]-size monotonicity (comparing X_i of size ℓ+1 with X_j of size ℓ) together with strict set monotonicity (comparing X_j with X_j \ {x_j}), not from [ℓ-1, ℓ]-set monotonicity.
- [Introduction, Section 1.1] The phrase 'there is no envy in terms of (or "with respect to") EFX between any two agents i, j ∈ {2, ..., n}' is awkward and should be rephrased, e.g., 'the allocation is EFX for the subprofile of agents 2,...,n'.
Circularity Check
No significant circularity: the proof is a self-contained constructive derivation; cited external theorems are contextual and the internal Theorem 3.2 is reused as a proven subroutine, not as an input that assumes the conclusion.
full rationale
The derivation chain in this paper does not exhibit circularity under the requested standards. The main constructive proof of Theorem 3.3 proceeds by an explicit iterative allocation process, and the only internal theorem it invokes is the paper's own Theorem 3.2, whose proof is fully provided in Appendix A.1. That invocation is not circular: Theorem 3.2 is proved independently for smaller agent sets, and the proof of Theorem 3.3 explicitly verifies that the restricted profiles satisfy the hypotheses before applying it. There are no fitted parameters, no normalization choices that secretly encode the conclusion, and no self-citations used as load-bearing evidence for the central claim; the references to Plaut and Roughgarden, Akrami et al., Mahara, and HV et al. are used only to position the contribution. Observation 2.2, which reduces weak profiles to strict profiles, is a standard order-preservation argument and does not assume the target result. The reader's concerns about the 'similar arguments' in the induction step and the 'n+1 ≡ 2' convention are matters of proof completeness or exposition, not circularity: even if the induction is incompletely written, the claimed steps are not shown to be equivalent to their inputs by definition. Accordingly, the appropriate finding is no significant circularity, with score 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Valuation functions map subsets of goods to real numbers and are set monotonic: v(X) ≤ v(Y) for X ⊆ Y.
- domain assumption Size monotonic valuations satisfy v(X) ≤ v(Y) whenever |X| < |Y| (at least on the relevant size intervals stated in Theorems 3.2 and 3.3).
- domain assumption For every weak valuation profile there exists a strict valuation profile respecting all strict inequalities and preserving the (local) monotonicity conditions (Observation 2.2).
Cite this review
Pith. "Pith review of On the existence of EFX allocations for goods." pith.science (2026). https://pith.science/paper/OAB3AMZ5
@misc{pith2026250709600,
author = {Pith},
title = {Pith review of: On the existence of EFX allocations for goods},
year = {2026},
howpublished = {\url{https://pith.science/paper/OAB3AMZ5}},
note = {Machine review of arXiv:2507.09600}
}
abstract
We consider a set $E$ of $m$ indivisible goods and a set $N$ consisting of $n \geq 2$ agents. The paper shows that if two agents have \textit{arbitrary} set monotonic valuation functions and the remaining agents have size monotonic valuation functions, then EFX allocations always exist.
Reference graph
Works this paper leans on
-
[1]
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, pages 61–61, 2023. 14
work page 2023
-
[2]
The unreasonable fairness of maximum nash welfare
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 (TEAC), 7(3):1–32, 2019
work page 2019
-
[3]
EFX Exists for Three Types of Agents
Vishwa Prakash HV , Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. Efx exists for three types of agents. arXiv preprint arXiv:2410.13580, 2024
work page Pith review arXiv 2024
-
[4]
Existence of efx for two additive valuations
Ryoga Mahara. Existence of efx for two additive valuations. Discrete Applied Mathematics, 340: 115–122, 2023
work page 2023
-
[5]
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. 15
work page 2020
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.