{"id":"b7c6890a-5407-4187-a404-d8612453420f","arxiv_id":"2501.04550","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For bi-valued chores, (2-1/k)-EFX and PO allocations exist in polynomial time, and for {1,2} instances, exact EFX and PO allocations are claimed.","lead":"This paper gives polynomial-time algorithms for fair and efficient allocations of indivisible chores when every chore costs each agent either 1 or k, improving the best known fairness guarantee from 3-EFX to (2-1/k)-EFX while keeping Pareto optimality. For the special case k=2 it claims an exact EFX and Pareto-optimal allocation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.9 is unsupported: Algorithm 2 line 18 (X_i <- X_i + e1 - e2 with i in U) directly contradicts 'only raised agents give out items,' so the proof that the envied agent j is unraised, and hence Theorem 4.13, does not go through.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing defect: Lemma 4.9 asserts that unraised agents never give out items, but Algorithm 2 line 18 explicitly performs X_i <- X_i + e1 - e2 for i in U. That is a direct contradiction within the text, not a matter of interpretation. I checked whether the false invariant could be replaced by a weaker statement that still proves j in U. The proof's case analysis depends on comparing the last rounds in which i's and j's earnings change, and it assumes i's bundle only ever grows before the relevant time. Once i can lose e2 while gaining e1, the premise 'Xi = X0_i' in the first case and the definition of ti in the second case both break; no alternative argument is supplied. Since Algorithm 3's MPB-feasibility and the PO guarantee rely on Lemma 4.7 being applicable to j, the proof of Theorem 4.13 is incomplete. I therefore agree with the reader's REJECT verdict: the preprint as written does not establish the claimed EFX-and-PO computation for {1,2}-instances. I do not claim the theorem is false; a repaired proof of Lemma 4.9 could change the verdict. The first result, Theorem 3.14, appears well argued and is not affected by this concern.","tokens_in":18246,"tokens_out":6339,"duration_ms":66085,"concrete_test":"Implement Algorithm 2 exactly as stated in Section 4.1.2 and exhaustively run it on all small {1,2}-instances (e.g., n <= 4, m <= 8), logging every update to U and every bundle change. Check whether any execution reaches line 18 with i in U, i.e., whether an unraised agent's bundle is decremented. If it is, the invariant 'only raised agents give out items' is refuted and Lemma 4.9 has no valid proof. To test the theorem-level consequence, for each output equilibrium check whether Algorithm 3 finds an unraised i that is pEF1 but not EFX toward some j, and verify whether the prescribed reallocation places an item inside MPB_j. If j is raised and the high-payment item is not MPB for j, Invariant 4.8 fails and Pareto optimality is no longer guaranteed. A single such instance settles the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Section 4 is Theorem 4.13, and its proof depends on Lemma 4.9. The fourth bullet of Lemma 4.9 asserts j in U. To prove it, the authors write: 'Recall that i is unraised, which implies that i has never lost any item during Algorithm 2 (only raised agents give out items).' This invariant is false as stated. Algorithm 2, line 18, updates X_i <- X_i + e1 - e2, where i in U, so an unraised agent does give out an item (e2) and receives e1 in exchange. Thus the dichotomy used in the proof of Lemma 4.9 - either i has never received any item, or we consider the last round ti in which i's earning increased - omits the possibility that i has both received and lost items. Consequently, the subsequent earning-history argument showing tj < ti, and hence j in U, does not follow. This is load-bearing: Algorithm 3 relies on j in U to apply Lemma 4.7 and conclude that the high-payment item e_i is MPB for j. Without j in U, the reallocation in Algorithm 3 may give j an item outside its MPB set, breaking the equilibrium property and hence Pareto optimality. Theorem 4.13 is therefore unsupported as written. This is a proof gap, not a demonstration that the theorem is false; a corrected invariant or a different argument for j in U could repair the result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fair and efficient allocations of indivisible chores with bivalued costs ({1,k}). The authors first design an algorithm that, starting from a pEF1 integral equilibrium, performs MPB-feasible item swaps to compute a (2-1/k)-EFX and PO allocation in polynomial time, improving the prior 3-EFX guarantee. They then claim that for k=2, the same framework yields exact EFX and PO allocations in polynomial time. The first result is supported by a detailed invariant-based proof; the second result, presented in Section 4, relies on a Lemma 4.9 whose proof contains a false assertion about the behavior of unraised agents in the equilibrium algorithm.","tokens_in":18487,"tokens_out":9957,"duration_ms":82596,"significance":"If the (2-1/k)-EFX guarantee is correct, it is a noteworthy improvement over the state-of-the-art 3-EFX result for bivalued chores, and the technique of avoiding fractional rounding in favor of integral equilibrium reallocations is likely to be useful. The claimed EFX+PO result for {1,2}-instances would be a significant existence and computation result, as exact EFX+PO allocations for chores are known only for very restricted cases. However, the proof gap in Lemma 4.9 currently leaves the second theorem unsupported. The paper also provides a self-contained proof of the First Welfare Theorem in this context and makes appropriate references to prior equilibrium constructions.","major_comments":[{"comment":"The proof of the fourth bullet of Lemma 4.9 rests on the assertion that 'only raised agents give out items' during Algorithm 2. This invariant is false as written: Algorithm 2 line 18 updates X_i ← X_i + e1 − e2 with i ∈ U, so an unraised agent can give away an item. Consequently, the dichotomy in the proof—that i has either never received any item or has received some items—omits the possibility that an unraised agent has both received and lost items. The subsequent earning-history argument that establishes t_j < t_i depends on this dichotomy and does not go through. Without the conclusion j ∈ U, Algorithm 3 cannot rely on Lemma 4.7 to guarantee that the high-payment item e_i lies in MPB_j, so the equilibrium property (and hence Pareto optimality) may be lost; the termination proof of Theorem 4.13 also uses j ∈ U. This is a load-bearing gap for Theorem 4.13.","section":"§4.1.2, Algorithm 2; §4.2, Lemma 4.9"},{"comment":"The proof of Lemma 4.12 asserts that 'by Lemma 4.7 and 4.9, the new item received by an agent must be an MPB item.' Since Lemma 4.9's proof is incomplete (as explained above), the claim that both reallocated items are MPB-feasible is not established. In particular, the case in Algorithm 3 line 7 where no low-payment item exists in X_j relies on j ∈ U to ensure e_i ∈ MPB_j via Lemma 4.7; without this, the pEF1 equilibrium invariant in Invariant 4.8 may fail, and the PO guarantee of the output allocation is unsupported. Thus the correctness of Algorithm 3 is not proven as written.","section":"§4.2, Lemma 4.12 and Theorem 4.13"}],"minor_comments":[{"comment":"The text contains several spacing artifacts (e.g., 'th e', 'it em', 'a llocation') that should be cleaned up in the final version.","section":"Abstract and Introduction"},{"comment":"The notation N_t is used for the earning groups {N_z, N_{z+1}, N_{z+2}}, which collides with the notation N_r for the agent groups in Algorithm 2 (Section 4.1.1). Consider using different symbols to avoid confusion.","section":"§4.2"},{"comment":"In part (1) of the proof, the inequality p(X_i^{t+1}) − 1 ≤ 2·p(X_j^t) − 1 is justified by citing that the allocation is pEF1 for agent i, but the specific bound p(X_i^t ∩ L) ≤ p(X_j^t) follows from Lemma 3.4. Please cite Lemma 3.4 explicitly.","section":"§3.3, Lemma 3.12"},{"comment":"The notation in the earning-history argument, such as p^{t_i}(X^{t_i}_{l_{t_i}}), is introduced implicitly; please define it or use the established notation from Lemma 4.6 for clarity.","section":"§4.2, Lemma 4.9"}],"recommendation":"major_revision","confidential_remarks":"The gap in Section 4 is serious but appears potentially fixable with a sharper analysis of the earning histories of unraised agents in Algorithm 2. The first result (Theorem 3.14) seems sound and independently valuable. Please ask the authors to repair Lemma 4.9 or provide an alternative argument for j ∈ U before reconsidering the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: Section 3 is genuinely good; Section 4 is not established. The (2-1/k)-EFX + PO guarantee for {1,k} chores improves Garg et al.'s 3-EFX and appears to hold. The proof via a pEF1 integral equilibrium and a swap between high- and low-payment agents is clean, and the invariants in 3.8–3.10 are checked carefully. I read the termination argument and it is fine. This is a solid new result.\n\nThe problem is the EFX+PO for {1,2} chores. Theorem 4.13 depends on Lemma 4.9, which asserts that if i is not EFX towards j then j is unraised. The proof invokes 'only raised agents give out items' to get that i has never lost an item. But Algorithm 2 line 18 updates X_i <- X_i + e1 - e2 with i in U: an unraised agent gives out e2 and receives e1. So the claimed invariant is false. The subsequent case analysis in Lemma 4.9 assumes the losing/gaining history of i is one-sided, which is exactly what line 18 breaks. Without j in U, Algorithm 3's reallocation to j may not give j an MPB item, and the equilibrium property—and hence PO—is no longer guaranteed. The gap is load-bearing, not cosmetic.\n\nI want to stress what this is not. It is not a counterexample or a claim that the theorem is false; the theorem may well be true, and a repaired invariant or a different argument for j in U could save it. The first half of the paper is unaffected and stands on its own.\n\nSo my recommendation: this should go to peer review, not a desk reject. A serious referee will want the authors to fix Lemma 4.9 or replace it. If the fix is straightforward, the paper becomes a strong contribution. If not, the second theorem is part of the paper and the rejection is justified for the preprint as written. I would bring it to reading group to discuss the reallocation technique, but I would not cite the second theorem until it is proven.","headline":"The (2-1/k)-EFX+PO result for {1,k} chores is likely correct and is a real improvement; the EFX+PO result for {1,2} chores rests on a false invariant about unraised agents and is unsupported as written.","tokens_in":19108,"tokens_out":2821,"would_cite":true,"duration_ms":26014,"reading_group":"yes","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":"The paper gives polynomial-time algorithms that turn a payment-envy-free equilibrium for bi-valued chores into a (2-1/k)-EFX and Pareto-optimal allocation, and into an exact EFX and Pareto-optimal allocation when k=2.","keywords":["fair division","chores","EFX","Pareto optimality","bi-valued valuations","market equilibrium","payment envy-freeness","approximation algorithms"],"falsifier":"Take any {1,2}-instance, run the preliminary equilibrium construction exactly as written, and record each unraised agent's bundle after every round; if any unraised agent ever loses an item, then the proof of Lemma 4.9 collapses, and running the final reallocation on that instance would show whether the claimed EFX-and-PO output still appears or the algorithm fails.","tokens_in":17980,"feed_emoji":"🧹","tokens_out":9865,"duration_ms":97482,"temperature":0.7,"pith_summary":"The paper tries to establish that bi-valued chores—where every item costs each agent either 1 or k—admit allocations that are both fair and efficient, and that such allocations can be computed quickly. Its first result is a polynomial-time algorithm that returns a (2-1/k)-approximate EFX allocation that is also Pareto optimal, improving the previous 3-EFX guarantee. Its second result says that when k=2, a related algorithm returns an exact EFX allocation that is also Pareto optimal. If correct, the k=2 case adds a broad family to the small set of chore instances known to admit EFX and PO allocations simultaneously.","feed_headline":"Bi-valued chores get (2-1/k)-fair, Pareto-optimal splits","feed_subtitle":"Same method reaches exact EFX when both costs are 1 and 2; prior best was 3-EFX.","key_machinery":"The engine is the pEF1 {1,k}-payment equilibrium, an integral allocation with item payments in {1,k} where each agent receives only items minimizing her cost-per-payment ratio and every payment-envy can be removed by deleting one item from the envier's bundle. The algorithm's load-bearing lemma shows that if an agent is not (2-1/k)-EFX toward another, then the envying agent holds a unique high-payment item, the envied agent's entire bundle lies in the envying agent's minimum pain-per-buck set, and the swap—giving the high-payment item to the envied agent and taking that agent's bundle—is feasible for both sides. Because payments never change, maintaining the equilibrium is exactly maintaining Pareto optimality. The k=2 refinement partitions agents into earning classes z, z+1, and z+2 and restricts swaps to unraised agents, making exact EFX reachable.","core_discovery":"The paper's central claim is that a payment-envy-free equilibrium (pEF1) for bi-valued chores—an allocation where each agent receives only items minimizing her cost-to-payment ratio, payments are 1 or k, and every payment-envy can be removed by deleting one item from the envier's bundle—can be reshaped by item swaps that preserve the equilibrium into an allocation that is (2-1/k)-EFX and Pareto optimal. The algorithm never changes item payments; every item moved is a minimum pain-per-buck item for its new owner, so the allocation remains a market equilibrium throughout, and Pareto optimality follows from the First Welfare Theorem. For k=2, the finer structure of the starting equilibrium, with agent earnings confined to z, z+1, and z+2, supports an exact EFX and PO result.","pith_inferences":["If the unraised-agent invariant can be restored or replaced, the k=2 claim might survive with a different potential or a modified update; a direct counterexample search on small {1,2}-instances would tell whether the construction as written actually allows an unraised agent to lose items in an execution that reaches a non-EFX output.","The same 'round an integral pEF1 equilibrium instead of a fractional one' idea is likely to transfer to chores with three or more fixed cost levels; the known failure of EFX plus PO for unrestricted ternary instances marks the boundary where the method must stop.","The earning-class argument for k=2 suggests a testable extension to weighted chores with bounded payment spread: if earnings fall in a bounded interval around some z, a similar classification might yield exact EFX for other small values of k."],"forward_implications":["For every {1,k}-instance, a (2-1/k)-EFX and PO allocation now has a polynomial-time construction, improving the previous 3-EFX-and-PO guarantee.","For {1,2}-instances, EFX and PO allocations exist for every number of agents and items, adding a broad family to the short list of chore cases with exact EFX plus Pareto optimality.","Because every transfer is minimum-pain-per-buck feasible and payments are static, the returned allocation is a market equilibrium and hence Pareto optimal; the entire difficulty is concentrated in the fairness loop.","The k=2 algorithm terminates in O(n) reallocation rounds after the pEF1 equilibrium is built, so the total running time stays polynomial."],"supporting_citations":[{"why":"Supplies the integral pEF1 equilibrium for bi-valued chores that Algorithms 1 and 3 start from.","marker":"[21]"},{"why":"Provides the pEF1 equilibrium construction followed for the k=2 case, including the agent-group and raising operations used in Lemma 4.9.","marker":"[30]"},{"why":"Establishes the previous 3-EFX and PO baseline by rounding a fractional equilibrium, which this paper improves.","marker":"[23]"},{"why":"Gives the First Welfare Theorem used to conclude that every maintained market equilibrium is Pareto optimal.","marker":"[27]"},{"why":"Handles the binary-chore base case that is excluded by scaling, completing the coverage of bi-valued instances.","marker":"[29]"}],"fun_headline_variants":["Chores: (2-1/k)-EFX and PO allocation achieved","Bi-valued chores: from 3-EFX to (2-1/k)-EFX","Exact EFX for bi-valued chores when costs are 1 and 2","Improved fair division for bi-valued chores: (2-1/k)-EFX and PO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the k=2 theorem, the load-bearing premise is that during the preliminary equilibrium construction an unraised agent only gains items and never gives one away; the construction as written updates an unraised agent's bundle as X_i + e1 - e2, so the proof does not currently establish that premise.","fun_headline_variants_meta":{"raw":{"variants":["Chores: (2-1/k)-EFX and PO allocation achieved","Bi-valued chores: from 3-EFX to (2-1/k)-EFX","Exact EFX for bi-valued chores when costs are 1 and 2","Improved fair division for bi-valued chores: (2-1/k)-EFX and PO"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000776,"raw_usage":{"total_tokens":3401,"prompt_tokens":886,"completion_tokens":2515,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":2424}},"tokens_in":502,"tokens_out":2515,"duration_ms":18933,"temperature":1.0,"reasoning_tokens":2424,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:30:55.247651+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any {1,2}-instance, run the preliminary equilibrium construction exactly as written, and record each unraised agent's bundle after every round; if any unraised agent ever loses an item, then the proof of Lemma 4.9 collapses, and running the final reallocation on that instance would show whether the claimed EFX-and-PO output still appears or the algorithm fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the integral pEF1 equilibrium for bi-valued chores that Algorithms 1 and 3 start from."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the pEF1 equilibrium construction followed for the k=2 case, including the agent-group and raising operations used in Lemma 4.9."},{"cited_title":"Constant-Factor EFX Exists for Chores","cited_arxiv_id":"2407.03318","evidence_quote":"Establishes the previous 3-EFX and PO baseline by rounding a fractional equilibrium, which this paper improves."},{"cited_title":"Mas-Colell, M","cited_arxiv_id":null,"evidence_quote":"Gives the First Welfare Theorem used to conclude that every maintained market equilibrium is Pareto optimal."},{"cited_title":"On the Existence of EFX (and Pareto-Optimal) Allocations for Binary Chores","cited_arxiv_id":"2308.12177","evidence_quote":"Handles the binary-chore base case that is excluded by scaling, completing the coverage of bi-valued instances."}],"review_version":1}