{"id":"3cc32773-00a3-4352-962b-7745c1c78bd9","arxiv_id":"2502.09777","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EFX allocations always exist for general monotone valuations in bipartite multigraphs, in multigraphs where each agent has at most ceil(n/4)-1 neighbors, and in multigraphs whose shortest non-parallel cycle has length at least 6.","lead":"This math paper proves that fair 'nobody is jealous' allocations always exist in certain graph-shaped sharing problems where each good is only useful to two people. It adds three guarantees, covering bipartite graphs, graphs with few friends, and graphs with long cycles, to a famous open problem in fair division.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"General-case proof is a roadmap: Theorems 2-3 for many parallel edges rest on unproven assertions in Section 4, so the central claim is not yet fully established.","rationale":"The reader's weakest assumption (the w.l.o.g. reductions involving dummy edges and degree-1 vertices) is patchable: zero-marginal dummy edges can be deleted from an EFX allocation without changing any agent's value for any bundle up to removal of a good, and a degree-1 vertex can be pre-assigned its only edge and then ignored because all other agents are EFX-satisfied against a singleton. Thus that concern does not really threaten the central claim. The genuine soft spot is Section 4, which is explicitly a 'proof roadmap' for the general many-parallel-edges case. The bipartite theorem has independent parallel support, and the at-most-2-parallel-edges section is detailed, but the full Theorems 2 and 3 depend on Lemma 4.9's unproven envy characterization, on Step 2/3 transfers asserted as 'essentially the same,' and on a sketched proof of Algorithm 7. This is a correctness-risk gap rather than a demonstrated counterexample. The proposed concrete test, whether analytical or computational, would determine whether the gap is merely expository or hides an actual error. The reader's CONDITIONAL verdict is therefore appropriate and need not change.","tokens_in":31229,"tokens_out":25134,"duration_ms":239922,"concrete_test":"Fill the gap in Lemma 4.9: for a non-PVCP pair (i,j) with the 3-bundle partition (P1, P2\\{g}, {g}) from Lemma 4.6, prove that in any maximum-weight A-perfect matching of H(G) (Definition 4.8), neither endpoint can receive the other's most-preferred bundle while its own most-preferred bundle is unallocated, by exhibiting an alternating swap that increases total weight. Then verify the EFX inequalities for each resulting allocation. As a computational check, enumerate all small multigraphs (n <= 8) with additive valuations, construct H(G), enumerate all maximum-weight matchings, and test Properties (1), (2), and (3.2). A single violation would refute Lemma 4.9; if none appears, the roadmap remains plausible but still lacks a written proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim covers arbitrary parallel multiplicity, but Section 4 begins with 'We provide a proof roadmap' and does not give complete proofs for the general case. Three specific gaps are load-bearing. First, Lemma 4.9 asserts that 'if i envies j in XM, then (i,j) is in PVCP and j should have received B1_i(j)' with no derivation. For non-PVCP pairs, Lemma 4.6 only guarantees that i and j have different most-valued bundles among the 3-partition; it does not by itself rule out j receiving i's most-preferred bundle while i receives its second-most-preferred bundle, which would break EFX for i against j. This can probably be repaired by a weight-improving swap in the maximum A-perfect matching, but the required argument is absent. Second, Step 2 for the bundle case says Algorithm 8 is 'essentially the same' as Algorithm 4, yet the proof that Observation 2.1 (a single envying vertex, with the envied vertex's bundle relevant only to that vertex) remains valid after a vertex's bundle becomes a union of bundles from several neighbors is not provided. Third, Algorithm 7's termination and the preservation of Property (2) after shrinking the Baux sets are only sketched. Since Theorems 2 and 3 for more than two parallel edges rely entirely on these claims, the existence result is conditional on completing these proofs.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the existence of envy-free-up-to-any-good (EFX) allocations in multigraphs under general monotone valuations, where agents are vertices, goods are edges, and each agent values only its incident edges. The main theorems (Theorems 1-3) claim that an EFX allocation always exists if the multigraph is bipartite, or if every agent has at most ceil(n/4)-1 neighbors, or if the shortest cycle with non-parallel edges has length at least 6. The proof follows a three-step framework: an initial EFX orientation with structural properties, an envy-reduction algorithm, and a final allocation of unallocated bundles to non-endpoint non-envied vertices. Section 3 presents a complete proof for the special case of at most two parallel edges per pair of vertices, while Section 4, titled 'Many Parallel Edges', is presented as a proof roadmap for the general case.","tokens_in":31507,"tokens_out":11165,"duration_ms":95416,"significance":"If fully established, these results would generalize the simple-graph EFX result of Christodoulou et al. [19] and the restricted-additive multigraph result of Kaviani et al. [29] to general monotone valuations for three classes of multigraphs, and would improve on concurrent work for bipartite multigraphs and for graphs with long non-parallel cycles. The three-step framework is original and the special case of at most two parallel edges (Section 3) is argued carefully, with a sound matching-weight argument in Lemma 3.7 and a coherent final-allocation proof in Lemma 3.12. However, the general-case proofs in Section 4 are incomplete in several load-bearing places, so the theorems as stated for arbitrary parallel multiplicity are not yet fully supported.","major_comments":[{"comment":"The proof of Property (1) contains an unsubstantiated assertion: it states that 'if i envies j in XM, then (i,j) ∈ PVCP and j should have received B1_i(j)' without a derivation. For pairs (i,j) not in PVCP, Lemma 4.6 only guarantees that i and j have different most-valued bundles among the 3-partition; it does not rule out the case where j receives i's most-preferred bundle P1 while i receives a strictly lower-valued bundle. Moreover, even if j receives P1, EFX requires vi(Xi) ≥ vi(P1 \\ {e}) for every e ∈ P1, and this does not follow from the EFX-cut used in Lemma 4.6, which gives a guarantee between P1 and P2, not between P2 \\ {g} and P1. A matching-exchange argument or a counterexample is needed; this gap is load-bearing for Theorem 2 in the general parallel-edge case.","section":"Section 4.1.2, Lemma 4.9"},{"comment":"The proof relies on Observation 2.1 to assert that the only bundle released is between i and pi(X), but Observation 2.1 is stated and proved for single-edge orientations. The manuscript does not prove that in the bundle setting an envied vertex's bundle cannot be a union of bundles from several neighbors under an EFX orientation, nor does it justify that setting Xpi(X) ← ∅ in line 7 preserves the invariant that every Xi is a union of bundles from Bi. These points are needed for the correctness of Step 2 in all three theorems when extended to bundles.","section":"Section 4.2, Algorithm 8 / Lemma 4.17"},{"comment":"The termination proof and the preservation of Properties (1)-(2) after shrinking the sets Baux_i are only sketched. Specifically, the claim that vertex b remains non-envied after Baux_b is updated relies on Observation 4.13, but the proof of that observation only covers the original Baux sets and does not explain why the same reasoning remains valid after the sets are shrunk in lines 12-15. It is also not shown that Property (2) holds with respect to the redefined U Baux_i(X) after the update. These are load-bearing for Theorem 3 in the general case.","section":"Section 4.1.3, Lemma 4.12 / Algorithm 7"},{"comment":"The paper opens Section 4 with 'We provide a proof roadmap' and defers several arguments from Section 3 to the general case by saying they are 'essentially the same' or 'exactly the same' (e.g., the transition from Claim 3.13 to Claim 4.20, and Step 2's Algorithm 8 relative to Algorithm 4). For a journal publication, the general case must either be proved in full or the theorems should be restricted to the at-most-two-parallel-edges case. As written, Theorems 1-3 for arbitrary parallel multiplicity are not fully established by the provided proofs.","section":"Section 4, general"}],"minor_comments":[{"comment":"The reductions for degree-1 vertices and for adding dummy zero-value edges are stated as 'w.l.o.g.' but are not formalized. Please add a short argument showing that an EFX allocation in the augmented instance (with degree-1 vertices pre-allocated or dummy edges added) translates back to an EFX allocation in the original multigraph.","section":"Section 2, 'At least degree 2 in G'"},{"comment":"The sentence 'Note that all edges between two endpoints are partitioned in a single way, i.e., the vertex in side B EFX-cuts' appears to be copied from the bipartite case and is confusing in the general setting, where there is no distinguished side B.","section":"Section 4, Definition 4.7"},{"comment":"In the proof, the phrase 'If P2 contains more than one goods' should be 'more than one good', and the argument that vi({g}) ≤ vi(P1) would benefit from an explicit sentence explaining that it follows from the EFX-cut property for i when |P2| > 1.","section":"Section 4.1.2, Lemma 4.6"},{"comment":"The condition 'if Br_ij ∈ Xi ∪ Xj, for some r ∈ {i,j}' is hard to parse; please clarify the index convention and the intended condition.","section":"Section 4.1.3, Algorithm 7, line 24"},{"comment":"Reference [29] (Kaviani et al., WINE 2024) is missing page numbers or an article number; please complete the bibliographic details.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper's Section 3 is a solid, careful proof for the two-parallel-edges case, and the overall framework is promising. The main concern is that Section 4, which is essential for the stated theorems, is a roadmap with several unproven assertions; the gaps in Lemma 4.9 and the extension of Observation 2.1 to bundles are load-bearing. I believe the results are likely correct and the gaps are repairable, but the manuscript in its current form does not meet the bar for publication as a complete proof. The authors should be asked to either provide full proofs for the general case or clearly state the two-parallel-edge restriction as the main result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nTwo calls on this one. The paper reports EFX existence for three multigraph classes under general monotone valuations: bipartite, at most ceil(n/4)-1 neighbors, and shortest non-parallel cycle length at least 6. The second and third classes are new; the first is an independent proof of a result that Afshinmehr et al. and Bhaskar-Pandit also obtained. The matching-heavy machinery, especially the initial allocation that limits envy to at most half the agents and the 3-partition lemma for pairs without a common EFX-cut, is genuinely useful and worth knowing.\n\nNow the caveat. The general case with arbitrary parallel edges is not fully proved. Section 4 opens by calling itself a “proof roadmap,” and the gaps are load-bearing. Three in particular:\n\n1. In the proof of Lemma 4.9, Property (1) assumes that if i envies j in the matching allocation, then j must have received i’s most-valued bundle and (i,j) is in PVCP. That step is asserted, not derived. The likely fix—an exchange or weight argument in the maximum A-perfect matching—is absent.\n\n2. Step 2 claims Algorithm 8 is “essentially the same” as Algorithm 4, but Algorithm 8 can give a vertex a bundle that is a union of several neighboring bundles. Observation 2.1, which says an envied vertex’s bundle is relevant only to the envying vertex, is no longer obviously true, and no analogue is proved. Without it the EFX-preservation argument for the bundle case doesn’t close.\n\n3. Algorithm 7’s termination and the maintenance of Property (2) while Baux sets shrink are only sketched.\n\nOn top of that, the “w.l.o.g.” reductions—degree at least 2 and adding dummy edges—are not shown to be EFX-preserving when mapping back to the original instance. That is likely fixable, but it is another loose end.\n\nFor the restricted case of at most two parallel edges, Section 3 is carefully written and the lemmas look sound. But the advertised theorems, as stated for general multigraphs, are conditional on completing Section 4. This is a paper for the community to watch, and a serious editor should send it to review—with the expectation of major revision. I would not cite the general theorems as established until the roadmap is filled in.\n\nBest,\n[You]","headline":"New EFX existence results in multigraphs, but the advertised general theorems rest on an incomplete proof roadmap in Section 4.","tokens_in":32073,"tokens_out":5198,"would_cite":false,"duration_ms":49817,"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":"Three graph conditions guarantee EFX fair division in multigraphs.","keywords":["EFX allocations","fair division","multigraphs","envy-free up to any good","general monotone valuations","cut-and-choose protocol","graphical valuations","indivisible goods"],"falsifier":"A single counterexample would refute the claim: exhibit a bipartite multigraph with general monotone valuations in which every complete allocation has an agent who, after removal of any one good from another agent's bundle, still strictly envies that bundle. Since the paper's construction is explicit, one could also run it on small instances (say up to 6 vertices with up to 3 parallel edges per pair and valuations from a finite set) and check whether the final parking step ever fails to find a non-envied non-endpoint; a failure would identify a false lemma.","tokens_in":30998,"feed_emoji":"⚖️","tokens_out":6598,"duration_ms":68613,"temperature":0.7,"pith_summary":"This paper addresses the main open problem in fair division of indivisible goods: whether envy-free-up-to-any-good (EFX) allocations always exist. In the multigraph model, agents are vertices, goods are edges, and each agent only cares about incident edges. The paper proves three new existence theorems for general monotone valuations: EFX allocations always exist when the multigraph is bipartite, when every agent has at most ceil(n/4)-1 neighbors, or when the shortest cycle without parallel edges has length at least 6. These results extend the known frontier beyond simple graphs and beyond multigraphs with restricted additive valuations. The proof is constructive rather than efficient, relying on a cut-and-choose partitioning of parallel edges and a three-stage allocation procedure.","feed_headline":"EFX fair division always exists on three multigraph classes","feed_subtitle":"Bipartite, sparse-neighbor, and long-cycle multigraphs all admit envy-free-up-to-any-good allocations.","key_machinery":"The central primitive is the EFX-cut: for the parallel edges between two vertices, one vertex partitions them into two bundles so that, whichever bundle that vertex receives, removing any single good from the other bundle leaves a bundle no better than its own. The paper also uses the 'most valued set of potentially unallocated non-parallel bundles' (denoted UNP), which captures the best bundle an agent could form from unallocated relevant goods together with their own bundle, subject to containing no parallel bundles. These primitives feed a three-stage procedure: build a partial EFX orientation with controlled envy, run an envy-reduction loop that preserves the non-envied status of every already non-envied agent, and finally park every leftover bundle at a non-envied agent that is not an endpoint. In the bounded-neighbor case, the initial allocation comes from a maximum-weight matching in a bipartite graph between agents and their top-two EFX-cut bundles, with Hall's theorem ensuring the matching exists.","core_discovery":"The paper establishes that, in a multigraph where vertices are agents and edges are indivisible goods, a complete EFX allocation exists under general monotone valuations whenever the multigraph satisfies one of three structural conditions: (a) it is bipartite, (b) every vertex has at most ceil(n/4)-1 neighbors, or (c) every cycle consisting of non-parallel edges has length at least 6. The construction starts with a partial EFX orientation in which no agent prefers an unallocated edge or bundle to their own bundle, then repeatedly reallocates bundles so that any remaining unallocated goods can be given to non-envied agents who are not endpoints of those goods. The graph conditions guarantee that enough such 'parking' agents exist. Multiple parallel edges are handled by partitioning them into bundles via EFX-cuts, rather than treating each edge independently.","pith_inferences":["The real structural requirement in each proof is that there be enough non-envied vertices to park leftover bundles without creating cycles of envy, so other graph families with similar domination properties may also admit EFX allocations.","Because the cycle-length condition is obstructed only by triangles and 5-cycles of non-parallel edges, a natural next target is handling exactly those two cycle lengths, which might lead to EFX for all multigraphs.","The cut-and-choose primitive is not known to be polynomial, so these existence results do not by themselves give efficient algorithms; efficient or approximate EFX algorithms on these classes are a natural extension.","A testable extension is to run the construction on small random multigraphs with additive valuations to see whether the number of unallocated bundles ever exceeds the available non-envied parking vertices, which would pinpoint where the proof's slack lies."],"forward_implications":["Every bipartite multigraph, with any number of parallel edges, admits an EFX allocation under arbitrary monotone valuations.","Every multigraph in which each vertex has at most ceil(n/4)-1 neighbors admits an EFX allocation, covering all sufficiently sparse-neighborhood multigraphs regardless of parallel edges.","Every multigraph whose non-parallel cycles all have length at least 6 admits an EFX allocation, including all multicycles except those of length 3 and 5.","The construction shows that leftover edges need not be assigned to their endpoints; they can be parked at non-envied non-adjacent vertices, which is the key reason the graph restrictions are needed.","The bipartite case is settled for both additive and general monotone valuations, and the remaining open gap for general multigraphs is localized to small non-parallel cycles."],"supporting_citations":[{"why":"Supplies the cut-and-choose EFX protocol for two agents with general valuations, from which the paper's EFX-cut primitive is drawn.","marker":"[33]"},{"why":"Introduced the graph-valuation model and proved EFX existence for simple graphs, providing the orientation and envy-reduction framework that this paper generalizes to multigraphs.","marker":"[19]"},{"why":"Established EFX existence in multigraphs for restricted additive valuations, the setting whose valuation generality this paper extends.","marker":"[29]"},{"why":"Hall's theorem is used to show that the bipartite matching graph used in the bounded-neighbor initial allocation always has a perfect matching on the agent side.","marker":"[25]"}],"fun_headline_variants":["EFX allocations exist on three multigraph classes","Three multigraph conditions ensure EFX allocations","Bipartite, sparse, and long-cycle multigraphs admit EFX","EFX exists for bipartite, sparse, or long-cycle multigraphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the simplifying reductions are harmless: giving a degree-1 vertex its only incident edge, and adding zero-valued dummy edges so every adjacent pair of vertices has at least two parallel edges, do not change whether an EFX allocation of the original multigraph exists.","fun_headline_variants_meta":{"raw":{"variants":["EFX allocations exist on three multigraph classes","Three multigraph conditions ensure EFX allocations","Bipartite, sparse, and long-cycle multigraphs admit EFX","EFX exists for bipartite, sparse, or long-cycle multigraphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000923,"raw_usage":{"total_tokens":4010,"prompt_tokens":1052,"completion_tokens":2958,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":668,"completion_tokens_details":{"reasoning_tokens":2888}},"tokens_in":668,"tokens_out":2958,"duration_ms":23802,"temperature":1.0,"reasoning_tokens":2888,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T20:33:09.589262+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single counterexample would refute the claim: exhibit a bipartite multigraph with general monotone valuations in which every complete allocation has an agent who, after removal of any one good from another agent's bundle, still strictly envies that bundle. Since the paper's construction is explicit, one could also run it on small instances (say up to 6 vertices with up to 3 parallel edges per pair and valuations from a finite set) and check whether the final parking step ever fails to find a non-envied non-endpoint; a failure would identify a false lemma.","supporting_citations":[{"cited_title":"Fair allocation in graphs","cited_arxiv_id":null,"evidence_quote":"Introduced the graph-valuation model and proved EFX existence for simple graphs, providing the orientation and envy-reduction framework that this paper generalizes to multigraphs."},{"cited_title":"Almost envy-free allocation of indivisible goods: A tale of two valuations","cited_arxiv_id":null,"evidence_quote":"Established EFX existence in multigraphs for restricted additive valuations, the setting whose valuation generality this paper extends."}],"review_version":1}