{"id":"3a009d49-3d23-462f-8d30-87ae98339682","arxiv_id":"2506.14149","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For two agents with monotone valuations, a maximal EF1 allocation of graph-conflicting items always exists for any graph and is efficiently computable; for three or more agents, existence fails and deciding it is NP-hard.","lead":"This paper proves that two people can always split conflicting items, represented as a graph, so that the split is both maximal and envy-free up to one item, for any conflict graph. It also shows that with three or more people such a split may not exist and that deciding whether it does is NP-hard.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the two-agent existence proof, the three-agent counterexample, and the NP-hardness reduction all re-derive cleanly.","rationale":"The reader's weakest-assumption flag correctly identifies Theorem 11's enumeration as the place where a gap would be most dangerous, since the three-agent counterexample underlies both the sharp existence dichotomy and the n = 3 NP-hardness result. I therefore focused my stress-test there. Reconstructing the argument, the enumeration is sound: maximality forces good 7 to be allocated; the recipient cannot receive goods 1 or 4; and goods 1 and 4 must themselves be allocated in every maximal allocation. The three cases by the number of Y-side goods received by agent 1 cover all possibilities, and the six allocations listed are exactly the maximal ones. Each is shown not to be EF1. I additionally re-checked the two-agent chain argument and found the proof of Lemma 3 correct under the ordered-adjacent definition; the maximum-weight maximal independent set S indeed has value at least that of every independent set X1, X2, since any independent set extends to a maximal independent set with no smaller monotone value. The NP-hardness reduction's YES and NO directions are both valid, including the use of λ = γ/t and the bound |A_{i'} ∩ X| < t. The chores section's equivalence, though stated tersely, is mathematically correct under the paper's definitions. The remaining issues are typographical and do not affect the central claims; therefore the ACCEPT verdict stands unchanged.","tokens_in":17682,"tokens_out":40262,"duration_ms":375675,"concrete_test":"Write a short brute-force program to enumerate all allocations of the 7-good instance in Theorem 11, filter to those that are valid (each bundle independent) and maximal (every unallocated good is adjacent to some good in every agent's bundle), and check whether any is EF1 under the stated valuation. If the enumeration returns exactly the six allocations listed in Figure 3 and none is EF1, the three-agent counterexample is confirmed independently of the hand case analysis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I re-derived the main positive result for two agents (Definitions 2–4, Lemmas 3–9, Theorem 6), the negative example for three agents (Theorem 11), and the hardness reduction (Lemma 15, Theorem 14). The most delicate step is the compressed case analysis in Theorem 11, where the paper lists six maximal allocations after several symmetry reductions. I checked that step carefully: because good 7 must be allocated and its recipient cannot take goods 1 or 4, the WLOG reduction to agent 1 receiving good 7 and choosing side Y is legitimate; goods 1 and 4 must be allocated in every maximal allocation; and the resulting cases (agent 1 receives zero, one, or two of {5, 6}) do indeed exhaust all maximal allocations. Each listed allocation fails EF1 under the stated valuation. I also checked the chores-transfer claim in Section 5: the asserted equivalence between EF1-for-chores under v and EF1-for-goods under −v is valid, and follows by contrapositive from the two ordered-pair directions of the respective definitions. The only issues I found are the known pseudocode typo in Algorithm 2 (line 6 should use Si, not S0) and a cross-reference typo in Section 5; neither affects the mathematical claims. No fitted parameters, circular reasoning, or missing justifications surfaced.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fair division of indivisible goods in which each agent's bundle must be an independent set in a conflict graph. For two agents, Theorem 6 establishes that a maximal EF1 allocation exists for every graph under identical monotone valuations, via a gapless chain of maximal allocations; Theorem 10 supplies a polynomial-time algorithm for additive valuations and a pseudo-polynomial-time algorithm for monotone valuations. For three agents, Theorem 11 gives a seven-good instance with identical monotone valuations that admits no maximal EF1 allocation; Proposition 12 gives additive counterexamples for n >= 4; and Lemma 15 reduces from Independent Set, yielding NP-hardness for every fixed n >= 3 (Theorem 14). Section 5 transfers the goods results to chores by a valuation-negation argument. The paper is self-contained and uses no fitted parameters or external numerical inputs beyond standard hardness results.","tokens_in":17864,"tokens_out":3856,"duration_ms":42032,"significance":"The two-agent result resolves the existence question for arbitrary conflict graphs, substantially generalizing the interval-graph result of Kumar et al., and the three-agent counterexample sharply locates the boundary of existence. The algorithms are concrete and checkable, and the reduction in Lemma 15 is stated generically, so any future constant-size counterexample automatically yields NP-hardness. The proofs of Lemma 3, Lemma 5, Theorem 6, the case analysis in Theorem 11, and the YES/NO directions of Lemma 15 are all transparent and I found them correct. The chore transfer is simple but cleanly argued. These are strong, publishable contributions.","major_comments":[],"minor_comments":[{"comment":"Line 6 of Algorithm 2 calls CHAIN EF1 (S0; G, v), but it should call CHAIN EF1 (Si; G, v); the same typo is also reflected in the surrounding text where the loop variable is i.","section":"Algorithm 2 (Section 3.5)"},{"comment":"The sentence 'the instances given in Theorem 12 and Proposition 11' has the theorem and proposition numbers reversed; it should refer to Proposition 12 and Theorem 11.","section":"Section 5"},{"comment":"In the sentence 'we must have v(S) < v(X_i^l \\ {g})', the left-hand side should be v(S_i), consistent with the subsequent inequality 'v(S_i) < (m-1)/m * v(X_i^l)'; as written, S is undefined at that point.","section":"Proof of Theorem 10 (Section 3.5)"},{"comment":"The assertion that the six allocations in Figure 3 exhaust all maximal allocations is load-bearing, and the case analysis is compressed: the text jumps from the WLOG reductions to 'there are only 6 maximal allocations to consider.' I verified the exhaustiveness, but adding a short table that justifies, for each case, why no other maximal allocation exists would make the proof much easier for readers to check independently.","section":"Proof of Theorem 11 (Section 4.1)"},{"comment":"The word 'NP-hardnesss' appears with a typo in both the Abstract and the Introduction; it should be 'NP-hardness'.","section":"Abstract and Introduction"},{"comment":"The first sentence of the proof should read 'Let (A1, A2) be a maximal EF1 allocation' rather than 'Let (A1, A2) a maximal EF1 allocation'.","section":"Proof of Theorem 1 (Section 3.1)"}],"recommendation":"minor_revision","confidential_remarks":"I found no mathematical correctness issues; the manuscript is suitable for publication after the local typo fixes described in the minor comments. The compressed case analysis in Theorem 11 was checked and is correct."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a strong paper and worth your time. It closes the two-agent existence question for maximal EF1 allocations on arbitrary conflict graphs, extending Kumar et al.'s interval-graph result to every graph. The proof machinery—relaxed ordered adjacency and gapless chains—is clean and clearly reusable. The algorithms are a nice bonus: polynomial for additive, pseudo-polynomial for monotone valuations.\n\nThe three-agent counterexample is the first of its kind and is correct, though the case analysis is compressed. The WLOG symmetries do cut down the enumeration, and I checked that the six maximal allocations are exhaustive; but a referee will want a bit more detail or a short verifier script to be fully comfortable. The NP-hardness result is also solid: the reduction from Independent Set is generic and elegant, with the lambda scaling and dummy goods doing exactly the right work. It turns any fixed negative instance into hardness, which is a nice contribution in itself.\n\nThe paper is self-contained. I saw no circularity, no fitted parameters, and no overclaiming. The chores transfer in Section 5 is terse but mathematically sound. The typos—Algorithm 2 using S0 instead of Si, and the cross-reference slip in Section 5—are cosmetic. The honest discussion of open cases, especially additive valuations for n=3, is a plus.\n\nWho should read this: anyone working on fair division under constraints, and possibly graph theorists interested in equitable coloring. The connection to Hajnal–Szemerédi is a nice hook. I would bring it to a reading group and cite it in my own work.\n\nMy recommendation: send it to peer review. It is a significant advance with proofs that hold up on close reading, and the compressed spot in Theorem 11 is fixable with exposition rather than a real gap. Accept with minor revisions.","headline":"This paper settles the two-agent maximal-EF1 existence question for arbitrary conflict graphs and adds a clean three-agent negative result plus NP-hardness; it deserves serious peer review.","tokens_in":18458,"tokens_out":1474,"would_cite":true,"duration_ms":18152,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","05C69","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For two agents with any conflict graph, a maximal EF1 allocation always exists.","keywords":["fair division","conflict graph","EF1","maximal allocation","independent set","monotone valuations","indivisible goods","chores"],"falsifier":"Run an exhaustive search over all maximal allocations of the 7-good instance in the three-agent counterexample (the graph $K_{3,3}$ plus item 7 with the given six-level valuation) and test each for EF1; if any maximal EF1 allocation is found, the counterexample is false. The search is finite and checkable by a short program, since every allocation is a subpartition into independent sets.","tokens_in":17423,"feed_emoji":"⚖️","tokens_out":9085,"duration_ms":89909,"temperature":0.7,"pith_summary":"The paper asks whether a set of indivisible goods with pairwise conflicts, represented by a graph whose edges forbid an agent from holding both endpoints, can still be divided fairly, where fairness means envy-free up to one good (EF1) and efficiency means the allocation is maximal (no unallocated good can be added to anyone's bundle). It answers this question positively for two agents with monotone (non-decreasing) valuations: a maximal EF1 allocation exists for every conflict graph, extending the previously known interval-graph case, and can be found in polynomial time for additive valuations and pseudo-polynomial time for monotone valuations. For three or more agents the picture changes sharply: there is a three-agent instance with identical monotone valuations in which no maximal EF1 allocation exists, and deciding existence is NP-hard for every fixed number of agents $n \\geq 3$. All of these results carry over to the allocation of chores.","feed_headline":"Two agents can always fairly split conflicting items","feed_subtitle":"Maximal EF1 exists for every conflict graph with two agents; three agents break the guarantee.","key_machinery":"The workhorse is the gapless chain: a sequence of maximal allocations $A^{(0)},\\ldots,A^{(k)}$ such that $v(A^{(0)}_1) \\geq v(A^{(0)}_2)$, $v(A^{(k)}_1) \\leq v(A^{(k)}_2)$, and each consecutive pair is ordered adjacent, meaning $|A^{(i-1)}_1 \\setminus A^{(i)}_1| \\leq 1$ and $|A^{(i)}_2 \\setminus A^{(i-1)}_2| \\leq 1$. Any gapless chain must contain an EF1 allocation. The proof is carried by a lemma showing that when the sign flips between adjacent allocations, one of the two is EF1, and by Algorithm 1, which constructs such a chain from any maximal independent set $S$ with $v(S) \\geq v(X_1)$ and $v(S) \\geq v(X_2)$.","core_discovery":"The central claim is that the obstruction to fair allocation under conflict constraints is not the graph but the number of agents. The proof builds a gapless chain of maximal allocations $A^{(0)},\\ldots,A^{(k)}$ for two agents: each step moves exactly one good from agent 1 to agent 2, and the first allocation favours agent 1 while the last favours agent 2. By monotonicity, some consecutive pair has the sign of $v(A_1) - v(A_2)$ flip, and a lemma shows that at least one allocation in that pair must be EF1. The paper constructs such a chain for any graph by starting from a value-maximal maximal independent set $S$ and scanning the remaining goods to form two independent sets $X_1, X_2$. On the negative side, the paper exhibits a 7-good instance on $K_{3,3}$ plus one extra item with identical monotone valuations where a case analysis reduces to six maximal allocations, all of which fail EF1, and it sketches a reduction from Independent Set that turns any constant-size negative instance into NP-hardness for fixed $n \\geq 3$.","pith_inferences":["The gapless-chain construction is not tied to interval graphs, so a natural test is whether a similar sign-flipping sequence can be built for other efficiency notions or for larger fixed numbers of agents.","The pseudo-polynomial bound for monotone valuations suggests that a strongly polynomial two-agent algorithm would need a different idea, since the current proof pushes the value of a maximal independent set upward by a factor of $m/(m-1)$ only in the additive case.","Because the paper's reduction converts any constant-size negative instance into NP-hardness, the open additive three-agent case is a single-instance question: finding one additive counterexample would simultaneously establish hardness for that setting."],"forward_implications":["For two agents with arbitrary conflict graphs and monotone valuations, maximal EF1 is guaranteed, subsuming the earlier interval-graph existence result.","The two-agent algorithms give a practical route to fair scheduling or office allocation when only two parties are involved, with polynomial time in the additive case.","No analogous guarantee can hold for three agents even with identical monotone valuations, so any general algorithm for $n \\geq 3$ must either restrict valuations further or settle for approximate existence.","Deciding whether a maximal EF1 allocation exists is NP-hard for every fixed $n \\geq 3$ (with additivity for $n \\geq 4$ and monotonicity for $n = 3$), so efficient universal decision procedures are out of reach unless $\\mathrm{P} = \\mathrm{NP}$.","Under uniform valuations, maximal EF1 allocations are maximal equitable partial colorings, so the paper's tree result provides a first step toward generalizing a classical equitable-coloring theorem."],"supporting_citations":[{"why":"The prior result this extends: existence of maximal EF1 for interval graphs and two agents with monotone valuations, whose chain-of-allocations proof is the template for the gapless chain.","marker":"[21]"},{"why":"Provided the earlier four-agent counterexample for complete bipartite graphs that the paper refines and uses as the base for the $n \\geq 4$ additive lower bound.","marker":"[18]"},{"why":"The standard result that EF1 allocations exist for monotone valuations without constraints; supplies the EF1 benchmark and the envy-removal definition.","marker":"[23]"},{"why":"The cut-and-choose protocol used to reduce the two-agent problem to identical valuations.","marker":"[9]"},{"why":"A classical bound on the number of maximal independent sets, which bounds the iteration count of the pseudo-polynomial algorithm.","marker":"[24]"},{"why":"The Independent Set problem from which the NP-hardness reduction constructs its hard instances.","marker":"[20]"}],"fun_headline_variants":["Two agents always get a fair split of conflicting items","Conflict graphs no obstacle: two agents always EF1","Two-agent fair division: any conflict graph works","EF1 for two agents on every conflict graph, even chores"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step is the finite enumeration in the three-agent counterexample: after fixing good 7 with agent 1 and applying symmetries, the proof asserts that every maximal allocation is one of six listed allocations, so a missed maximal allocation could hide an EF1 allocation and break the negative result.","fun_headline_variants_meta":{"raw":{"variants":["Two agents always get a fair split of conflicting items","Conflict graphs no obstacle: two agents always EF1","Two-agent fair division: any conflict graph works","EF1 for two agents on every conflict graph, even chores"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000273,"raw_usage":{"total_tokens":1638,"prompt_tokens":951,"completion_tokens":687,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":632}},"tokens_in":567,"tokens_out":687,"duration_ms":7327,"temperature":1.0,"reasoning_tokens":632,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:22:41.572481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search over all maximal allocations of the 7-good instance in the three-agent counterexample (the graph $K_{3,3}$ plus item 7 with the given six-level valuation) and test each for EF1; if any maximal EF1 allocation is found, the counterexample is false. The search is finite and checkable by a short program, since every allocation is a subpartition into independent sets.","supporting_citations":[{"cited_title":"Fair Interval Scheduling of Indivisible Chores","cited_arxiv_id":"2402.04353","evidence_quote":"The prior result this extends: existence of maximal EF1 for interval graphs and two agents with monotone valuations, whose chain-of-allocations proof is the template for the gapless chain."},{"cited_title":"Hummel and M","cited_arxiv_id":null,"evidence_quote":"Provided the earlier four-agent counterexample for complete bipartite graphs that the paper refines and uses as the base for the $n \\geq 4$ additive lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The standard result that EF1 allocations exist for monotone valuations without constraints; supplies the EF1 benchmark and the envy-removal definition."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The cut-and-choose protocol used to reduce the two-agent problem to identical valuations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"A classical bound on the number of maximal independent sets, which bounds the iteration count of the pseudo-polynomial algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Independent Set problem from which the NP-hardness reduction constructs its hard instances."}],"review_version":1}