Lower Bound for Online MMS Assignment of Indivisible Chores

Masoud Seddighin; Saeed Seddighin

REVIEW 4 major objections 6 minor 1 cited by

Lower Bound for Online MMS Assignment of Indivisible Chores

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict Tight lower bound for deterministic online MMS chores; the base and two-agent cases are solid, but the general induction is sketched, not proved. read the letter →

arxiv 2507.12984 v1 pith:C5J3RKAH submitted 2025-07-17 cs.GT

Masoud Seddighin , Saeed Seddighin This is my paper · ORCID

classification cs.GT MSC 68W2791B32

keywords onlinealgorithmsfairdivisionindivisiblechoresmaximinsharecompetitiveratiolowerbounddeterministic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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−ε).

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Minor things: the MMS definition flips between max-min and min-max in the intro and prelims, and reference [14] is duplicated. Not material.

Bottom 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.

Referee Report

4 major / 6 minor

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.

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 (4)

[Section 3, paragraph beginning "The transition from each sc(i, eps) to sc(i+1, eps)"] 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 3, sc(i+1) construction] 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 3, sc(2) MMS accounting] 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 3, sc(1) and sc(2) definitions of w] 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.

minor comments (6)

[Section 1, MMS definition] 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 3, sc(2) bound for ℓ_2] 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.
[References] References [13] and [14] are duplicates of the same JACM paper; please remove the duplicate.
[Section 3, notation] 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 3, sc(2) proof] 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 3, sc(1) proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the recursive adversary construction is self-contained and does not assume the theorem.

full rationale

The derivation chain is a direct lower-bound adversary construction, not a cycle. The base case sc(1,eps) is specified from an arbitrary previous-history total x and produces chores with costs w = x/eps for agent a1; the bound MMS1 <= w(1+eps) follows from the same additive cost structure, not from the claimed competitive ratio. For sc(2,eps), the paper computes the ratio from the geometry of exponentially increasing costs and the accounting MMS1 <= (1+3eps')w, again using only the constructed costs. The passage from sc(i) to sc(i+1) is asserted as 'the exact same blueprint' rather than fully written out; this is a completeness or correctness gap in the proof, not circularity, because the induction hypothesis is a strictly weaker statement (failure on i agents) used to force a response on i+1 agents, and no step defines the target bound in terms of itself. Self-citations [9,10,17,18] appear only as literature context, not as evidence for Theorem 3.1. The prior lower bound [21] is external prior work used only as a baseline. No fitted parameter is relabeled as a prediction, no uniqueness theorem is imported from the authors, and the central claim is not equivalent by construction to its inputs.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof relies on standard fair division definitions, a standard scheduling bound that is not stated, and an unproved inductive composition. No new particles, forces, or entities are introduced.

assumptions (3)

domain assumption Additive cost valuations are the model for how agents evaluate bundles of chores.
Used throughout; fair division with additive costs is the framework, and the proof's construction relies on costs being additive across chores.
standard math For any list of item costs, the optimal n-bin makespan is at most total/n plus (1 - 1/n) times the largest item cost (Graham bound).
Used implicitly to upper bound MMS1 in the sc(2) argument; the paper writes MMS1 <= nw/n + 3eps'w without deriving it.
ad hoc to paper The sc(i) adversary can be used as a black box inside sc(i+1), with a separate geometric cost sequence for the backstop agent, and aborted runs can be restarted without invalidating the backstop's MMS bound.
This is the unproved inductive composition that the 'same blueprint' sentence relies on; it is the main gap in the proof as written.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lower Bound for Online MMS Assignment of Indivisible Chores." pith.science (2026). https://pith.science/paper/C5J3RKAH

@misc{pith2026250712984,
  author       = {Pith},
  title        = {Pith review of: Lower Bound for Online MMS Assignment of Indivisible Chores},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C5J3RKAH}},
  note         = {Machine review of arXiv:2507.12984}
}

abstract

We consider the problem of online assignment of indivisible chores under \MMS\ criteria. The previous work proves that any deterministic online algorithm for chore division has a competitive ratio of at least 2. In this work, we improve this bound by showing that no deterministic online algorithm can obtain a competitive ratio better than $n$ for $n$ agents.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Constant Weighted Maximin Share Approximations for Chores
cs.GT 2025-10 conditional novelty 8.0 of 10

Weighted maximin share for indivisible chores admits a 12-approximate allocation and cannot be approximated better than factor 2.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages · cited by 1 Pith paper

[14]

Fair enough: Guaranteeing approxi- mate maximin shares.Journal of the ACM (JACM), 65(2):8, 2018

David Kurokawa, Ariel D Procaccia, and Junxing Wang. Fair enough: Guaranteeing approxi- mate maximin shares.Journal of the ACM (JACM), 65(2):8, 2018

work page 2018
[1]

Simplification and im- provement of mms approximation

Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and im- provement of mms approximation. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2485–2493, 2023

work page 2023
[2]

Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations

Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami. Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations. Advances in Neural Information Processing Systems, 36, 2024

work page 2024
[3]

Approximation al- gorithms for computing maximin share allocations.ACM Transactions on Algorithms (TALG), 13(4):52, 2017

