{"id":"185f9c25-e008-427e-8899-71272547ce54","arxiv_id":"2506.09288","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For additive valuations over goods relevant to at most two agents, the paper proves existence of a 1/√2-approximate EFX allocation, improving the prior 2/3 bound.","lead":"This paper proves that in fair division settings where each good matters to at most two agents, a complete allocation always exists whose fairness guarantee is 1/√2, about 0.707, up from the previous best of 2/3. The result is an existence proof for a stronger approximate version of envy-freeness up to any good (EFX) on multigraph instances.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The imported basic feasible allocation lemma is false as stated: on a simple (2,\\infty)-bounded instance with two agents valuing only one shared good, no one-good-per-agent allocation can give every agent positive value, so Algorithm 1's initialization assumption fails.","rationale":"The reader's weakest_assumption correctly identifies the imported Kaviani et al. lemma. I agree, and the concern is sharper than merely 'unproven': the lemma as stated is contradicted by a simple (2,\\infty)-bounded instance. This is the most load-bearing point because the entire invariant proof starts from the basic feasible allocation; if an agent can have zero value in it, the weighted envy graph has an infinite/undefined edge, and Properties (iii)-(v) are not established. The theorem's truth is not disproved: the example still admits a complete EFX allocation, so a fix may be possible by preprocessing or by handling zero-value agents separately. I also reviewed the Rule 4 rotation argument flagged by the reader; after carefully following Algorithm 5, the reversal of C before pool allocation makes the proof's 'no good from P(j) is given to i' true, so that concern appears to be an exposition issue rather than a correctness hole. The Mahara theorem usage in Rule 3 has a suspicious dummy-agent footnote and should also be checked, but the initialization lemma is the primary blocker. Verdict remains CONDITIONAL pending a corrected initialization lemma or an additional argument covering instances without an all-positive matching.","tokens_in":13690,"tokens_out":42293,"duration_ms":380293,"concrete_test":"Check the Kaviani et al. lemma on the explicit instance above (agents 1,2,3; goods g,h,i; v1(g)=v2(g)=1; v3(h)=v3(i)=1; all other values 0). If the lemma is meant to hold for all (2,\\infty)-bounded inputs, this instance is a counterexample: since agents 1 and 2 both value only g, no one-good-per-agent allocation gives both positive value. If the authors instead intend an extra condition (e.g., existence of an all-positive matching), that condition must be stated and proven, and instances failing it must be handled separately in Theorem 4.9.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4.9 depends on the assertion in Section 2 ('By a result of Kaviani et al. (2024)') that a Nash-social-welfare-maximizing one-good-per-agent allocation can be chosen so every agent receives positive value. This lemma is not re-derived, and as stated it is false. Consider three agents and three goods g,h,i with v1(g)=v2(g)=1, v3(h)=v3(i)=1, and all other values 0. The instance is (2,\\infty)-bounded and every agent has a positive-valued good. In any one-good-per-agent allocation, g is assigned to exactly one of agents 1 and 2; the other receives h or i, which he values at 0. Hence every allocation (and every NSW-maximizer, since all have NSW 0) leaves some agent with zero value. The lemma's conclusion fails. Algorithm 1's initialization therefore cannot guarantee Properties (iii)-(v) in such instances: the weighted envy graph is undefined when a denominator is zero, and the invariant framework of Lemma 4.2 onward does not start. This is a load-bearing gap in the proof of the central claim, even though the theorem itself may be true (an EFX allocation exists in this example by giving g to one agent and h,i to agent 3).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fair allocation of indivisible goods with additive (2,∞)-bounded valuations, equivalently represented as multigraphs. It presents Algorithm 1, which maintains five invariants while applying five update rules, and claims in Theorem 4.9 that the algorithm always returns a complete (1/√2)-EFX allocation, improving the previous 2/3-approximation for this class. The proof is built on a weighted envy graph, a cycle classification, and an imported 'basic feasible allocation' lemma from the authors' earlier work (Kaviani et al., 2024), used to initialize the algorithm with one positive-valued good per agent.","tokens_in":13996,"tokens_out":12045,"duration_ms":137549,"significance":"If the main theorem is correct, it is a meaningful quantitative improvement for a natural bounded-valuation fair-division model and gives a concrete, structural algorithm rather than a nonconstructive existence argument. The invariant framework and the detailed case analysis for cycles are valuable ingredients. However, the proof currently rests on an initialization lemma that is false as stated, and the proof of Rule 4 contains an unjustified claim about rotated heavy edges; as a result, the central theorem is not established by the manuscript in its present form. The paper does not provide machine-checked proofs or code, so the correctness of the lengthy case analysis rests entirely on the written arguments.","major_comments":[{"comment":"The assertion that the basic feasible allocation can be chosen so that every agent receives a positive-valued good is false as stated. Consider N={1,2,3}, M={g,h,i}, with v1(g)=v2(g)=1, v3(h)=v3(i)=1, and all other singleton values 0. This instance is additive and (2,∞)-bounded. In any one-good-per-agent allocation, g is assigned to exactly one of agents 1 and 2, and the other receives h or i, which he values at 0. Hence every NSW-maximizing one-good-per-agent allocation gives some agent value 0, contradicting the initialization premise. Since the weighted envy graph G_X is defined via ratios vi(Xj)/vi(Xi), this makes the graph undefined at initialization and prevents Properties (iii)–(v), and therefore Lemmas 4.2–4.8 and Theorem 4.9, from being applied to the instance. The theorem may still be true, but the proof as written does not cover all (2,∞)-bounded instances.","section":"Section 2, Algorithm 1 initialization"},{"comment":"The proof of Property (i) for Rule 4 contains an unjustified step about rotated heavy edges. The text says that after the rotation, for the incoming edge j→i, 'i receives j's previous bundle' and 'since j→i is a heavy edge', j does not √2-envy i. After a rotation, however, the new edge j→i has weight v_j(X_i^new)/v_j(X_j^new), which equals v_j(X_j^old)/v_j(X_h^old) for the predecessor h of j; this is not the reciprocal of the old edge i→j, and the heaviness of the old edge i→j does not by itself bound this ratio. The conclusion may be recoverable from a different edge, but the argument as written is a gap in the proof that Rule 4 preserves the invariants.","section":"Lemma 4.7, Rule 4"}],"minor_comments":[{"comment":"The text says 'we focus on the special case where p=2 and q=1', but the abstract and Theorem 4.9 claim (2,∞)-bounded instances. This should be corrected to q=∞, since the algorithm and lemmas do not appear to use q≤1.","section":"Section 2, paragraph on (p,q)-bounded valuations"},{"comment":"In the case vi(A)<vi(B), the pseudocode first assigns X_i* ← B and then immediately overwrites X_i* ← A. The intended else-branch is missing; as written, the algorithm does not implement the described choice of the more valuable bundle.","section":"Algorithm 3, lines 8–10"},{"comment":"The reduction to Mahara (2023) via dummy agents with infinite-valued dummy goods is outside the additive real-valuation model stated in the paper. Please replace it with a valid reduction or a direct two-agent argument (e.g., using known complete EFX guarantees for two agents).","section":"Section 3, Rule 3 footnote"},{"comment":"The restatement says the agents have 'at most two distinct valuation functions' but the footnote refers to an additional assumption in Mahara (2023) that each valuation is shared by at least two agents; the relationship between these statements should be clarified.","section":"Theorem 4.4 restatement"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the imported basic feasible allocation lemma from the authors' own prior work, which is used without proof and is false as stated. Since the authors are also the authors of the cited paper, they are in a position to either correct the statement, re-derive a valid version, or adjust the initialization to handle agents without a positive-valued one-good allocation. The Rule 4 rotation gap also needs a repair. The framework appears salvageable, but the current manuscript does not yet prove the claimed theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper genuinely improves the approximate EFX constant for (2,∞)-bounded instances from 2/3 to 1/√2, and the five-rule algorithm with its invariant structure is a real piece of work. Second, there is a load-bearing gap: the imported basic feasible allocation lemma from Kaviani et al. (2024) is false as stated, and the counterexample is small. So the main theorem is not proved by the current text.\n\nThe counterexample: three agents, three goods g,h,i. Agents 1 and 2 value g at 1, agent 3 values h and i at 1, everything else 0. This is (2,∞)-bounded. In any one-good-per-agent allocation, g goes to one of agents 1 and 2; the other must receive h or i and gets value 0. Hence no allocation of one good per agent gives everyone positive value. The paper's claim that a NSW-maximizing basic feasible allocation can be chosen with all-positive values fails. Since the weighted envy graph divides by vi(Xi), the algorithm cannot even initialize on such instances. This is not a missing proof; the asserted statement is wrong.\n\nThe rest of the proof may survive a fix: the invariant framework is carefully built, and the rules are plausible. The Rule 4 rotation argument in Lemma 4.7 is loose—after rotation the relevant edge weight is the reciprocal of a heavy edge, so the proof needs to be phrased in terms of the other direction—but that looks fixable. The reduction to Mahara's two-valuation theorem also deserves a clean write-up; using a dummy agent with infinite value is nonstandard and should be checked.\n\nMy advice: ask the authors to repair the initialization. They need either a correct version of the basic feasible allocation lemma (possibly with extra assumptions or a separate treatment of zero-value bundles) or a modified algorithm that handles zero-valued bundles directly. Once that's done, I expect the 1/√2 constant and the main structure to hold up, but I can't certify the theorem from the current manuscript.\n\nWho is this for: people working on EFX and (p,q)-bounded valuations. The paper is worth a serious referee, but my own verdict would be major revision: the new constant is real, the gap is concrete and narrow, and the fix is likely possible.","headline":"New 1/√2 EFX constant for multigraphs, but the proof rests on a false imported lemma about basic feasible allocations.","tokens_in":14487,"tokens_out":4217,"would_cite":false,"duration_ms":41047,"reading_group":"maybe","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 additive valuations over multigraph goods — where each good is relevant to at most two agents — a complete allocation that is (1/√2)-EFX always exists, improving the previous (2/3) guarantee.","keywords":["fair division","EFX","approximate envy-freeness","(p,q)-bounded valuations","multigraph goods","additive valuations","Nash social welfare","weighted envy graph"],"falsifier":"Enumerate all small (2,∞)-bounded additive instances (say, multigraphs with n ≤ 4 vertices and up to 8 edges with arbitrary positive weights), run Algorithm 1 as specified, and check whether any output contains agents i,j and a good g ∈ X_j with √2 · v_i(X_i) < v_i(X_j \\ {g}). One such instance would disprove Theorem 4.9. Independently, search for any (2,∞)-bounded instance where no one-good-per-agent allocation maximizing Nash social welfare gives every agent a positive-value good; that would break the initialization and the entire proof.","tokens_in":13550,"feed_emoji":"⚖️","tokens_out":9272,"duration_ms":87555,"temperature":0.7,"pith_summary":"This paper proves that in any fair-division instance where each good is valued positively by at most two agents (a multigraph whose vertices are agents and whose edges are goods), a complete allocation satisfying a 1/√2-approximate notion of envy-freeness up to any good (EFX) always exists. This improves the previous best guarantee of 2/3 for the same class. The result matters because EFX is a leading fairness notion for indivisible goods, and proving existence for structured but broad classes is the main avenue of progress while the general existence question remains open. The proof is constructive: an algorithm with five updating rules returns the allocation.","feed_headline":"Fair division improves to 1/√2-EFX for multigraph goods","feed_subtitle":"A five-rule algorithm guarantees complete allocations where envy is bounded by √2 after any good is removed.","key_machinery":"The argument is carried by the weighted envy graph $G_X$, with edge weights $w_X(i,j)=v_i(X_j)/v_i(X_i)$; an edge is heavy when its weight exceeds $1/\\sqrt{2}$ and light otherwise. The algorithm maintains a partition of agents into finalized and remaining groups, together with five invariants, of which the crucial one is that every remaining agent's bundle is relevant only to itself and at most one other remaining agent — this forces the zero-value envy graph to be a disjoint union of cycles. Five rules then resolve these cycles: pool-envy elimination (Rule 1), finalizing agents with no out-edges (Rule 2), handling 2-cycles via a two-agent EFX completion theorem of Mahara (2023) or a choice protocol (Rule 3), rotating bundles in homogeneous cycles and assigning relevant pool goods (Rule 4), and breaking heterogeneous cycles through a heavy/light three-agent pattern (Rule 5). Leftover goods are given to the last finalized agent.","core_discovery":"The paper's central claim is Theorem 4.9: for additive (2,∞)-bounded valuations — each good is relevant to at most two agents, with no bound on how many goods a pair shares — Algorithm 1 returns a complete (1/√2)-EFX allocation. Since every agent receives all goods, this shows the existence of complete allocations in which no agent β-strongly envies another for β=√2, i.e., after deleting any single good from a rival's bundle, the agent's own bundle is at least 1/√2 as valuable. This establishes 1/√2 ≈ 0.707 as the best known universal approximation factor for EFX over multigraph goods, improving the (2/3)-EFX guarantee of Amanatidis et al. (2024).","pith_inferences":["The technique likely extends to $(p,q)$-bounded instances with $p>2$, but the in-degree-at-most-one invariant that drives the cycle structure would need a different justification, so the constant would probably degrade with $p$.","The basic feasible allocation lemma is used as a black box; a direct proof or a counterexample for $(2,\\infty)$-bounded valuations would be the simplest way to test the robustness of the whole construction.","The paper gives no lower bound: it remains possible that the true best factor for this class is better than $1/\\sqrt{2}$; a brute-force search over small multigraphs could suggest whether the constant is tight."],"forward_implications":["Any additive instance on a multigraph — including parallel edges, i.e., multiple goods shared by the same pair — now has a guaranteed complete allocation that is $(1/\\sqrt{2})$-EFX, improving the previous $2/3$ factor.","The two-agent completion theorem enters as a black box in Rule 3, so whenever only two agents remain the algorithm actually produces an exact EFX allocation between them, not just an approximate one.","The invariant framework — finalized agents never $\\sqrt{2}$-envy the union of remaining bundles, and remaining bundles have in-degree at most one — is a reusable template for other approximate-EFX existence proofs.","The result closes one gap in the $(p,q)$-bounded landscape: for $p=2$, $q=\\infty$, the guarantee jumps from $2/3$ to $1/\\sqrt{2}$; exact EFX itself remains open even for this class."],"supporting_citations":[{"why":"Establishes the previous (2/3)-EFX guarantee that this paper improves; supplies the baseline comparison and the pushing-frontier framing.","marker":"Amanatidis et al. (2024)"},{"why":"Provides the basic feasible allocation lemma (existence of a one-good-per-agent maximum-Nash-welfare allocation with positive goods for every agent) used without proof in the initialization.","marker":"Kaviani et al. (2024)"},{"why":"Supplies Theorem 4.4, used in Rule 3 to extend a partial EFX allocation of two agents to a complete EFX allocation of all remaining goods.","marker":"Mahara (2023)"},{"why":"Introduced (p,q)-bounded valuations and proved EFX for (2,1)-bounded instances, the framework within which this paper works.","marker":"Christodoulou et al. (2023)"},{"why":"Introduced the weighted envy graph that the paper uses to define heavy/light edges and cycle structure.","marker":"Farhadi et al. (2021)"}],"fun_headline_variants":["Fair division improves to 1/√2-EFX for multigraphs","New best: 1/√2-EFX for multigraph fair division","Multigraph fair division: 1/√2-EFX achieved","Fairness boost: 1/√2-EFX surpasses 2/3-EFX","Algorithm guarantees 1/√2-EFX for (2,∞) valuations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The initialization relies on a lemma from Kaviani et al. (2024) — not re-proved here — that a maximum-Nash-welfare one-good-per-agent allocation can be chosen so that every agent receives a good of positive value; if that lemma fails for some (2,∞)-bounded instance, the invariants that the whole algorithm depends on can fail at the very first step.","fun_headline_variants_meta":{"raw":{"variants":["Fair division improves to 1/√2-EFX for multigraphs","New best: 1/√2-EFX for multigraph fair division","Multigraph fair division: 1/√2-EFX achieved","Fairness boost: 1/√2-EFX surpasses 2/3-EFX","Algorithm guarantees 1/√2-EFX for (2,∞) valuations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000625,"raw_usage":{"total_tokens":2861,"prompt_tokens":879,"completion_tokens":1982,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":495,"completion_tokens_details":{"reasoning_tokens":1872}},"tokens_in":495,"tokens_out":1982,"duration_ms":17790,"temperature":1.0,"reasoning_tokens":1872,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:55:39.561183+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all small (2,∞)-bounded additive instances (say, multigraphs with n ≤ 4 vertices and up to 8 edges with arbitrary positive weights), run Algorithm 1 as specified, and check whether any output contains agents i,j and a good g ∈ X_j with √2 · v_i(X_i) < v_i(X_j \\ {g}). One such instance would disprove Theorem 4.9. Independently, search for any (2,∞)-bounded instance where no one-good-per-agent allocation maximizing Nash social welfare gives every agent a positive-value good; that would break the initialization and the entire proof.","supporting_citations":[{"cited_title":"Pushing the Frontier on Approximate EFX Allocations","cited_arxiv_id":"2406.12413","evidence_quote":"Establishes the previous (2/3)-EFX guarantee that this paper improves; supplies the baseline comparison and the pushing-frontier framing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the basic feasible allocation lemma (existence of a one-good-per-agent maximum-Nash-welfare allocation with positive goods for every agent) used without proof in the initialization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 4.4, used in Rule 3 to extend a partial EFX allocation of two agents to a complete EFX allocation of all remaining goods."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced (p,q)-bounded valuations and proved EFX for (2,1)-bounded instances, the framework within which this paper works."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the weighted envy graph that the paper uses to define heavy/light edges and cycle structure."}],"review_version":1}