{"id":"64faf451-b5ac-40d7-9877-5aaa0cd05467","arxiv_id":"2507.12984","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"No deterministic online algorithm for indivisible chores can guarantee every agent a cost below n times their maximin share, making the trivial all-to-one algorithm optimal.","lead":"This paper proves that no online algorithm can fairly distribute arriving chores among n agents with a guarantee better than n times each agent's fair share. The result closes a gap in online fair division by improving the known lower bound from 2 to n.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The induction step 'the exact same blueprint' is the load-bearing point: it silently assumes that an aborted inner sc(i) run can be restarted on agents a2..a_{i+1} and that a1's final MMS satisfies an unstated total-cost/largest-item bound. This is never proved for general i.","rationale":"I read the paper in good faith. The base case sc(1) and the sc(2) construction are checkable and, modulo small fixable edge cases such as w = x/epsilon when x = 0, the algebra is consistent. The claimed lower bound of n is not contradicted by any known result, and the trivial all-to-one-agent algorithm indeed has competitive ratio n, so the target is coherent. The genuinely load-bearing weakness is the general induction step: the sentence 'the transition from each sc(i, epsilon) to sc(i+1, epsilon) follows the exact same blueprint' is the only support for the entire recursive construction beyond two agents. The reader's weakest_assumption points to exactly this composition of an inner sc(i) adversary with an outer geometric sequence for a1, and I agree that this is the right concern. I do not see a demonstrated falsehood, only a missing proof of a non-obvious composition: aborted runs must be restartable, the recursive scenarios must terminate, and the MMS upper bound for a1 must be justified by an explicit scheduling bound. These are the kinds of gaps that can be filled, but until they are filled the theorem is conditional rather than established. Therefore I would not accept the paper as-is without a complete induction step, and I would not reject it either, because the sc(2) case strongly suggests the intended construction can be made rigorous. The reader's CONDITIONAL verdict is the appropriate one, so my stress-test does not change the verdict.","tokens_in":4656,"tokens_out":24414,"duration_ms":294692,"concrete_test":"Explicitly instantiate the induction step for i = 2: define ell_2, run sc(2) on agents a2 and a3, and verify that after every abort caused by an assignment to a1, the updated cost profiles of a2 and a3 satisfy the 'arbitrary previous chores' hypothesis needed to start another sc(2) run. Then check the a1 accounting formally: for each aborted run, the chore assigned to a1 dominates all a1-costs not assigned to a1 since the last restart; after stopping when total generated a1-cost first reaches nw, verify that T (total a1-cost of all chores generated) satisfies T <= (n + O(epsilon))w and largest item L = O(epsilon)w, so that the list-scheduling bound gives MMS_1 <= (1 + O(epsilon))w and the final ratio is at least n(1 - epsilon). If this written-out step type-checks without extra assumptions, the induction is likely sound; if it cannot be written out, Theorem 3.1 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 depends entirely on the recursive construction of sc(i, epsilon), but the paper only writes out sc(1) and sc(2); the step from sc(i) to sc(i+1) is dismissed with 'the exact same blueprint except that the values of ell_i increase exponentially.' For that step to be valid, three concrete conditions must hold, and none is proved. First, ell_i must be well-defined and finite for every i, yet only ell_1 = n is defined and an upper bound for ell_2 is sketched; the paper does not prove that the general recursion terminates. Second, when a run of the inner sc(i) on agents a2..a_{i+1} is aborted because a chore is assigned to a1, the chores already assigned to a2..a_{i+1} become part of the previous history for the next run; the induction hypothesis does allow arbitrary previous chores, but the paper never checks that restarting after an abort preserves the hypotheses needed by sc(i). Third, the final MMS bound for a1 uses the scheduling-type inequality MMS <= T/n + (1 - 1/n)L (or an equivalent), where T is total cost and L is the largest chore cost; this bound is never stated, and the accounting of T after many aborted restarts is compressed into a few inequalities. The sc(2) calculation also glosses over the zero-previous-cost case w = x/epsilon, which needs an explicit handling. None of these is an obvious counterexample, and the sc(2) case suggests the blueprint is plausible, but the general induction is not actually written out. Because the theorem is a universal lower bound for all n, this gap is load-bearing: if the composition fails, the proof does not establish the claimed n lower bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online assignment of indivisible chores to n agents under the maximin share (MMS) benchmark, where chores arrive one by one and must be irrevocably assigned. The main result (Theorem 3.1) claims that no deterministic online algorithm can be (n - nε)-competitive for any ε > 0, i.e., the competitive ratio is at least n, matching the trivial upper bound of assigning all chores to a single agent. The proof constructs a recursive adversarial scenario sc(i, ε) for i = 1, ..., n. The base scenario sc(1, ε) is written out: with prior cost x for agent a1, the adversary introduces n chores of cost w = x/ε, forcing cost nw against MMS at most w + x. The step from sc(1) to sc(2) is sketched with a geometric cost sequence and a bound on the total cost and MMS for a1. The transition from sc(i) to sc(i+1) is asserted to follow \"the exact same blueprint\" with exponentially growing ℓ_i, but is not formalized.","tokens_in":5039,"tokens_out":8727,"duration_ms":89223,"significance":"If the claimed lower bound is correct, it is a significant improvement over the previous best lower bound of 2 and closes the problem for deterministic online MMS chore assignment, since the trivial algorithm that assigns every chore to one agent is n-competitive. The base case argument is clean and the exponential-growth intuition for the recursive scenario is plausible. The paper is self-contained and does not rely on the result it proves. However, the proof as written contains a load-bearing unproven induction step; without a complete recursive construction, the theorem is not established for n > 2. The result is therefore potentially important, but the manuscript currently does not provide a complete proof.","major_comments":[{"comment":"The induction step from sc(i, ε) to sc(i+1, ε) is the core of the proof, but it is only asserted. The paper defines ℓ_1 = n and sketches ℓ_2, but does not define ℓ_i for general i, prove that the geometric sequences and restarting loops terminate, or show that the total number of chores generated remains finite. A universal lower bound for all n requires a fully specified recursion; as written, the proof only establishes the cases i = 1 and i = 2.","section":"Section 3, paragraph beginning \"The transition from each sc(i, eps) to sc(i+1, eps)\""},{"comment":"The induction step requires composing an inner sc(i, ε) adversary on agents a2..a_{i+1} with an independent geometric cost sequence for a1, restarting the inner adversary after each abort. The proof never states the input-history hypothesis under which sc(i, ε) is invoked after an abort, nor proves that the inner scenario's guarantee (one of a2..a_{i+1} exceeds her MMS by the desired factor) is preserved when the inner scenario is run multiple times with interleaved chores assigned to a1. Without this composition lemma, the recursive construction is not well-defined.","section":"Section 3, sc(i+1) construction"},{"comment":"The bound \"MMS1 ≤ nw/n + 3ε'w = (1+3ε')w\" relies on an unstated scheduling-type inequality MMS ≤ T/n + (1 - 1/n)L, where T is total cost and L is the largest item cost. Even with that inequality, the displayed total cost bound from the previous line is T ≤ (n+2ε')w, not T = nw; the calculation as written drops the 2ε'w term. For the general induction, the paper gives no accounting of the accumulated total cost across all aborted restarts, which is needed to bound a1's final MMS. The sc(2) calculation therefore does not demonstrate the general invariant.","section":"Section 3, sc(2) MMS accounting"},{"comment":"The definition w = x/ε (and similarly w = x/ε' in sc(2)) degenerates when the scenario is invoked with no prior chores: x = 0 gives w = 0 and all subsequent costs are zero, so the scenario never terminates and produces no positive cost. Since the online instance begins with an empty history, the construction as written does not apply to the initial invocation. The proof needs an explicit rule for the first chore (e.g., w = max(x, 1)/ε) or another way to seed a positive cost.","section":"Section 3, sc(1) and sc(2) definitions of w"}],"minor_comments":[{"comment":"In the introduction, MMS_i is defined as max over partitions of min over bundles, which is the goods form; Section 2 correctly defines it as min over partitions of max over bundles for chores. Please correct the introduction.","section":"Section 1, MMS definition"},{"comment":"The inequality ℓ2 ≤ ℓ1 + n(1+1/ε')^{ℓ1} is stated without derivation; it would help to explain why each pattern can contribute at most nw to a1's cost and how the multiplicative factor n arises.","section":"Section 3, sc(2) bound for ℓ_2"},{"comment":"References [13] and [14] are duplicates of the same JACM paper; please remove the duplicate.","section":"References"},{"comment":"The symbol n appears both as the total number of agents in the theorem and as the index in sc(i); in the sc(2) calculation \"nw/n\" is confusing because the scenario has only a1 and a2 active. Please clarify that MMS is computed over n bundles, one per agent, even when only i agents ever receive chores.","section":"Section 3, notation"},{"comment":"In the sc(2) proof, the phrase \"if ℓ1 consecutive chores are given to agent a2 then the algorithm would not be (n - nε)-competitive by the guarantees of sc(1, ε)\" should note that sc(1, ε) is invoked with the previous chores assigned to a2 as history; the costs of those chores for a2 need to be defined consistently.","section":"Section 3, sc(2) proof"},{"comment":"The proof of sc(1) states that costs for other agents \"do not matter\"; to make the online instance complete, specify that all other agents have sufficiently large costs for the constructed chores, or explicitly state that their values are irrelevant and can be set arbitrarily.","section":"Section 3, sc(1) proof"}],"recommendation":"major_revision","confidential_remarks":"The paper is very short and the proof is compressed. The core claim is plausible and the base case is sound, but the omitted induction is substantial; a major revision with a fully written recursive construction and a composition lemma is necessary. I do not see circularity or novelty problems; the claim matches the state of the art and the approach is original. The paper's fit for cs.GT is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper improves the known deterministic lower bound for online MMS chore division from 2 to n, matching the trivial all-to-one algorithm. That is the right result, and the recursive adversary is genuinely new for this setting. I worked through sc(1) and sc(2); the algebra is correct, and the exponential cost sequence for agent a1 does what it claims. Credit where due: the base case is clean, and the two-agent lift is a clever use of a 'threat' sub-scenario.\n\nThe soft spot is the general induction. The proof says the transition from sc(i) to sc(i+1) follows 'the exact same blueprint' and then stops. Three things need to be explicit before Theorem 3.1 is fully proved for all n. First, the parameter ℓ_i, the maximum number of chores in sc(i), is only defined for i=1 and bounded for i=2; the general recursion is asserted. It's surely finite, roughly an exponential tower, but the paper should prove it. Second, when a run of the inner sc(i) is aborted by giving a chore to a1, the next run restarts on agents a2..a_{i+1} with the chores so far as previous history. The induction hypothesis allows arbitrary previous history, so this is probably fine, but the composition is never written out. Third, the MMS upper bound for agent a1 relies on the standard scheduling bound MMS ≤ T/n + (1-1/n)L, where T is total cost and L the largest chore. The paper doesn't state it; I had to reverse-engineer it. None of these looks like a real counterexample, but for a universal lower bound they are load-bearing exposition gaps, not cosmetic ones.\n\nMinor things: the MMS definition flips between max-min and min-max in the intro and prelims, and reference [14] is duplicated. Not material.\n\nBottom line: I agree with the conditional verdict. The result is likely correct and the proof is fixable, but the current manuscript does not contain a complete proof of the main theorem. It deserves a serious referee, one who will ask for the full induction. I'd accept it for review, with the expectation of a revision.","headline":"Tight lower bound for deterministic online MMS chores; the base and two-agent cases are solid, but the general induction is sketched, not proved.","tokens_in":5490,"tokens_out":13030,"would_cite":true,"duration_ms":135997,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that no deterministic online algorithm for splitting chores can guarantee every agent less than n times her fair share, where n is the number of agents.","keywords":["online algorithms","fair division","indivisible chores","maximin share","competitive ratio","lower bound","deterministic algorithms"],"falsifier":"Run the explicit sc(2, ε) construction with small n (say n=2 or 3) and search deterministically for a strategy that keeps every agent's final cost below (n − nε) times her MMS; if such a strategy exists, the induction's embedding step is false, and if none exists, the base step can be inspected numerically to verify the claimed ratio.","tokens_in":4477,"feed_emoji":"🧹","tokens_out":5727,"duration_ms":61533,"temperature":0.7,"pith_summary":"The paper tries to establish a lower bound for online fair division of indivisible chores: when chores arrive one by one and must be assigned immediately, no deterministic algorithm can guarantee every agent a bundle costing less than n times her maximin share, for n agents. The previous known lower bound was 2; the paper raises it to the full n. That number matters because the naive strategy of giving every chore to a single agent is n-competitive, so if the theorem is right, the deterministic online problem is completely closed: nothing beats the trivial policy. The argument is an adaptive adversary that builds chores recursively, forcing whichever agent receives the expensive items to exceed an n-fold multiple of her fair share. A careful reader should note that the recursive step from i agents to i+1 agents is asserted rather than fully expanded.","feed_headline":"Online chore division: no deterministic algorithm beats ratio n","feed_subtitle":"An adaptive adversary forces one agent to pay n times her fair share, matching the all-in-one strategy.","key_machinery":"The carrying object is the recursive scenario sc(i, ε), an adaptive adversary that controls the costs of incoming chores. Its base case forces one agent to take n chores, and its inductive step is a geometric cost ladder for agent a1: chore costs increase exponentially, and any assignment to a1 costs at least 1/ε′ times the total cost, for a1, of the chores she did not take, while a stray run of chores to the other agents triggers the embedded sc(i) trap. The length parameter ℓ_i grows exponentially at each level—ℓ_1 = n and ℓ_2 ≈ n(1+1/ε′)^{ℓ_1}—so the full adversary is finite but tower-sized. The induction is what converts a trap for i agents into a trap for i+1 agents while keeping the MMS bound of the new backstop agent under control.","core_discovery":"The paper's central claim is Theorem 3.1: for every ε > 0 there is an online instance with n agents on which any deterministic online algorithm leaves some agent with cost at least (n − nε) times her MMS, where MMS is the maximin share—the minimum, over all n-way partitions of the chores, of the maximum cost any bundle imposes on that agent. Since ε is arbitrary, no deterministic online algorithm can be (n − nε)-competitive; the best possible deterministic competitive ratio is exactly n. The proof constructs scenarios sc(i, ε) by induction. In sc(1, ε) a single trapped agent receives n chores whose costs dwarf her MMS, giving ratio about n. For sc(i+1, ε), the adversary generates chores whose costs for agent a1 grow geometrically, while an inner scenario sc(i, ε) is embedded on the remaining agents; if the algorithm gives too many consecutive chores to the inner agents the embedded trap fires, and if it gives one to a1, that single chore pays for all skipped chores by a factor of about 1/ε. At the end a1 has accumulated a stated fraction of the total generated cost while her MMS stays bounded, again forcing ratio n(1−ε).","pith_inferences":["A natural next test is whether the bound survives with a bounded number of chores: since ℓ_2 is exponential in n, an algorithm that knows it will see at most poly(n) chores might beat n within that horizon, and this construction does not rule it out.","The proof's reliance on adaptive cost revelation suggests that an oblivious adversary (all costs fixed in advance) may be strictly weaker; checking whether the same n lower bound holds for offline-known cost sequences would delimit the role of adaptivity.","The same recursive ladder might transfer to other fairness benchmarks, such as proportional share or envy-free up to one chore, with the geometric ratio 1/ε playing the same role; testing that would show whether the n barrier is specific to MMS or generic to online chores.","Because the construction forces a1 to accumulate cost while the other agents are trapped, it resembles a scheduler-exploiting adversary; a concrete follow-up could be to port the scenario to online load balancing and see whether the same ratio appears there."],"forward_implications":["The deterministic competitive ratio for online MMS chore division is exactly n: the trivial algorithm that assigns every chore to one agent is optimal.","The old lower bound of 2 is superseded; no constant-factor deterministic online algorithm exists for chores, in contrast to the offline setting where a 13/11 approximation is known.","Any algorithm that wants a ratio below n must be randomized or must assume extra structure, such as a bound on the number of chores m or non-adversarial cost sequences.","The adversary needs scenarios of length roughly exponential in n at the second level and tower-exponential deeper, so the result concerns worst-case instances with very long chore streams.","If randomization or a known horizon m can break the bound, the paper's construction gives a concrete family of instances on which to test such algorithms."],"supporting_citations":[{"why":"Supplies the online MMS model and the previous 2 lower bound that this paper improves.","marker":"[21]"},{"why":"Defines the maximin share benchmark that the competitive ratio is measured against.","marker":"[5]"},{"why":"Gives the current best 13/11 approximation for offline chore allocation, the contrast that makes the online n lower bound significant.","marker":"[11]"}],"fun_headline_variants":["Online chores: no deterministic algorithm beats ratio n","Chore division online: deterministic algorithms stuck at n","MMS chores online: deterministic ratio n is tight","For online chores, no deterministic algorithm beats n","Deterministic online chores: ratio n is unavoidable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole proof rests on the unstated claim that the inner i-agent trap can be embedded inside the i+1-agent scenario and restarted whenever the fresh agent takes a chore, without changing that fresh agent's maximin-share bound; if that composition fails at some level, the theorem does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Online chores: no deterministic algorithm beats ratio n","Chore division online: deterministic algorithms stuck at n","MMS chores online: deterministic ratio n is tight","For online chores, no deterministic algorithm beats n","Deterministic online chores: ratio n is unavoidable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000861,"raw_usage":{"total_tokens":3685,"prompt_tokens":841,"completion_tokens":2844,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":457,"completion_tokens_details":{"reasoning_tokens":2780}},"tokens_in":457,"tokens_out":2844,"duration_ms":22491,"temperature":1.0,"reasoning_tokens":2780,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:37:00.924260+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the explicit sc(2, ε) construction with small n (say n=2 or 3) and search deterministically for a strategy that keeps every agent's final cost below (n − nε) times her MMS; if such a strategy exists, the induction's embedding step is false, and if none exists, the base step can be inspected numerically to verify the claimed ratio.","supporting_citations":[{"cited_title":"Multi-agent online scheduling: Mms allocations for indivisible items","cited_arxiv_id":null,"evidence_quote":"Supplies the online MMS model and the previous 2 lower bound that this paper improves."},{"cited_title":"A Reduction from Chores Allocation to Job Scheduling","cited_arxiv_id":"2302.04581","evidence_quote":"Gives the current best 13/11 approximation for offline chore allocation, the contrast that makes the online n lower bound significant."}],"review_version":1}