{"id":"398b9774-17a3-42fb-b768-8ba786a51bca","arxiv_id":"2412.00254","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EF2X allocations are guaranteed to exist for any four-agent fair division instance with cancelable valuations, and can be computed in pseudopolynomial time.","lead":"This paper proves that four agents with cancelable valuations, a class that generalizes additive valuations, always have an EF2X fair allocation, and gives an algorithm to find one. The result settles an open question for a relaxation of the central EFX problem and introduces techniques that may be useful for the harder EFX question.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Pseudo-polynomial runtime claim in Theorem 3.1 lacks a positive minimum-gap bound for real-valued valuations; the existence proof itself appears internally consistent.","rationale":"The reader's weakest-assumption analysis identified the same load-bearing concern: the pseudo-polynomial runtime proof relies on a positive minimum gap δ between distinct bundle values, which is not guaranteed for real-valued valuations as defined in Section 2. I examined the existence argument (Theorems 3.26--3.43 and supporting lemmas) and found no internal inconsistency; the case analysis is lengthy but the key steps—potential-strict-increase cycles, swap-optimization, PR-based reallocation, and Hall's theorem applications—appear logically coherent. The main gap is therefore in the computational claim, not the existence claim. The paper could fix this by adding an integrality/rationality assumption to Theorem 3.1, or by weakening the runtime guarantee to finite termination. Since the reader's CONDITIONAL verdict already reflects this, no change to the verdict is needed. The secondary 'not hard to verify' point about a polynomial number of PR executions per edge is also worth formalizing, but it is likely fixable and less fundamental than the missing minimum-gap bound.","tokens_in":46211,"tokens_out":20778,"duration_ms":180280,"concrete_test":"Restate Theorem 3.1 assuming valuations are nonnegative integer-valued (or rational with denominator at most Q), and re-prove Theorem 3.49 with δ, Δ ≥ 1/Q^2. If the proof goes through, the computational claim requires an explicit bounded-precision/integrality assumption. Conversely, construct an additive four-agent instance where agent 1's item values are distinct numbers in [0,1] with minimum pairwise gap 2^{-2^m} and simulate the algorithm from an initial partition; if the number of strict potential increases (or PR operations) can be made Ω(2^m), then the pseudo-polynomial claim fails for real-valued inputs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem (Theorem 3.1) includes a computational guarantee: 'we can compute one in pseudo-polynomial time.' The runtime proof in Section 3.9 bounds PR steps by m·n·v(M)/δ, where δ = min_{S,T: v(S)≠v(T)} |v(S)-v(T)|, and bounds the number of cycles by a polynomial in v1(M)/Δ, where Δ is the analogous minimum gap for agent 1's valuation. These bounds are only meaningful if δ and Δ are bounded below by a quantity that is part of the pseudo-polynomial parameterization (e.g., 1 for integer valuations). However, Section 2 defines valuations as real-valued, vi: 2^M → R_{\\ge 0}, and no integrality, rationality, or bounded-precision assumption is stated. For real inputs, the set of distinct values is finite, so Δ > 0 for a non-degenerate agent 1, but Δ can be exponentially small (e.g., 2^{-2^m}), making v1(M)/Δ exponential. For degenerate valuations used in PR runs with agents 2--4, δ may be undefined or zero. Thus the stated pseudo-polynomial guarantee is not justified as written. The existence result—the main contribution—is supported by a long case analysis and appears consistent; the runtime gap does not break existence, but it means Theorem 3.1 is overclaimed unless an integrality/rationality assumption is added. A secondary, smaller gap is the sentence in Section 3.9 that 'it is not hard to verify' that each edge has a polynomial number of PR executions; this is plausible (e.g., the repeat loop in Theorem 3.33 runs at most m times) but not proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the existence and computation of EF2X allocations (envy-free up to any two goods) in discrete fair division. Its main result, Theorem 3.1, states that for every instance with four agents in which at least three agents have cancelable valuations (and one has an arbitrary monotone valuation), an EF2X allocation exists and can be computed in pseudo-polynomial time. The proof is constructive and organized as a staged algorithm: starting from an arbitrary partition, it applies a sequence of transformations (described in a flowchart with stages A, B, B1, B2, B2i, B2ii) driven by a potential function equal to agent 1's value for the first bundle. The paper also gives a secondary result, Theorem 4.1, claiming a polynomial-time algorithm for three agents with cancelable valuations.","tokens_in":46470,"tokens_out":25514,"duration_ms":209872,"significance":"If the existence proof is correct, this is a substantial advance for a central open direction in fair division. EF2X is a natural relaxation of EFX, and establishing existence for four agents under cancelable valuations—a strict generalization of additive valuations—significantly extends the frontier of known existence results. The paper introduces reusable techniques: EFkX-best bundles, swap-optimization, and partition-transformation lemmas based on the Plaut–Roughgarden local search, which may be useful for the still-open EFX problem. The central existential argument is a long case analysis that appears internally consistent; it does not rely on circular reasoning and explicitly builds on external results (e.g., cancelable valuations being MMS-feasible) rather than on the target theorem. The main weaknesses are in the computational claims: the pseudo-polynomial runtime proof is not fully justified for the stated model of real-valued valuations, and the polynomial-time three-agent construction has an under-specified initialization step.","major_comments":[{"comment":"The pseudo-polynomial runtime guarantee is not justified under the paper's stated model. Section 2 defines valuations as real-valued functions vi: 2^M → R_{\\ge 0}, with no integrality, rationality, or precision assumption. The proof in Section 3.9 defines δ = min_{S,T: v(S) ≠ v(T)} |v(S)-v(T)| for PR runs and Δ = min_{S,T: v1(S) ≠ v1(T)} |v1(S)-v1(T)| for the potential, and bounds the number of steps by m·n·v(M)/δ and the number of cycles by v1(M)/Δ. For arbitrary real inputs, δ and Δ can be arbitrarily small (e.g., 2^{-2^m}), and for degenerate valuations δ may be undefined. The paper needs an explicit assumption that valuations are integer-valued or rational with a bounded-precision input model, together with a lower bound on the minimum gap for the valuations on which PR is run. Without this, 'pseudo-polynomial' is not well-defined and the computational claim of Theorem 3.1 is overclaimed.","section":"Section 3.9, Theorem 3.49; Theorem 3.1"},{"comment":"The runtime proof asserts without proof that 'it is not hard to verify that, except running time of PR algorithm, all other operations in every edge run in polynomial time. Also, every PR algorithm runs in pseudo-polynomial time, and we will have a polynomial number of executions of PR algorithm at every edge of Figure 1.' This is load-bearing for Theorem 3.49: the number of PR invocations per edge must be bounded explicitly. While the repeat loop in Theorem 3.33 runs at most m times, other edges (e.g., the PR calls in Lemmas 3.23 and 3.25) are not accompanied by analogous bounds. The proof should either supply per-edge bounds or state and prove a general lemma bounding PR invocations.","section":"Section 3.9, final paragraph"},{"comment":"The reduction to a non-degenerate agent 1 via Corollary A.4 conflicts with the runtime analysis. Lemma A.2 constructs a perturbed valuation v'_1(S) = v1(S) + ε Σ_{g∈S} 2^j, with ε 2^{m+1} < δ, where δ is the minimum gap of v1. If the algorithm is run on v'_1, then the quantity Δ in Section 3.9 must be the minimum gap of v'_1, which can be exponentially small in m, making the bound v1(M)/Δ exponential rather than pseudo-polynomial. If, instead, the algorithm is run on the original possibly degenerate v1, strict potential increases are not guaranteed, so the termination argument fails. The paper does not specify which valuation is actually used by the algorithm or how the pseudo-polynomial bound is preserved under the perturbation.","section":"Corollary A.4 and Section 3.9"},{"comment":"The initialization of the three-agent algorithm is not justified. The text states: 'Using this modified version of the PR algorithm, we compute a partition (X1, X2) such that X1 and X2 are EFX-feasible for some distinct agents i and j, respectively.' However, the PR algorithm is run with a single valuation function v and returns a partition that is EFX-feasible for that same valuation. No argument is given for why one of the two bundles is EFX-feasible for a different agent j. This step is essential for the resulting partition to be in stage B (Definition 4.2), and therefore Theorem 4.1's proof is incomplete as written.","section":"Section 4 (Theorem 4.1)"}],"minor_comments":[{"comment":"In the restated conditions of stage B2i, the text says 'We say partition X is in stage B2ii if all the following hold', but this should read 'stage B2i'.","section":"Section 3.7"},{"comment":"The sentence 'Since there are finitely many bundles (in fact, 2^|M|)' is imprecise: a partition contains only four bundles, while 2^|M| is the number of all possible bundles (subsets). The intended meaning is clear but the wording should be corrected.","section":"Section 3.9, Theorem 3.49"},{"comment":"The step 'Hence, agent 1 EFX-envies X'_4 relative to bundle X'_1' relies on the minimality of X'_2 and X'_3, which ensures that agent 1 does not EFX-envy those two bundles relative to X'_1. This minimality is used implicitly but never stated; adding a sentence would make the argument clearer.","section":"Lemma 3.21"},{"comment":"The notation EF2XBest_i(X) is used in Observation 3.15 and elsewhere, but it is not formally defined in the preliminaries (only EFXBest_i is defined). The authors should add a definition of EF2X-best bundles or state explicitly that it is the natural analogue.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"This is a serious and technically dense contribution. The central existence proof for four agents appears internally consistent on close reading, though I did not mechanically verify every lemma; the staged structure and the extensive use of lemmas with explicit preconditions give me moderate confidence. The main obstacles are the computational claims: the pseudo-polynomial runtime proof lacks an integrality/rationality assumption and the 'polynomial number of PR executions per edge' is asserted rather than proven; the non-degeneracy perturbation also interacts with the runtime bound in an unresolved way. The three-agent result is more sketchy and needs a fix for the initial partition construction. These issues are fixable within the manuscript's scope, so I recommend major revision rather than rejection. The paper is likely to be of interest to the EC/SODA/AGT community if the runtime and initialization gaps are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main takeaway: this is a real result. It proves EF2X exists for four agents with cancelable valuations, and only needs three of them cancelable. That is the first guarantee of this kind beyond very restricted additive classes, so it advances a question people care about. The proof is long, but it has a clear stage structure, and the case analysis is internally consistent as far as I can tell. The new techniques (EFkX-best bundles, swap-optimization) are genuinely useful and likely to outlive this application.\n\nWhere it gets soft: the pseudo-polynomial runtime claim in Theorem 3.1 is not justified as written. Section 3.9 defines δ and Δ as minimum gaps between distinct bundle values, then bounds PR iterations and cycle counts by v(M)/δ and v1(M)/Δ. But valuations are defined as real-valued in Section 2, and no integrality or bounded-precision assumption is stated. For real inputs those gaps can be exponentially small, so the bound is not pseudo-polynomial. This is a real flaw in the computational claim, but it does not touch the existence argument, which is the main contribution. The fix is straightforward: either state a rationality/integrality assumption or drop the pseudo-polynomial claim and say the algorithm terminates in finite time (which follows since potential is strictly increasing over a finite set). The 'not hard to verify' step about a polynomial number of PR executions per edge is minor; if the stage graph and the per-transition bounds check out, that will close.\n\nI also want to note the paper cites the relevant recent work, including the parallel HV et al. result, and it doesn't oversell by claiming EFX. The 3-agent polynomial-time algorithm is a nice secondary result, though it depends on the same modified PR lemma, which is proven.\n\nBottom line: this deserves a serious referee. The existence theorem is likely correct and is a meaningful step in a notoriously hard area. The runtime claim needs a fix before publication, but that's a revision, not a rejection. If I were the editor, I'd send it out and expect the authors to add an integrality assumption or weaken the theorem statement.","headline":"A genuine first EF2X guarantee for four agents with cancelable valuations; the existence proof looks solid but the pseudo-polynomial runtime claim needs an integrality assumption.","tokens_in":47051,"tokens_out":1926,"would_cite":true,"duration_ms":18764,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"An EF2X allocation is guaranteed for every four-agent instance with cancelable valuations, and it can be computed in pseudo-polynomial time.","keywords":["EF2X","cancelable valuations","fair division","indivisible goods","envy-free up to any two goods","four agents","pseudo-polynomial algorithm","EFX"],"falsifier":"A direct counterexample would be a four-agent instance with three cancelable valuations, one arbitrary monotone valuation, and a finite set of goods for which every complete allocation leaves some agent EF2X-envious of another; if such an instance exists, Theorem 3.1 is false. Short of that, one can test the runtime claim by checking whether the algorithm's strict potential increases can be made to grow faster than a polynomial in the input size on a family of small additive instances.","tokens_in":45962,"feed_emoji":"🤝","tokens_out":6750,"duration_ms":63777,"temperature":0.7,"pith_summary":"This paper proves that EF2X allocations always exist for instances with four agents, any number of indivisible goods, and cancelable valuations—a class that strictly contains additive valuations. The proof is constructive, following an algorithm that starts from an arbitrary partition and modifies it through a sequence of stages until each bundle is EF2X-feasible for the agent it is assigned to. A potential function based on agent 1's value for bundle 1 is shown to increase strictly on every progress step, which yields a pseudo-polynomial runtime. If the result stands, it closes the four-agent question for EF2X, a case that had remained open even for additive valuations, and it leaves the analogous EFX question as the next target.","feed_headline":"EF2X is guaranteed for four agents","feed_subtitle":"A staged algorithm always removes envy up to any two goods, even with cancelable valuations.","key_machinery":"The load-bearing mechanism is a staged local-search algorithm on partitions of the good set. The algorithm uses EFkX-best bundles, meaning bundles that maximize the value after removing k of an agent's least-liked goods, plus a swap-optimization subroutine that exchanges goods between two bundles whenever both associated agents weakly prefer the other good. It also uses the Plaut-Roughgarden algorithm as a subroutine to make all bundles EFX-feasible for agent 1. The potential φ(X)=v1(X1) never decreases, and every transition that loops back to an in-stage partition strictly increases it, which bounds the number of strict increases and gives the pseudo-polynomial runtime.","core_discovery":"The central claim is Theorem 3.1: for every instance with four agents, three of whom have cancelable valuations and one arbitrary monotone valuation, and any number of goods, there exists an EF2X allocation that can be computed in pseudo-polynomial time. The algorithm produces a full allocation, not a partial one, and often the returned allocation is actually EFX rather than merely EF2X. As a secondary contribution, the same techniques give a polynomial-time algorithm for EF2X with three cancelable agents.","pith_inferences":["Editorial inference: if one restricts to rational or integer valuations, the δ-based potential bound becomes a genuine pseudo-polynomial guarantee; the real-valued statement needs a small additional hypothesis about the valuation gap.","Editorial inference: the stage framework identifies the final matching step as the main obstruction to four-agent EFX, and replacing the EF2X matching condition with an EFX one would settle that open problem.","Editorial inference: a testable extension is to run the same stage decomposition with a potential that tracks a different agent or a different bundle, which may make the approach scale beyond four agents.","Editorial inference: because cancelable valuations contain additive ones, the result immediately covers all additive four-agent instances and suggests that EF2X may hold for any fixed number of agents under cancelability."],"forward_implications":["For four agents, EF2X is guaranteed to exist in full generality, with only three of the four agents required to have cancelable valuations.","The algorithm's output is a completely allocated EF2X partition, so no goods are donated or thrown away.","The same constructive machinery gives a polynomial-time EF2X algorithm for three agents, where known EFX algorithms are only pseudo-polynomial.","Because the computed allocation is often EFX, the proof doubles as partial progress toward the still-open EFX existence question for four agents.","The result highlights EF2X as a meaningful relaxation that can be certified even when EFX is not yet available."],"supporting_citations":[{"why":"Proved EFX existence for three agents, which is the base result the paper extends and the source of the four-agent open question.","marker":"Chaudhury et al. [2024]"},{"why":"Introduced cancelable valuations and gave EFX guarantees for nice-cancelable instances, supplying the valuation class studied here.","marker":"Berger et al. [2022]"},{"why":"Introduced EF2X and proved existence for restricted additive valuations, giving the notion and the prior restricted result.","marker":"Akrami et al. [2022]"},{"why":"Proved EF2X existence for (∞,1)-bounded valuations, the most recent restricted case the paper generalizes.","marker":"Kaviani et al. [2024]"},{"why":"Supplies the PR algorithm used as a subroutine to make all bundles EFX-feasible for agent 1.","marker":"Plaut and Roughgarden [2020]"},{"why":"Provides the non-degeneracy perturbation argument and the MMS-feasible framework used to justify the valuation assumptions.","marker":"Akrami et al. [2023]"}],"fun_headline_variants":["Four-agent EF2X solved, even with cancelable valuations","EF2X guaranteed for four agents, beyond additive case","EF2X exists for four agents: constructive proof","New algorithm proves EF2X for four agents","Four-agent EF2X always achievable, even beyond additive"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The running-time argument requires that agent 1's valuation has a positive minimum gap between any two distinct bundle values; for arbitrary real-valued inputs the paper does not explicitly justify where this gap comes from, so the pseudo-polynomial guarantee as stated is only fully supported under an integrality or bounded-gap assumption.","fun_headline_variants_meta":{"raw":{"variants":["Four-agent EF2X solved, even with cancelable valuations","EF2X guaranteed for four agents, beyond additive case","EF2X exists for four agents: constructive proof","New algorithm proves EF2X for four agents","Four-agent EF2X always achievable, even beyond additive"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3321,"prompt_tokens":932,"completion_tokens":2389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":2310}},"tokens_in":548,"tokens_out":2389,"duration_ms":17262,"temperature":1.0,"reasoning_tokens":2310,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:33:45.447020+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct counterexample would be a four-agent instance with three cancelable valuations, one arbitrary monotone valuation, and a finite set of goods for which every complete allocation leaves some agent EF2X-envious of another; if such an instance exists, Theorem 3.1 is false. Short of that, one can test the runtime claim by checking whether the algorithm's strict potential increases can be made to grow faster than a polynomial in the input size on a family of small additive instances.","supporting_citations":[{"cited_title":"Almost full E FX exists for four agents","cited_arxiv_id":null,"evidence_quote":"Introduced cancelable valuations and gave EFX guarantees for nice-cancelable instances, supplying the valuation class studied here."},{"cited_title":"An EF2X alloc ation protocol for restricted additive valuations","cited_arxiv_id":null,"evidence_quote":"Introduced EF2X and proved existence for restricted additive valuations, giving the notion and the prior restricted result."}],"review_version":1}