{"id":"33e3c6e8-1646-45dd-8af1-bb031db19e80","arxiv_id":"2608.08864","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A deterministic tie-breaking rule in the Plaut-Roughgarden repair procedure yields at most m transfers for monotone cancelable valuations, giving polynomial-time EFX repair.","lead":"A simple tie-breaking rule makes the classic Plaut-Roughgarden envy-free repair procedure run in polynomial time for a broad class of valuations, instead of an exponential worst case. The result also yields a better fairness guarantee for allocating chores, and a new example shows the valuation class strictly exceeds additive valuations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1.2 depends on an unproven α-MMS extension of the Lin–Wu–Zhou phases; Theorem 1.1 itself is sound.","rationale":"I independently checked the two central lemmas of Theorem 1.1. In Lemma 3.2, Case 1 correctly uses cancelability to compare singleton values after removing the common sub-bundle, and Case 2 correctly shows the next transferred item was already eligible in the previous iteration, so the fixed-order maximality gives the strict decrease. Lemma 3.1's max-preservation also follows from cancelability via Observation 2.2. Thus the main repair theorem is sound. The separation example in Proposition 5.1 is also valid: the three inequalities a>b+c, c+d>a+b, and b+e>a+c yield d+e>a+b+c, contradicting the reversed comparison abc≻de. The only substantive defect is the unproven assertion in Lemma 4.2 that the Lin–Wu–Zhou phases extend from exact MMS to α-MMS. The paper itself flags this as an omitted proof, and the application in Corollary 1.2 depends on it. I therefore keep the reader's CONDITIONAL verdict; the concern does not invalidate Theorem 1.1 but leaves the chores application unsupported until the α-MMS extension is supplied.","tokens_in":14876,"tokens_out":19429,"duration_ms":193282,"concrete_test":"Obtain the full Lin–Wu–Zhou paper and symbolically re-derive their Lemmas 3.4, 3.5, and Theorem 4.1 with an α-MMS partition of M^+ as the input, tracking every inequality that uses exact MMS. In particular, verify that for every agent i, the cost of the bundle output by Phases 2/3 is at most α·MMS_i(M), not merely α·MMS_i(M^+) plus an unabsorbed cost term from M^0. If the original proof relies on equality in the MMS bound to place the M^0 chores, then the α extension is not established and Corollary 1.2 needs a separate argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main repair theorem appears correct: Lemma 3.1 uses cancelability to preserve min and max bundle values, and Lemma 3.2 forces consecutive transferred items to strictly decrease in the fixed order, so at most |S| transfers occur. The load-bearing gap is in the advertised application. Corollary 1.2 combines a (1+ε)-MMS partition of M^+, the polynomial PR repair, and Lemma 4.2, which asserts that Phases 2 and 3 of Lin, Wu, and Zhou preserve α-MMS and EFX while bounding social cost by 2·OPT. The proof of Lemma 4.2 is a single sentence: the exact-MMS guarantees are in LWZ26 Lemmas 3.4/3.5, and 'one can easily extend the proof to work with α-MMS instead of exact.' No extension is supplied. This matters because the final allocation adds chores from M^0 in Phases 2/3, which can only increase each agent's cost. Preserving α-MMS with respect to the original item set M requires an inequality of the form final_cost(i) ≤ α·MMS_i(M); it is not automatic from having started with an α-MMS partition of M^+ and keeping its maximum cost bounded. If the original exact-MMS argument uses equality or tightness of the MMS partition to absorb the M^0 chores, the α extension may fail or require a different constant. Since the paper's headline improvement over the 4/3-MMS guarantee rests on this unproved extension, the application is conditional on closing this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Plaut-Roughgarden (PR) EFX-repair dynamic for agents with identical valuations. It shows that, for monotone cancelable valuations, a single deterministic tie-breaking rule—always transfer the highest-ranked eligible item, where the ranking is consistent with singleton values—makes the dynamic terminate after at most |S| transfers, where S is the set of items being partitioned. The resulting partition is EFX-feasible, and the repair does not decrease the minimum bundle value nor increase the maximum bundle value (Theorem 1.1). The proof is via two lemmas: Lemma 3.1 preserves the min and max under cancelability, and Lemma 3.2 shows consecutive transferred items strictly decrease in the fixed order. The paper then applies this repair to restricted additive chores, combining a Hochbaum-Shmoys scheduling PTAS with the framework of Lin, Wu, and Zhou to claim an EFX, (1+ε)-MMS, and 2-approximate social-cost allocation (Corollary 1.2). Finally, it constructs a five-item monotone cancelable ordering with no additive representation (Proposition 5.1).","tokens_in":15198,"tokens_out":10905,"duration_ms":111467,"significance":"If the main theorem holds, it is a genuinely useful contribution: it gives the first polynomial-time implementation of the canonical PR repair dynamic for a class strictly containing additive valuations, with strong monotonicity guarantees that make it a modular subroutine. The proof is simple, self-contained, and appears correct; the at-most-|S| transfer bound is sharp and does not depend on value magnitudes. The separation result in Proposition 5.1 is also valuable, as it shows cancelable orderings are strictly more expressive than additive ones, settling a question that is natural given the parallel between the two classes in EFX results. The chore application, however, depends on an unproven and nontrivial extension of the Lin-Wu-Zhou framework to approximate MMS, and this gap currently prevents the advertised improvement over the 4/3-MMS guarantee from being fully established.","major_comments":[{"comment":"The proof of Lemma 4.2 is not sufficient for the claimed use in Corollary 1.2. The sentence 'One can easily extend the proof to work with α-MMS instead of exact' is not a proof, and the issue is load-bearing. Phases 2 and 3 add chores from M^0 to the bundles of the α-MMS partition of M^+, so an agent's final cost c_i(A_i) can exceed the cost of her M^+ bundle. To conclude α-MMS with respect to the original item set M, one needs an inequality of the form c_i(A_i) ≤ α·MMS_i(M). This does not follow automatically from starting with an α-MMS partition of M^+ and preserving a bound on the cost of that partition, because MMS_i(M) can be larger than MMS_i(M^+) and the added chores may consume that slack unevenly. Since the privacy of Corollary 1.2 rests on this extension, the authors must either supply a complete proof, give a precise citation with theorem numbers showing that [LWZ26] already proves the α-MMS version, or restate Corollary 1.2 as conditional.","section":"Section 4, Lemma 4.2"},{"comment":"The social-cost bound of 2·OPT(I) is also imported from Lemma 4.2, whose proof is not provided. If the exact-MMS argument in [LWZ26] uses the tightness of the MMS partition in an essential way, the same gap that threatens the α-MMS preservation could also affect the 2-approximation guarantee. The paper should make explicit which parts of the 2·OPT proof survive when Phase 1 is replaced by the PR repair of an approximately optimal MMS partition rather than an exact one.","section":"Section 4, Corollary 1.2"}],"minor_comments":[{"comment":"The phrase 'an an α-MMS partition' contains a duplicated article and should be corrected.","section":"Section 4, Lemma 4.1"},{"comment":"The sentence listing PR as a useful subroutine appears twice consecutively with slightly different citation lists; one of the two should be deleted.","section":"Section 1"},{"comment":"The separation result is called Proposition 1.3 in the abstract and Proposition 5.1 in Section 5; the numbering should be made consistent.","section":"Abstract and Section 5"},{"comment":"The notation 'X'_j = X_j \\ g ⪯_j X_j' introduces the symbol ⪯_j without definition; the argument is clear from monotonicity and should be stated without new notation.","section":"Proof of Lemma 3.1"},{"comment":"In line 4, the phrase 'where X_j is the current bundle containing g' is slightly ambiguous because X_j was already used for the bundle from which g is transferred; rewording to 'and let X_j denote the current bundle that contains g' would improve clarity.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The core result, Theorem 1.1, appears sound and well proved, and the separation example is convincing. The only real obstacle is the unproven α-MMS extension in Lemma 4.2, on which the paper's headline application depends. Since the manuscript cites [LWZ26] as 'to appear', the referee cannot independently verify the extension from the cited text. If the authors can provide the missing proof—or show that a cited lemma already contains it—the paper would be acceptable. Otherwise the application section should be revised to state the conditional nature of the (1+ε)-MMS claim or to remove it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. Theorem 1.1 is sound and is the real contribution. The tie-breaking rule — fix an order consistent with singleton values and always transfer the highest-ranked eligible item — makes consecutive transferred items strictly decrease, so at most m transfers. I checked the two lemmas, including the case where the next transfer comes from the bundle that just received the previous item; Lemma 3.2’s argument with repeated cancellation works. Lemmas 3.1 and 3.2 together give min-value non-decrease and max-value non-increase, which is exactly what a repair subroutine needs.\n\nThe cancelable extension is genuinely new: the concurrent work disclosed in the paper covers additive only, and no prior version of the PR repair had a polynomial bound even for additive. The separation example in Section 5 also checks out — the three comparisons force d+e > a+b+c, contradicting the swapped pair. I don’t see a problem with the AI-generated proof being noted in the text; the proof is short and correct.\n\nThe soft spot is the application. Corollary 1.2 leans entirely on Lemma 4.2, and the proof of that lemma is one sentence asserting that Phases 2 and 3 of Lin–Wu–Zhou extend from exact MMS to α-MMS. No extension is shown. This matters because Phases 2 and 3 add the chores from M^0, which can only raise an agent’s final cost. Starting from an α-MMS partition of M^+ and not increasing its max cost does not, by itself, imply each agent ends up at α·MMS over the original M; the cited exact-MMS argument may rely on tightness that an approximate partition does not have. Until that step is written out, the (1+ε)-MMS improvement over 4/3 is conditional. Theorem 1.1 does not depend on this, so the main result stands either way.\n\nThe citation pattern looks normal, and the paper is honest about BF26. I’d send it to a serious referee; the report should ask for a real proof of the α-MMS extension in Lemma 4.2, or a weakened statement that the application is conditional on it. Anyone working on EFX repair dynamics or restricted additive chores should read this, and I would cite it for Theorem 1.1.","headline":"The main EFX-repair theorem is sound and genuinely useful; the headline chores corollary rests on an unproved α-MMS extension of a cited result and needs a fix before that claim is accepted.","tokens_in":15711,"tokens_out":3463,"would_cite":true,"duration_ms":37242,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single tie-breaking rule turns the standard EFX repair procedure into a polynomial-time algorithm for cancelable valuations.","keywords":["EFX","envy-free up to any good","cancelable valuations","fair division","repair procedure","restricted additive chores","minmax share","polynomial-time algorithm"],"falsifier":"Run Algorithm 1 over all monotone cancelable set functions on a small ground set (four or five items) and all starting partitions: any instance that needs more than $|S|$ transfers, or that decreases the minimum bundle value or increases the maximum bundle value, would refute Theorem 1.1. Separately, run the [L WZ26] Phases 2 and 3 starting from a merely $(1+\\varepsilon)$-MMS partition of $M^+$; if the final allocation ever fails to be $(1+\\varepsilon)$-MMS or EFX, Corollary 1.2 collapses.","tokens_in":14661,"feed_emoji":"⚖️","tokens_out":10144,"duration_ms":93989,"temperature":0.7,"pith_summary":"This paper addresses a gap in the standard envy-free-up-to-any-good (EFX) repair dynamic: the leximin++ repair procedure from [PR20] repeatedly transfers an eligible item to a minimum-valued bundle and is known to terminate, but no polynomial bound on transfers was known, even for additive valuations. The paper proves that a single deterministic tie-breaking rule—always transfer the highest-ranked eligible item in an order consistent with singleton values—makes the same repair terminate after at most $|S|$ transfers for every monotone cancelable valuation over a set $S$. Along the way it preserves two invariants: the minimum bundle value never drops and the maximum bundle value never rises. The paper then uses this repair as a module to obtain, for restricted additive chores, a polynomial-time allocation that is simultaneously EFX, $(1+\\varepsilon)$-MMS, and a 2-approximation to optimal social cost. It closes with a five-item cancelable ordering with no additive representation, showing the extension beyond additivity is real.","feed_headline":"One tie-breaking rule makes EFX repair polynomial-time","feed_subtitle":"For cancelable valuations, always moving the highest-ranked eligible item cuts transfers to at most one per item.","key_machinery":"The carrying mechanism is the fixed strict item order $\\triangleleft$ consistent with singleton values, combined with the tie-breaking rule “transfer the $\\triangleleft$-maximum eligible item.” The key lemma shows that the item transferred in iteration $\\ell+1$ is strictly below the item transferred in iteration $\\ell$ in this order: the proof splits into the case where the new item comes from the bundle that just received the previous item (canceling common items yields $v(g_{\\ell+1}) < v(g_\\ell)$) and the case where it comes from another bundle (then it was already eligible earlier and was passed over because $g_\\ell$ ranked higher). This makes the order a progress measure that caps the number of transfers at $|S|$ without any assumption on value sizes.","core_discovery":"The central claim is Theorem 1.1: for a monotone cancelable set function $v$ over $m$ items and any $n$-partition $X$ of a subset $S$, Algorithm 1—always moving the highest-ranked eligible item to a minimum-valued bundle—stops after at most $|S|$ transfers and returns an EFX-feasible partition $Y$ with $\\min_v(Y) \\geq \\min_v(X)$ and $\\max_v(Y) \\leq \\max_v(X)$. The proof is self-contained and rests on a monotone progress measure: consecutive transferred items strictly decrease in the fixed item order, so each item can be transferred at most once. Cancelability is used to cancel common items when comparing bundles, which yields both the strict descent of transferred items and the non-increase of the maximum bundle value. The running bound is independent of value magnitudes and works in the value-oracle model.","pith_inferences":["If the same descent argument works for weakly well-layered or other non-cancelable valuation classes, the order-based progress measure could yield polynomial repair there; the paper does not investigate this.","The unproved extension of [L WZ26]'s Phases 2 and 3 to $\\alpha$-MMS is the main risk to Corollary 1.2; verifying or refuting that extension would settle whether the EFX plus $(1+\\varepsilon)$-MMS guarantee is actually available.","Because the repair preserves the maximum bundle value, it may combine with other efficiency notions stated in terms of the worst bundle, beyond the social-cost application.","The five-item separation suggests that other algorithmic results known only for additive valuations may deserve re-examination for cancelable valuations, where the same EFX-style guarantees could hold by different proofs."],"forward_implications":["For every monotone cancelable valuation, any prescribed partition of a subset $S$ can be repaired to EFX in polynomial time, with the minimum bundle value never decreased and the maximum bundle value never increased.","The repair is a modular subroutine: any construction that yields a partition with a bound on its most valuable (or most costly) bundle can be post-processed to add EFX without losing that bound.","For restricted additive chores, for every fixed $\\varepsilon > 0$, a polynomial-time allocation exists that is EFX, $(1+\\varepsilon)$-MMS, and a 2-approximation to the optimal social cost, improving the previous polynomial-time $4/3$-MMS guarantee.","Cancelable valuations are strictly more expressive than additive valuations even at the ordinal level, so the polynomial repair covers a genuinely larger class than the additive special case."],"supporting_citations":[{"why":"Introduced the leximin++ repair dynamic that Algorithm 1 modifies, and provided the termination argument that gives no polynomial bound.","marker":"[PR20]"},{"why":"Named this transfer-to-minimum-bundle dynamic the PR algorithm and supplied the terminology used throughout the paper.","marker":"[AAC+23]"},{"why":"Provided the restricted-additive-chores framework whose Phases 2 and 3 the application reuses, as well as the previous 4/3-MMS polynomial guarantee.","marker":"[L WZ26]"},{"why":"Supplied the scheduling PTAS that computes a (1+epsilon)-MMS partition of the common-positive-cost chores in polynomial time.","marker":"[HS87]"},{"why":"Introduced the EFX notion whose feasibility is the target property of the repaired partition.","marker":"[CKM+19]"}],"fun_headline_variants":["EFX repair now polynomial for cancelable valuations","One tie-break rule makes EFX repair run in O(m)","Cancelable valuations: EFX repair in at most m transfers","Deterministic tie-break ensures polynomial EFX repair","Tie-breaking to fix EFX: at most one transfer per item"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The repair theorem itself assumes the valuation is monotone and cancelable; the chores application adds a second, unproven assumption, namely that the two final phases of the cited [L WZ26] construction still work when the starting partition is only close to optimal, rather than exactly at the best possible maximum bundle value.","fun_headline_variants_meta":{"raw":{"variants":["EFX repair now polynomial for cancelable valuations","One tie-break rule makes EFX repair run in O(m)","Cancelable valuations: EFX repair in at most m transfers","Deterministic tie-break ensures polynomial EFX repair","Tie-breaking to fix EFX: at most one transfer per item"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000628,"raw_usage":{"total_tokens":2909,"prompt_tokens":959,"completion_tokens":1950,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":1865}},"tokens_in":575,"tokens_out":1950,"duration_ms":13379,"temperature":1.0,"reasoning_tokens":1865,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:23:14.579611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 over all monotone cancelable set functions on a small ground set (four or five items) and all starting partitions: any instance that needs more than $|S|$ transfers, or that decreases the minimum bundle value or increases the maximum bundle value, would refute Theorem 1.1. Separately, run the [L WZ26] Phases 2 and 3 starting from a merely $(1+\\varepsilon)$-MMS partition of $M^+$; if the final allocation ever fails to be $(1+\\varepsilon)$-MMS or EFX, Corollary 1.2 collapses.","supporting_citations":[],"review_version":1}