{"id":"0f0bfac8-1c76-4dfb-91cf-348618c53283","arxiv_id":"2508.15380","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For up to four valuation types, a complete 2/3-EFX allocation always exists; for k types, a (1-ε)-EFX allocation with O~(sqrt(k/ε)) charity exists.","lead":"This paper proves that complete 2/3-EFX allocations always exist in fair division when agents have at most four distinct additive valuations, and that (1-ε)-EFX allocations with about sqrt(k/ε) unallocated goods exist when there are k valuation types. It also identifies and fixes two proof errors in a prior EC 2024 paper.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Case 3.2 proof gap: 'Hence Step 9.2 does not fail' is a non sequitur—the derived bound concerns d2's valuation of (X_d1∪C)\\ {g1}, while Step 9.2's failure is edge (d1,d2)∈G_e(X). Without Step 9.2, Steps 9.3/9.4 are not evaluated, so leading agents' 2/3-EFX towards d2 is unsupported.","rationale":"After reading the full proof, the weakest point is exactly where the reader located it. The Case 3.2 argument is the only place where the modified Steps 9.1–9.4 are used to handle the hard subcase of three critical goods with a second D-agent. The proof's line 'Hence Step 9.2 does not fail' is the sole bridge from the algorithm's failure conditions to the EFX inequalities for leading agents toward d2. It is invalid as written: the quantified inequality for d2 does not bear on the existence of edge (d1,d2). I did not find an independent counterexample; the theorem is plausible and prior results support the approach. The issues in Appendix C and the likely typo in the champion graph of Theorem 4 are secondary and do not displace this gap. Because the reader already marked the paper CONDITIONAL and this concern agrees with its weakest assumption, I recommend keeping the verdict unchanged; the authors should repair the Step 9.2 argument or supply a different proof for the subcase.","tokens_in":26537,"tokens_out":11852,"duration_ms":104542,"concrete_test":"Run a bounded exhaustive search over 4-type instances (e.g., groups A,B,C,D with |D|=2 and at most 10 goods) that realize the Case 3.2 configuration at the output of 3PA+-TYPES: |X_d1|=2, |X_d2|=1, (d1,d2)∈G_e(X), |C|=3 with one critical good in each of A,B,C, and all Steps 1–9 failed. For each instance, execute Algorithm 4 and test 2/3-EFX. A violation disproves Theorem 3; if none is found, the theorem can survive but the current proof still needs a new argument, since the paper's inequality does not eliminate the edge (d1,d2).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's concern is correct and is the load-bearing gap for Theorem 3. In Case 3.2 (p.16), after allocating g1 to d2 and {g2,g3} to d1, the proof must show every leading agent in A∪B∪C is 2/3-EFX toward d2. It invokes the failure of Steps 9.3 and 9.4 to conclude v_u(X_u1) ≥ v_u(Y_d2 \\ {g}) for every g∈Y_d2. But Steps 9.3/9.4 are conditional on Step 9.2, whose second condition is |X_d2|=2 or (d1,d2)∉G_e(X). In the subcase |X_d2|=1 with (d1,d2)∈G_e(X), Step 9.2 fails and those steps are never evaluated. The paper attempts to rule out this subcase by deriving v_d((X_d1∪C)\\ {g1}) < 3/2 v_d(X_d2) from the edge and the failure of Step 3. This inequality concerns agent d2's valuation of a large bundle; it does not contradict (d1,d2)∈G_e(X), which asserts v_d(X_d1) < 2/3 v_d(X_d2). It also does not imply |X_d2|=2. Hence the claim 'Step 9.2 does not fail' is unsupported. Because the subsequent EFX argument for leading agents toward d2 rests entirely on the failure of 9.3/9.4, the proof of Theorem 3 has a genuine gap at this point. The theorem may still be true, but the written argument does not cover the case where Step 9.2 fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies approximate envy-freeness up to any good (α-EFX) for indivisible-goods allocation with additive valuations, focusing on instances with few valuation types. The first contribution is Theorem 3, which claims that for any number of agents with at most four distinct additive valuations, Algorithm 4 (FewTypesAllocate) computes a complete 2/3-EFX allocation. The algorithm modifies the 3PA+ algorithm of Amanatidis et al. with new steps 9.1–9.4 and a Pseudo-Cycle-Resolution subroutine; termination is argued via a configuration-repetition argument. The second contribution is Theorem 4, which claims that for any number of agents with at most k distinct valuations there is a (1−ε)-EFX allocation with charity size O~(√(k/ε)), by adapting the rainbow-cycle-number framework of Chaudhury et al. to a graph on leading agents. The paper also reports and corrects an error in the termination proof of the Envy-Cycle-Elimination subroutine in [5], giving a counterexample and a potential-function proof.","tokens_in":27057,"tokens_out":33658,"duration_ms":354786,"significance":"If both main theorems are correct, the paper makes a significant advance. Theorem 3 would give the first complete 2/3-EFX guarantee for an unrestricted number of agents under a type restriction weaker than the known three-type exact-EFX result. Theorem 4 would improve the charity bound from O~(√(n/ε)) to O~(√(k/ε)) when the number of valuation types is small, which is a natural and useful parameter. The paper also contains a concrete, checkable correction to a published proof: the counterexample in Appendix C genuinely shows that the earlier edge-count argument for termination of cycle resolution on the enhanced envy graph is invalid, and the proposed potential function appears to repair it. These are real strengths. However, the proof of Theorem 3 has a load-bearing gap in Case 3.2: the argument that Step 9.2 does not fail is a non sequitur, and the subsequent EFX verification for leading agents toward d2 depends on that unsupported conclusion. The theorem may still be true, but the written proof is incomplete.","major_comments":[{"comment":"The sentence 'Hence Step 9.2 does not fail' is a non sequitur. In the subcase |X_d2|=1 and (d1,d2)∈G_e(X), Step 9.2's condition is false by definition, so Steps 9.3 and 9.4 are never evaluated; their 'failure' cannot be used to infer anything about the final allocation. The attempted contradiction derives v_d((X_d1∪C)\\ {g1}) ≤ (2/3)v_d(X_d2)+(2/3)v_d(X_d2), but Step 3 only bounds pairs of pool goods; X_d1 is not in the pool, so v_d(X_d1) is not controlled by that step. Even if the inequality held, it concerns d2's valuation of a large bundle and does not contradict (d1,d2)∈G_e(X), which asserts v_d(X_d1) < (2/3)v_d(X_d2). Since the claim that leading agents in A∪B∪C are 2/3-EFX toward d2 rests entirely on the failure of Steps 9.3 and 9.4, this subcase is not proven. The theorem may be true, but the written argument does not cover the case where Step 9.2 fails.","section":"§4, proof of Theorem 3, Case 3.2 (p.16)"},{"comment":"The proof asserts without proof that for every source s and every unallocated good g_i there is a leading agent a that is a heavy-champion of X_s∪{g_i}. This existence is what guarantees that every vertex of the t-partite graph has an incoming edge from every other part, and it is therefore load-bearing for the rainbow-cycle argument. The manuscript neither proves this nor cites a specific lemma from [9] that establishes it. It should also explicitly justify that a heavy-champion among non-leading agents can be replaced by the leading agent of the same type (this follows from Proposition 1 but is not stated), and correct the citation to 'Part 2 of Proposition 2' for the fact that a champion finds the relevant good valuable. The gap is likely repairable using standard arguments from [9], but as written the proof is incomplete.","section":"§5.1, proof of Theorem 4"}],"minor_comments":[{"comment":"'due to HV et al.' is informal; use a proper author name or reference number.","section":"Abstract / §1"},{"comment":"The notation '(d1,d2) /∈ G_e(X)' is ambiguous; use a clear '∉' symbol and state explicitly that the step executes when the edge is absent.","section":"Algorithm 2, Step 9.2"},{"comment":"The subroutine is named Pseudo-Cycle-Resolution, but Figure 1 and surrounding text call it Pseudo-Path-Resolution. Please unify the terminology.","section":"Procedure 3 and Figure 1"},{"comment":"Typo: 'least valued good om C' should be 'least valued good in C'.","section":"Algorithm 4, line 14"},{"comment":"The phrase 'assuming 2ε≤1/2' should read 'assuming ε≤1/2'.","section":"§5, Proposition 2 proof"},{"comment":"The citation 'from Lemma 4' for the fact that |X_d1|=2 appears to be a citation error; the relevant statement is Lemma 2 (or its analogue for 3PA+-TYPES).","section":"Theorem 3 proof, Case 2"}],"recommendation":"major_revision","confidential_remarks":"The load-bearing gap in Theorem 3, Case 3.2 must be closed before the paper can be accepted. The authors need either to prove that the problematic subcase cannot occur, to modify the algorithm so that Steps 9.3/9.4 are triggered when needed, or to provide a separate EFX argument for leading agents toward d2 when Step 9.2 fails. The corrections to [5] appear sound and are a useful contribution in their own right. Theorem 4 is plausible but needs the champion-existence lemma made explicit."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: the paper has a real gap in the proof of Theorem 3, so it is not yet a complete resolution of the four-type 2/3-EFX question. The rest of the package is solid and worth engaging with.\n\nWhat is genuinely good: the corrected termination proof for ECE in the enhanced envy graph is a real fix, and the erratum about 3PA+ Step 9 (using G_e instead of G_r) is also correct and useful. The charity result in Theorem 4, replacing n with k in the ~O(sqrt(n/eps)) bound via a champion graph on leading agents, is a clean and plausible extension of the rainbow-cycle framework. If the edge definition in that proof is just a typo, as I suspect, the argument should go through.\n\nThe problem is Theorem 3, Case 3.2 (page 16). The proof needs leading agents from groups A, B, C to be 2/3-EFX toward d2. It claims that Steps 9.3 and 9.4 fail, and therefore each such leading agent satisfies the required inequality. But Steps 9.3/9.4 are only evaluated when Step 9.2's condition holds. In the subcase |X_d2|=1 and (d1,d2) in G_e(X), Step 9.2 fails, so those steps were never run, and their failure cannot be asserted. The paper tries to rule out this subcase with the sentence \"Hence Step 9.2 does not fail,\" but what precedes it is a valuation inequality about (X_d1 ∪ C) \\ {g1}. That inequality does not contradict (d1,d2) being an edge of G_e(X); it is perfectly consistent with the edge. So the step as written is a non-sequitur, and the main theorem's proof has a genuine gap. The theorem may still be true, and I expect it is, but this written argument does not cover the case.\n\nThere is also a likely typo in Theorem 4's champion graph: the edge condition references g_i while the head vertex is (g_j, s(b)). That should presumably be g_j. Minor, but should be fixed.\n\nWho is this for: anyone working on EFX existence or approximate EFX with few types. The corrections to [5] and the charity result are cite-worthy even if Theorem 3 remains open in this version. I would send it to peer review, but with the expectation that the authors need to repair the Case 3.2 argument or restructure the proof so the failure of Steps 9.3/9.4 is established without relying on Step 9.2's condition.","headline":"The charity bound and the corrections to Amanatidis et al. are solid, but the four-type 2/3-EFX theorem has a genuine proof gap in Case 3.2 that the current argument does not fill.","tokens_in":27493,"tokens_out":4324,"would_cite":true,"duration_ms":40054,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For instances with at most four types of additive valuations, a complete 2/3-EFX allocation always exists for any number of agents, and with k types a (1−ε)-EFX allocation can leave only about √(k/ε) goods in charity.","keywords":["fair division","indivisible goods","EFX","2/3-EFX","additive valuations","few types of agents","EFX with charity","rainbow cycle number"],"falsifier":"Construct a four-type instance that reaches Case 3.2 of the proof—one source, at least two agents in the source's group, and three critical goods—where $|X_{d2}|=1$ and $(d_1,d_2)$ is an edge of the enhanced envy graph, while the stated inequality $v_d((X_{d1} \\cup C) \\setminus g_1) < \\frac{2}{3} v_d(X_{d2})$ holds; then run Algorithm 4 and check whether any agent in groups A, B, or C fails to be $\\frac{2}{3}$-EFX toward $d_2$. A single such instance, or an exhaustive search of small four-type instances finding no complete $\\frac{2}{3}$-EFX allocation, would refute the theorem.","tokens_in":26504,"feed_emoji":"⚖️","tokens_out":7059,"duration_ms":70541,"temperature":0.7,"texified_at":"2026-08-05T19:51:24.887476+00:00","pith_summary":"The paper proves that envy-freeness up to any good, the standard fairness guarantee for indivisible goods, can be approximated in settings with few distinct preference types. Its main result is that for any number of agents whose additive valuations fall into at most four groups, a complete allocation exists in which every agent is $\\frac{2}{3}$-EFX: each agent prefers her own bundle to any other agent's bundle with its single best item removed, up to a $\\frac{2}{3}$ factor. This extends the previously known three-type guarantee to four types. A second result shows that with $k$ types, a $(1-\\varepsilon)$-EFX allocation can leave only about $\\sqrt{k/\\varepsilon}$ goods unallocated, replacing the previous charity bound's dependence on the number of agents $n$ by the number of types $k$. These are practical settings because demographic grouping, public housing categories, and similar applications naturally produce few preference types.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":8175,"prompt_tokens":845,"completion_tokens":7330,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":845,"completion_tokens_details":{"reasoning_tokens":6526}},"feed_headline":"Four agent types always admit a 2/3-EFX allocation","feed_subtitle":"Any number of agents with at most four valuations get all goods in a 2/3-EFX split; for k types, charity stays near √(k/ε).","key_machinery":"The object carrying the argument is the 3PA+-TYPES algorithm: the property-preserving partial-allocation algorithm of [5] modified by Steps 9.1–9.4, which add a Pseudo-Cycle-Resolution subroutine. The subroutine shifts bundles along an envy path that passes through leading agents only, and then reorders bundles within each group to preserve the ordering invariant; this is what lets the algorithm allocate the contested critical goods when a single source exists. Around this sits the standard machinery of leading agents, the ordering invariant, reduced and enhanced envy graphs, and the critical-good completion lemma of [19], plus, for the charity result, the rainbow cycle number of [9].","core_discovery":"On its own terms, the paper's central claim is Theorem 3: every additive-valuation instance with at most four valuation types admits a complete $\\frac{2}{3}$-EFX allocation, no matter how many agents there are. The proof extends the 3PA+ algorithm of [5] with extra steps (9.1–9.4) that handle the single-source, three-critical-goods configuration, using a 'pseudo-cycle' swap among leading agents of the four groups to redistribute bundles without breaking the $\\frac{2}{3}$-EFX property. Theorem 4 then gives a $(1-\\varepsilon)$-EFX allocation with $\\tilde{O}(\\sqrt{k/\\varepsilon})$ charity for $k$ types, by building a rainbow-cycle-free 'champion graph' on leading agents and invoking the $O(d \\log d)$ bound on the rainbow cycle number. Along the way the","pith_inferences":["If the gap in Theorem 3's Case 3.2 can be closed by a stronger argument, the pseudo-cycle technique could extend to more than four types; the paper's own bottleneck note about critical goods suggests the current construction is near its limit.","The charity bound's dependence on k rather than n implies that for large populations with few preference types, the number of unallocated goods stays manageable—exactly the regime in which the result has practical force.","A natural test is to implement the 3PA+-TYPES algorithm and search random four-type instances for violations of the Step 9.2 implication, which would turn the suspected proof gap into a concrete counterexample if it exists."],"forward_implications":["Complete 2/3-EFX is now guaranteed for any number of agents with at most four distinct additive valuations, not just three.","For k valuation types, one can compute a (1−ε)-EFX allocation that leaves out O~(√(k/ε)) goods, with the charity bound independent of the total number of agents.","The corrected analysis of the 3PA+ algorithm—termination via a product potential and the use of the enhanced envy graph in path resolution—restores the previously claimed seven-agent 2/3-EFX guarantee.","The non-degeneracy assumption is harmless for α-EFX, so the existence results apply to degenerate instances as well."],"supporting_citations":[{"why":"Supplies the 3PA+ algorithm and the seven-agent 2/3-EFX framework that the paper modifies and corrects.","marker":"[5]"},{"why":"Establishes the leading-agent and ordering-invariant properties of k-type instances that the four-type proof relies on.","marker":"[16]"},{"why":"Provides the critical-good completion lemma used to turn the partial allocation into a complete 2/3-EFX allocation.","marker":"[19]"},{"why":"Supplies the near-tight bound R(d)=O(d log d) on the rainbow cycle number used to bound charity for k types.","marker":"[1]"},{"why":"Introduces the rainbow cycle number and the reduction from bounded-charity EFX to rainbow cycles.","marker":"[9]"},{"why":"Provides the envy-cycle elimination procedure whose correctness and termination underlie several steps.","marker":"[17]"},{"why":"Gives basic 1/2-EFX existence and the fact that envy-cycle elimination preserves EFX properties.","marker":"[20]"},{"why":"Shows non-degeneracy can be assumed; the paper extends the lemma to α-EFX.","marker":"[11]"}],"fun_headline_variants":["Four types guarantee 2/3-EFX for any number of agents","2/3-EFX always achievable with at most four valuations","Any agent count, four types: 2/3-EFX guaranteed","Fair split for all: 2/3-EFX with just 4 value types","With just 4 value types, 2/3-EFX is always possible"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The four-types theorem rests on the claim that in the single-source, three-critical-goods case, the valuation inequalities in the proof force the algorithm's Step 9.2 condition to hold; that implication is asserted but not established.","fun_headline_variants_meta":{"raw":{"variants":["Four types guarantee 2/3-EFX for any number of agents","2/3-EFX always achievable with at most four valuations","Any agent count, four types: 2/3-EFX guaranteed","Fair split for all: 2/3-EFX with just 4 value types","With just 4 value types, 2/3-EFX is always possible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001264,"raw_usage":{"total_tokens":5071,"prompt_tokens":863,"completion_tokens":4208,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":4114}},"tokens_in":607,"tokens_out":4208,"duration_ms":33988,"temperature":1.0,"reasoning_tokens":4114,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T17:58:00.764741+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a four-type instance that reaches Case 3.2 of the proof—one source, at least two agents in the source's group, and three critical goods—where $|X_{d2}|=1$ and $(d_1,d_2)$ is an edge of the enhanced envy graph, while the stated inequality $v_d((X_{d1} \\cup C) \\setminus g_1) < \\frac{2}{3} v_d(X_{d2})$ holds; then run Algorithm 4 and check whether any agent in groups A, B, or C fails to be $\\frac{2}{3}$-EFX toward $d_2$. A single such instance, or an exhaustive search of small four-type instances finding no complete $\\frac{2}{3}$-EFX allocation, would refute the theorem.","supporting_citations":[{"cited_title":"Pushing the Frontier on Approximate EFX Allocations","cited_arxiv_id":null,"evidence_quote":"Supplies the 3PA+ algorithm and the seven-agent 2/3-EFX framework that the paper modifies and corrects."},{"cited_title":"EFX Exists for Three Types of Agents, November 2024","cited_arxiv_id":null,"evidence_quote":"Establishes the leading-agent and ordering-invariant properties of k-type instances that the four-type proof relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the critical-good completion lemma used to turn the partial allocation into a complete 2/3-EFX allocation."},{"cited_title":"EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number.Operations Research, 73(2):738–751, March 2025","cited_arxiv_id":null,"evidence_quote":"Supplies the near-tight bound R(d)=O(d log d) on the rainbow cycle number used to bound charity for k types."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the rainbow cycle number and the reduction from bounded-charity EFX to rainbow cycles."},{"cited_title":"Fair allocation of a multiset of indivisible items","cited_arxiv_id":null,"evidence_quote":"Provides the envy-cycle elimination procedure whose correctness and termination underlie several steps."}],"review_version":1}