GeorgiosAmanatidis, Evangelos Markakis, AfshinNikzad, and Amin Saberi. Approximation al- gorithms for computing maximin share allocations.ACM Transactions on Algorithms (TALG), 13(4):52, 2017. 4

work page 2017
[4]

Cambridge University Press, 1996

Steven J Brams and Alan D Taylor.Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996

work page 1996
[5]

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

2011
[6]

The unreasonable fairness of maximum nash welfare

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. InProceedings of the 2016 ACM Conference on Economics and Computation, pages 305–322. ACM, 2016

work page 2016
[7]

How to cut a cake fairly

Lester E Dubins and Edwin H Spanier. How to cut a cake fairly. American mathematical monthly, pages 1–17, 1961

work page 1961

Show all 20 references

[8]

A note on cake cutting.Discrete Applied Mathematics, 7(3):285– 296, 1984

Shimon Even and Azaria Paz. A note on cake cutting.Discrete Applied Mathematics, 7(3):285– 296, 1984

1984
[9]

Fair allocation of indivisible goods to asymmetric agents

Alireza Farhadi, MohammadTaghi Hajiaghayi, Mohammad Ghodsi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods to asymmetric agents. InProceedings of the 16th Conference on Autonomous Agents and MultiAgent Sy...

2017
[10]

Fair allocation of indivisible goods: Improvements and generalizations

Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. InPro- ceedings of the 2018 ACM Conference on Economics and Computation, pages 539–556. ACM, 2018

2018
[11]

A reduction from chores allocation to job scheduling.arXiv preprint arXiv:2302.04581, 2023

Xin Huang and Erel Segal-Halevi. A reduction from chores allocation to job scheduling.arXiv preprint arXiv:2302.04581, 2023

2023 arXiv
[12]

When can the maximin share guar- antee be guaranteed? InAAAI, volume 16, pages 523–529, 2016

David Kurokawa, Ariel D Procaccia, and Junxing Wang. When can the maximin share guar- antee be guaranteed? InAAAI, volume 16, pages 523–529, 2016

2016
[15]

On approximately fair allocations of indivisible goods

Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM conference on Electronic commerce, pages 125–131. ACM, 2004

2004
[16]

Cake-cutting algorithms: Be fair if you can

Jack Robertson and William Webb. Cake-cutting algorithms: Be fair if you can. AK Pe- ters/CRC Press, 1998

1998
[17]

Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem.Artificial Intelligence, 327:104049, 2024

Masoud Seddighin and Saeed Seddighin. Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem.Artificial Intelligence, 327:104049, 2024

2024
[18]

Beating the logarithmic barrier for the subadditive maximin share problem

Masoud Seddighin and Saeed Seddighin. Beating the logarithmic barrier for the subadditive maximin share problem. InEC, 2025

2025
[19]

The problem of fair division.Econometrica, 16(1), 1948

Hugo Steinhaus. The problem of fair division.Econometrica, 16(1), 1948. 5

1948
[20]

How to cut a cake fairly.The American Mathematical Monthly, 87(8):640– 644, 1980

Walter Stromquist. How to cut a cake fairly.The American Mathematical Monthly, 87(8):640– 644, 1980

1980
[21]

Multi-agent online scheduling: Mms allocations for indivisible items

Shengwei Zhou, Rufan Bai, and Xiaowei Wu. Multi-agent online scheduling: Mms allocations for indivisible items. In International Conference on Machine Learning, pages 42506–42516. PMLR, 2023. 6

2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [14]

Fair enough: Guaranteeing approxi- mate maximin shares.Journal of the ACM (JACM), 65(2):8, 2018

David Kurokawa, Ariel D Procaccia, and Junxing Wang. Fair enough: Guaranteeing approxi- mate maximin shares.Journal of the ACM (JACM), 65(2):8, 2018

work page 2018

[2] [1]

Simplification and im- provement of mms approximation

Hannaneh Akrami, Jugal Garg, Eklavya Sharma, and Setareh Taki. Simplification and im- provement of mms approximation. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2485–2493, 2023

work page 2023

[3] [2]

Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations

Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami. Random- ized and deterministic maximin-share approximations for fractionally subadditive valuations. Advances in Neural Information Processing Systems, 36, 2024

work page 2024

[4] [3]

Approximation al- gorithms for computing maximin share allocations.ACM Transactions on Algorithms (TALG), 13(4):52, 2017

GeorgiosAmanatidis, Evangelos Markakis, AfshinNikzad, and Amin Saberi. Approximation al- gorithms for computing maximin share allocations.ACM Transactions on Algorithms (TALG), 13(4):52, 2017. 4

work page 2017

[5] [4]

Cambridge University Press, 1996

Steven J Brams and Alan D Taylor.Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996

work page 1996

[6] [5]

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

2011

[7] [6]

The unreasonable fairness of maximum nash welfare

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. InProceedings of the 2016 ACM Conference on Economics and Computation, pages 305–322. ACM, 2016

work page 2016

[8] [7]

How to cut a cake fairly

Lester E Dubins and Edwin H Spanier. How to cut a cake fairly. American mathematical monthly, pages 1–17, 1961

work page 1961