{"id":"6492215b-1d45-4bc6-92c8-4158cc793b8f","arxiv_id":"2608.03171","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Any hypergraph with girth at least 4 admits an EFX allocation under general monotone valuations, and a restricted class of multi-hypergraphs admits one in pseudo-polynomial time.","lead":"This paper proves that a fair division guarantee called EFX always holds for hypergraph-shaped allocation problems without short cycles, and that such allocations can be computed efficiently. It matters because EFX existence is a major open problem in fair division, and each new class where it holds narrows the gap.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's pseudo-polynomial time claim is formally undefined because valuations are allowed to be arbitrary reals; Lemma 4.9's social-welfare potential requires an integrality assumption that is never stated.","rationale":"The reader's weakest_assumption correctly identifies the valuation-encoding gap in Theorem 2's pseudo-polynomial time claim. My independent read of the proof confirms that the existence arguments for both theorems are coherent: the girth conditions support Observations 2.1 and 2.2, the induction in Lemmas 3.2 and 4.5 preserves EFX, and the parking argument in Lemma 4.8 supplies non-envied recipients for unallocated patches. The only place where the proof relies on an unstated assumption is the transition from a strictly increasing social-welfare potential to a pseudo-polynomial time bound, which requires valuations to take values in a discrete set with a minimum positive increment. This is a genuine but localized gap: it affects the complexity guarantee of Theorem 2, not the existence of EFX allocations. The fix is straightforward (state integer-valued valuations), so the reader's CONDITIONAL verdict is appropriate and my read does not move it. I found no additional load-bearing flaw in the central constructions.","tokens_in":18027,"tokens_out":48429,"duration_ms":434873,"concrete_test":"Check the Preliminaries and Lemma 4.9 for any assumption that valuations are integer-valued or bounded-precision rationals. If none exists, add the assumption that every vi(S) is a nonnegative integer and re-derive the potential bound: since each while iteration in FixProp3Gen strictly increases the integer social welfare, the number of iterations is at most the total sum of all agents' values for the grand bundle, making the running time pseudo-polynomial. If the paper intends arbitrary real valuations, replace the pseudo-polynomial claim in Theorem 2 with an existence-only statement, since the potential argument provides no complexity bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 defines valuations as vi: 2^M -> R≥0, with no integrality or bounded-precision assumption, and Theorem 2 promises a pseudo-polynomial-time construction. The proof of Lemma 4.9 argues termination by the social-welfare potential: every update strictly increases the sum of agents' values for their own bundles, 'following the analysis of [19]'. This argument only yields a bound on the number of iterations if each increment is bounded away from zero, which holds for integer (or fixed-precision rational) valuations but not for arbitrary reals; with R≥0 values, the same social welfare can increase by 1/2, 1/4, ... over exponentially many allocations. Moreover, pseudo-polynomial time is not even defined for a value-oracle model with arbitrary real outputs. Thus the complexity guarantee in Theorem 2 is incomplete as stated. This does not invalidate the existence part: the algorithm still terminates in finite time because only finitely many allocations exist, and Theorem 1's polynomial bound (Lemma 3.6) is a separate combinatorial argument not affected by this issue. But the pseudo-polynomial claim in Theorem 2 requires a stated assumption on valuation encoding.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the existence and computation of EFX allocations in a graphical fair-division setting where agents are vertices of a (multi)hypergraph and goods are edges; each agent may value only the edges incident to it. The first main result (Theorem 1) states that for hypergraphs with girth at least 4 and arbitrary monotone valuations, an EFX allocation always exists and can be constructed in polynomial time. The second main result (Theorem 2) extends this to multi-hypergraphs of girth at least 4 under an additional structural condition: there is a vertex whose incident edge-multiplicities are at most the corresponding edge size minus 2; for this case the construction is claimed to run in pseudo-polynomial time. The proofs maintain a partial EFX orientation satisfying four invariants, use a distinguished vertex 0 to 'park' non-oriented edges, and in the multi-hypergraph case import a minimal-envy-patch subroutine from Chaudhury et al. [19]. A reduction (Lemma 4.1) is given to indicate that dropping the multiplicity restriction is at least as hard as the almost-full EFX problem.","tokens_in":18135,"tokens_out":25220,"duration_ms":222006,"significance":"If correct, Theorem 1 is a solid advance: it establishes exact EFX existence for hypergraphs of girth at least 4 under fully general monotone valuations, going beyond the previously known approximate guarantee for girth-3 hypergraphs and complementing the triangle-free multigraph results in the literature. The four-property framework and the use of a single parking vertex are clean, and the girth observations (Observations 2.1-2.2) are simple but effective in limiting how many edges can be visible to a pair of agents. The paper is also honest about the boundary of its technique: Theorem 2 requires a restrictive multiplicity condition, and Lemma 4.1 connects the relaxed condition to the hard almost-full EFX problem. The main weaknesses are formal: the complexity claims are not fully pinned down with respect to the valuation model, and the polynomial-time proof of Lemma 3.6 contains a misstatement that needs a corrected argument to support the claimed bound.","major_comments":[{"comment":"The pseudo-polynomial time claim in Theorem 2 is not well-defined for the valuation model stated in Section 2. There, valuations are arbitrary monotone functions vi: 2^M -> R_{\\ge 0}; for real-valued inputs, 'pseudo-polynomial time' has no standard meaning because there is no integer parameter with respect to which the running time can be measured. Moreover, the proof of Lemma 4.9 argues termination by the social-welfare potential strictly increasing, 'following the analysis of [19]'. That argument yields an iteration bound only if each increase of the potential is bounded away from zero, which holds for integer-valued (or fixed-precision rational) valuations but not for arbitrary reals. As written, Lemma 4.9 establishes only finite termination. I recommend adding an explicit integrality or bounded-precision assumption to Theorem 2 and the abstract, or replacing the pseudo-polynomial claim with a finite-termination statement. This issue does not affect the existence part of Theorem 2, but it is load-bearing for the stated complexity guarantee.","section":"Section 2, Lemma 4.9, Theorem 2"},{"comment":"The proof that Algorithm 2 runs in O(n^6) time contains an incorrect statement. It says: 'every envied vertex receives a single edge' and uses this to conclude that each vertex can be updated at most n times. However, line 4 of Algorithm 2 sets X_i <- U_i(X), which may contain many edges, not a single edge. The intended bound can likely be repaired by arguing that whenever a vertex's bundle changes, its value strictly increases, and therefore a vertex can never receive the same edge twice; this would bound the number of allocations per vertex by its degree. But this argument is not given, and the stated reason ('it has at most n relevant edges') does not by itself bound the number of updates of the form U_i(X). As written, Lemma 3.6 does not establish the polynomial-time claim of Theorem 1, so the proof of that central theorem is incomplete at this point.","section":"Lemma 3.6, Algorithm 2"}],"minor_comments":[{"comment":"The phrase 'polynomial time to the number of agents and goods' should read 'polynomial in the number of agents and goods'.","section":"Abstract and Theorem statements"},{"comment":"The line 'k = arg max_j {v_j(Z) > v_j(X_j)}' is ambiguous: it should specify that k is the highest-index vertex satisfying the condition, since the proofs of Property (2) in Lemmas 4.6 and 4.7 rely on that tie-breaking rule.","section":"Algorithm 4, line 3"},{"comment":"The assertion that 'vertex 0 may be only allocated edges from a single patch' is used critically in Algorithm 6 but is not explicitly proven; it follows because FixProp3Gen replaces the whole bundle (X_k <- Z) rather than appending to it, so the last allocation to vertex 0 always comes from a single patch. Please state this justification explicitly.","section":"Lemma 4.8"},{"comment":"The heading 'Envy - EFX allocation' has a typographical issue, and the definition of an allocation is introduced before the graphical model; consider reorganizing so that an allocation is defined after the hypergraph setting.","section":"Section 2"},{"comment":"The sentence 'k defined in line 3 belongs to e since v_k(Z) > v_k(X_k) \\ge 0' is terse; it relies on the fact that a positive value for a set Z implies positive value for at least one edge in it, and all edges in a patch share the same vertex set, so k must be in e.","section":"Lemma 4.3"},{"comment":"In the discussion of Christodoulou et al., the phrase 'construct an EFX allocation by orienting the edges' would be clearer as 'construct an EFX orientation', as that is the standard term used later in the paper.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the main existence results appear plausible and well-structured. The major issues are repairable: the polynomial-time proof of Lemma 3.6 needs a corrected argument, and Theorem 2's pseudo-polynomial claim needs either an explicit integrality assumption or a downgraded statement. I do not see a fundamental flaw in the existence proofs, but the current text does not yet support the advertised complexity statements. The reliance on Subroutine 7 from [19], including a coauthor, is legitimate as a published black box and does not create circularity; the self-referential limitation statements in the introduction are consistent with the body of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a genuine step forward for EFX on hypergraphs: it turns the known sqrt(2)/2-EFX approximation for girth-at-least-3 hypergraphs into exact EFX for girth-at-least-4, under general monotone valuations, and adds a multi-hypergraph generalization with a single restricted vertex. The parking-vertex approach is a real idea, and Lemma 4.1 gives a nice tightness argument: if you allow one incident patch of multiplicity |e|-1 at the special vertex, you are solving the almost-full EFX problem with one unallocated good. I read the core invariants carefully and they hold up. Observations 2.1 and 2.2 do the girth work, Properties 1–4 are checked in the lemmas, and there's no circularity: Subroutine 7 is imported from a published paper and has nothing to do with the claims here.\n\nThe soft spot is Theorem 2's complexity statement. Section 2 lets valuations be arbitrary reals, and pseudo-polynomial time isn't defined for real-valued input. Lemma 4.9 argues termination by social-welfare potential, \"following [19]\"; that only yields a pseudo-poly bound if each increment is bounded away from zero, i.e., if valuations are integer or fixed-precision rational. With reals, the same social welfare can climb by 1/2, 1/4, ... over an exponential number of allocations. So as stated, the pseudo-polynomial claim is not quite a theorem. The existence part of Theorem 2 survives: the algorithm still terminates in finite time because there are finitely many allocations and the potential strictly increases. And the polynomial-time claim in Theorem 1 is unaffected—that bound (Lemma 3.6) counts actual reallocations of edges, not potential increments, and appears robust.\n\nThere's also a confusing sentence before Lemma 4.9 about Subroutine 7 running in time \"polynomial on the number of different values of the social welfare\"—that's garbled and should be cleaned up, but it doesn't affect the mathematics.\n\nWho should read this: anyone tracking the EFX frontier in graphical and hypergraph settings. It deserves a serious referee. If I were refereeing, I'd ask for the valuation-encoding assumption to be stated, or the complexity claim downgraded to finite termination, plus a clarification of that garbled sentence. I wouldn't block acceptance on the existence theorems.","headline":"Solid EFX frontier result with a real but repairable hole in the pseudo-polynomial claim of Theorem 2.","tokens_in":18791,"tokens_out":5406,"would_cite":true,"duration_ms":52197,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that EFX allocations always exist for hypergraphs of girth at least 4, under arbitrary monotone valuations, and can be built in polynomial time; a generalized result covers multi-hypergraphs under a multiplicity bound.","keywords":["EFX allocation","envy-free up to any good","hypergraph","multi-hypergraph","girth","monotone valuations","fair division","algorithmic game theory"],"falsifier":"Exhibit one finite hypergraph of girth at least 4 with agents holding arbitrary monotone valuations and prove that no complete EFX allocation exists; the paper predicts every such instance has one. For the multi-hypergraph theorem, apply the paper's own Lemma 4.1 reduction to any instance of the open almost-full EFX problem: the resulting multi-hypergraph has a vertex whose single violating edge has multiplicity exactly one above the bound, so an instance of that open problem with no almost-full EFX allocation would directly contradict Theorem 2's conclusion.","tokens_in":17723,"feed_emoji":"⚖️","tokens_out":10051,"duration_ms":74187,"temperature":0.7,"pith_summary":"This paper attacks the open problem of whether envy-free-up-to-any-good (EFX) allocations always exist. It establishes that on hypergraphs whose shortest cycle has length at least 4, an EFX allocation always exists for any number of agents with general monotone valuations that only increase with more goods, and it can be constructed in polynomial time. For multi-hypergraphs, where several goods may sit on the same set of vertices, the same conclusion holds in pseudo-polynomial time provided at least one vertex has all its incident edges of multiplicity at most the edge size minus 2. The significance is that these are among the broadest settings in which exact EFX, rather than an approximation, is guaranteed; the previous best for hypergraphs of girth at least 3 was only an approximate guarantee.","feed_headline":"Hypergraphs without short cycles always admit EFX fair splits","feed_subtitle":"Exact envy-freeness up to any good holds for general monotone valuations, with a polynomial-time construction.","key_machinery":"The load-bearing structure is the girth-at-least-4 condition on the underlying simple hypergraph. It yields two facts: any two vertices lie together in at most one edge (Observation 2.1), and two vertices that share an edge have no common neighbor outside that edge (Observation 2.2). These make a vertex's incident edges nearly private, which lets the algorithm designate vertex 0 as a parking spot for all edges that cannot be oriented to an endpoint without creating envy, and lets the completion phase hand a newly allocated edge to a non-envied vertex knowing that only its intended recipient values it. The second mechanism is the subroutine from [19] that finds an inclusion-wise minimal subset from a patch of identical-copy edges such that no agent envies a proper subset of it, together with a social-welfare potential that strictly increases at every step, which bounds the running time as pseudo-polynomial in the multi-hypergraph case.","core_discovery":"The central claim, stated as Theorem 1, is that every instance on a hypergraph of girth at least 4 — where agents are vertices, goods are edges, and a good matters only to the agents incident to it — admits a complete EFX allocation for arbitrary monotone valuations, producible in time polynomial in the number of agents and goods. The proof is constructive: it first builds a partial EFX orientation in which a specially designated vertex 0 stays non-envied while all difficult edges are parked on it, then completes the allocation by giving every remaining edge either to a non-envied vertex or to vertex 0. Theorem 2 extends the same template to multi-hypergraphs in which edges may repeat, requiring only that some vertex have incident edge multiplicities bounded by the edge size minus 2, in which case the construction runs in pseudo-polynomial time. The paper also shows the multiplicity condition is not an artifact: if a single vertex is allowed one incident edge of multiplicity one more than the bound, the problem becomes as hard as the open almost-full EFX problem of existence with at most one unallocated good.","pith_inferences":["The proof's reliance on the two girth-4 observations suggests girth 4 is not merely sufficient for this technique but likely necessary for it; testing exact EFX on small girth-3 hypergraphs would reveal whether the girth restriction can be relaxed at all.","The pseudo-polynomial runtime in the multi-hypergraph case is driven by a social-welfare potential that can take exponentially many values; a combinatorial lexicographic potential might give a polynomial bound in this restricted setting, which would be a testable improvement.","The reduction in Lemma 4.1 connects the multiplicity bound to the almost-full EFX problem: progress on EFX with bounded charity would automatically imply EFX existence for a wider class of multi-hypergraphs, and a counterexample in that class would refute a natural relaxation.","The park-on-vertex-0 template may transfer to other structured markets, such as goods with limited externalities described by interval or geometric graphs, wherever a small set of hub vertices can absorb all edges that cannot be oriented."],"forward_implications":["Every simple hypergraph with girth at least 4, including every 3-cycle-free graph, admits a complete EFX allocation for general monotone valuations, constructible in polynomial time.","The same guarantee holds in multi-hypergraphs with girth at least 4 as soon as one vertex meets the multiplicity bound $|\\mathcal{P}_e| \\le |e|-2$ for all incident patches, though the construction is only pseudo-polynomial.","A designated non-envied parking vertex can absorb all non-orientable edges without creating envy, so the absence of an EFX orientation is not an obstacle to an exact EFX allocation.","Relaxing the multi-hypergraph condition by allowing a single incident edge of multiplicity one larger than the bound makes the existence problem at least as hard as the open almost-full EFX problem, so the bound is tight relative to that open problem."],"supporting_citations":[{"why":"Introduces the graph/hypergraph fair-division setting and the algorithm skeleton (its Algorithm 2) whose EFX preservation this paper generalizes to hypergraphs.","marker":"[20]"},{"why":"Supplies rule U1 and Subroutine 7 (its Algorithm 3) that FixProp3Gen uses to find minimally envied subsets of unallocated patches, along with the social-welfare potential behind the pseudo-polynomial bound.","marker":"[19]"},{"why":"Establishes the prior best guarantee for hypergraphs of girth at least 3 (approximate EFX for subadditive valuations), which Theorem 1 improves to exact EFX for girth at least 4.","marker":"[34]"},{"why":"The almost-full EFX problem for four agents that Lemma 4.1 reduces to, demonstrating the tightness of the multiplicity condition.","marker":"[11]"}],"fun_headline_variants":["Girth-4 hypergraphs always permit EFX allocations","Sparse hypergraphs guarantee envy-free-up-to-any-good splits","EFX fairness achievable in hypergraphs with no short cycles","No short cycles, no envy: EFX exists for hypergraph goods","Poly-time EFX construction for girth-4 hypergraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire construction assumes the underlying simple hypergraph has girth at least 4, so any two vertices share at most one edge and two vertices of a shared edge have no outside common neighbor, and, in the multi-hypergraph case, that some one vertex has all incident edge multiplicities at most the edge size minus 2; if either fails, the parking argument that prevents new envy collapses.","fun_headline_variants_meta":{"raw":{"variants":["Girth-4 hypergraphs always permit EFX allocations","Sparse hypergraphs guarantee envy-free-up-to-any-good splits","EFX fairness achievable in hypergraphs with no short cycles","No short cycles, no envy: EFX exists for hypergraph goods","Poly-time EFX construction for girth-4 hypergraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1429,"prompt_tokens":959,"completion_tokens":470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":383}},"tokens_in":575,"tokens_out":470,"duration_ms":4232,"temperature":1.0,"reasoning_tokens":383,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:54:34.089835+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit one finite hypergraph of girth at least 4 with agents holding arbitrary monotone valuations and prove that no complete EFX allocation exists; the paper predicts every such instance has one. For the multi-hypergraph theorem, apply the paper's own Lemma 4.1 reduction to any instance of the open almost-full EFX problem: the resulting multi-hypergraph has a vertex whose single violating edge has multiplicity exactly one above the bound, so an instance of that open problem with no almost-full EFX allocation would directly contradict Theorem 2's conclusion.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the prior best guarantee for hypergraphs of girth at least 3 (approximate EFX for subadditive valuations), which Theorem 1 improves to exact EFX for girth at least 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The almost-full EFX problem for four agents that Lemma 4.1 reduces to, demonstrating the tightness of the multiplicity condition."}],"review_version":2}