MMS Allocation for Chores with Online Agent Arrivals

1 Introduction

• Online chore allocation assigns each arriving agent unallocated items irrevocably, with the goal of a full allocation that minimizes the worst MMS approximation ratio.Agents have subadditive cost functions, and even a trivial allocation guarantees n-MMS.Source: §1 · pp. 2–3
• For two agents, and more generally under a nested binary-cost construction, no online algorithm can guarantee a ratio strictly better than n.The motivating question is whether bounded item counts or few agent types allow ratios below n.Source: §1 · p. 3

1.1 Our Contributions

• With no prior cost-function information, an algorithm can achieve a ratio strictly below n when the item count is bounded or agents have few types.The algorithm is near-optimal: deterministic online algorithms face a lower bound of Ω(min{n, k log k, log m}), even for binary additive instances.Source: §1.1 · p. 3
• For online chore allocation with binary additive costs, when agents belong to k known types and k ≤ n, a 3-competitive algorithm exists; for general k, constant-competitive algorithms do not exist.Source: §1.1 · p. 4

1.2 Technical Overview

• A universal partition divides the chores into n bundles that are approximately MMS for every type, letting each arriving agent take any unused bundle.One construction controls all kn type-bundle constraints; another builds bundles sequentially, controlling the k types and the remaining chores to obtain O(log k).Source: §1.1 · p. 4, §1.2 · p. 5
• For binary additive costs, a universal residual keeps remaining chores low-cost for every type while requiring only that the current bundle be low-cost for its recipient.The algorithm allocates zero-cost chores first, then a fixed-size subset; random selection and conditional-expectation derandomization yield a deterministic 3-competitive algorithm when k ≤ n.Source: §1.2 · p. 5, §1.1 · p. 5

1.3 Related Work

• Prior online chore work largely studies item arrivals; related agent-arrival work considers goods, while this paper studies chores in that complementary model.Prior offline chore results include an O(min{n, log m})-MMS algorithm for subadditive costs.Source: §1 · p. 2, §1.3 · p. 6

2 Preliminaries

• Agents arrive sequentially; each reveals her cost function and must receive an irrevocable bundle of unallocated chores.A full allocation assigns all items.Source: §2 · pp. 6–7
• Cost functions are nonnegative and, unless stated otherwise, normalized to cost 0 for the empty set and assumed monotone.Agents with the same cost function belong to the same type.Source: §2 · p. 7
• An MMS partition divides the chores into n bundles, each costing an agent at most her MMS; the paper fixes one such partition per cost function.The paper assumes this partition is unique, which matters when agents share a cost function.Source: §2 · p. 7
• An allocation is α-MMS when every agent’s bundle costs at most α times her MMS; α = 1 is an MMS allocation.An algorithm is α-competitive if it returns such an allocation for every online instance.Source: §2 · p. 7

3 Unknown Subadditive Cost Functions

• O(min{n, k log^{1+ϵ} k, log m})-MMS is achievable for subadditive costs when k is unknown and the algorithm knows only n and m.The guarantee holds for any constant ϵ > 0.Source: §3 · p. 7, §3.1 · p. 8

3.1 The Online Algorithm

• The algorithm asks each arriving agent to take the largest currently available bundles from her MMS partition, with the requested count adapting as new types appear.It uses the number of distinct types seen so far to set the bundle count; an O(1)-approximate MMS partition can be used in polynomial time without changing the asymptotic ratio.Source: §3.1 · p. 8
• When k is known in advance, fixing the bundle count yields a min{n, k, ⌈log m⌉ + 1}-MMS allocation.The realized types of arriving agents need not be known in advance.Source: §3.1 · p. 10

3.2 Lower Bound on MMS Guarantee

• For subadditive costs, an instance with k monotone submodular types makes every allocation Ω(k)-MMS.This establishes a lower bound in the number of types.Source: §3.2 · p. 10
• No online algorithm achieves o(min{n, k log k, log m}), even for binary additive costs.The lower bounds include an (n − ϵ) barrier and a 1/4 log m barrier.Source: §3.2 · p. 10
• The lower-bound construction uses binary additive costs with nested approval sets, leaving enough items for later agents to incur high MMS approximation ratios.For each arriving agent, the approval set is the set of items still unallocated.Source: §3.2 · pp. 10–11

4 Known Additive Cost Function Types

• The setting allows k > n and types that never appear; costs are normalized so each type has MMS 1.Under this normalization, each item costs at most 1 and the total cost of all items is at most n for each type.Source: §4 · p. 12

4.1 From Online Allocation to Offline Universal Partitions

• An α-MMS universal partition yields an α-competitive online algorithm by assigning a distinct bundle to each arriving agent.The partition guarantees every bundle has cost at most α times the MMS under every type, even though an agent’s type is unknown before arrival.Source: §4.1 · p. 12

-MMS universal partition

• Randomly assigning items to bundles gives a universal-partition existence argument, which conditional expectations derandomize into a polynomial-time construction.The analysis establishes a B-MMS partition when B(log B−1) > 2 log(kn).Source: §4.1 · p. 12, -MMS universal partition · p. 13

4.3 O(log k)-MMS Universal Partition

• A deterministic polynomial-time algorithm constructs an O(log k)-MMS universal partition, yielding an online guarantee independent of n.It builds bundles sequentially, bounding the cost of each new bundle and the remaining items across all k types; the guarantee improves on the previous algorithm when k ≪ n.Source: §4.3 · pp. 14, 16

4.4 Lower Bound for Universal Partitions

• Every universal partition can incur an approximation ratio of Ω(log k log log k), even for binary additive cost functions.The construction ensures that every size-q subset is approved by some type, forcing a bundle to cost at least q while that type’s MMS is 1.Source: §4.4 · p. 17
• The universal-partition lower-bound expression involves log k and log log k.The supplied passage states the expression as “log k log log k” without further mathematical notation.Source: §4.4 · p. 17
• This lower bound applies only to universal partitions and does not directly imply a lower bound for general online algorithms.Source: §4.4 · p. 17

5 Known Binary Additive Cost Function Types

• For unrestricted k, binary additive instances admit no o(log log k) guarantee, so the algorithm focuses on k≤n.Each binary type is determined by its approval set.Source: §5 · p. 18

5.1 The Algorithm and the Invariant

• A universal-residual invariant bounds each type's remaining approval items by 2r·µ_t, allowing the last agent's remaining items to be safely allocated.Here r is the number of remaining agents, and µ_t is the MMS for type t.Source: §5.1 · p. 19

5.2 The Existence and Computation of Set S

• Random sampling establishes a feasible set S in each round, and conditional-expectation derandomization computes it in deterministic polynomial time.The selected set preserves the potential bound needed to maintain the residual invariant.Source: §5.2 · pp. 20–21, §5.1 · p. 20
• For k≤n known binary additive types, a deterministic polynomial-time online algorithm returns a 3-MMS allocation.The cost-function types are known in advance, but agents reveal their types only on arrival.Source: §5 · p. 18, §5.2 · p. 21

5.3 Lower Bound for Bounded k

• Even for constant k, no deterministic online algorithm guarantees a ratio strictly below 2, placing the 3-MMS guarantee between 2 and 3.The lower bound holds for known binary additive cost instances.Source: §5.3 · p. 22
• The paper also reports exact MMS guarantees for k=2 and a 3/2 lower bound for k=7, leaving the relevant values of k open.The open question is which k permit exact MMS or more generally constant-factor approximations.Source: §5.3 · p. 22

6 Conclusion and Open Problems

• The uninformed subadditive setting has a near-optimal competitive ratio of O(min{n, k log^1+ϵ k, log m}) for any constant ϵ > 0.The paper also reports polylogarithmic guarantees for additive costs and constant guarantees for binary additive costs when types are known.Source: §6 · p. 22
• For known types, the optimal competitive ratio's growth with k and the threshold for constant- or 1-competitive algorithms remain unclear.The paper also leaves open whether a universal residual can yield a constant ratio for general additive costs when k ≤ n.Source: §6 · p. 22
• Whether randomized algorithms improve competitive ratios in expectation or with high probability remains an open question.Source: §6 · p. 22

Declaration of AI Use

• The authors developed the main algorithmic framework.Source: Declaration of AI Use · p. 23
• GPT-5.6 Sol assisted in exploring parts of the proofs.Source: Declaration of AI Use · p. 23
• The authors wrote the manuscript, independently verified all arguments, and take full responsibility; ChatGPT and Codex assisted with language editing and literature searches.Source: Declaration of AI Use · p. 23

A Upper Bounds for Known Number of Types

• The algorithm sets ℓ=min{n, k, ⌈log m⌉+1} for every arriving agent.Equivalently, it sets ℓ=min{n, k, L/2}, with L=2(⌈log m⌉+1).Source: A Upper Bounds for Known Number of Types · p. 25
• min{n, k, ⌈log m⌉+1}-MMS is achieved when k is known upfront.Algorithm 3 outputs a complete allocation with this approximation ratio.Source: A Upper Bounds for Known Number of Types · p. 25
• Each agent's cost is bounded by ℓ times her MMS, and the proof establishes that all items are allocated.Completeness is handled in cases based on ℓ, including a pigeonhole argument when ℓ=k.Source: A Upper Bounds for Known Number of Types · p. 25

B Lower Bounds for Known Subadditive Types

• The appendix gives an offline lower bound of Ω(min{n, k, log m/log log m}) for known subadditive type-cost functions.The n- and m-dependent terms follow from Li et al. [LWZ23]; the appendix focuses on the k-dependent term for k≤n.Source: B Lower Bounds for Known Subadditive… · p. 26
• For every k≤n, some instance with k subadditive cost types forces every complete allocation to have MMS approximation ratio Ω(k).The construction yields an agent with cost at least k while every type's MMS is at most 2, giving a ratio of at least k/2.Source: B Lower Bounds for Known Subadditive… · p. 26
• The construction assigns each item a k-coordinate vector and defines each type's cost by the number of distinct values in its corresponding coordinate.For any complete allocation, the proof combines a coordinate value untouched by each type's agents to force an item to remain unallocated under the assumed lower costs.Source: B Lower Bounds for Known Subadditive… · p. 26

• The randomized extraction step in Lemma 4.5 can be implemented deterministically in polynomial time.Source: C Derandomization for O(log k)-MMS… · p. 26
• Items are fixed sequentially, with each remaining item assigned to S with probability 6/(n − i + 1), while the conditional expectation of the potential stays below 1.Source: C Derandomization for O(log k)-MMS… · p. 27
• For each undecided item, the algorithm assigns it to S only when that choice does not increase the conditional expectation; otherwise, it excludes the item.Source: C Derandomization for O(log k)-MMS… · p. 27
• The conditional expectation is computable in polynomial time by evaluating the potential’s required terms for each type and critical type.Source: C Derandomization for O(log k)-MMS… · p. 27

• The set S described in Lemma 5.6 can be computed deterministically in polynomial time.The fixing process makes at most |Bi| decisions, each requiring at most two potential evaluations.Source: D Omitted Proofs from Section 5 · pp. 29–30
• Selecting s = ⌈3 · |Bi|/(2 · (n − i + 1))⌉ items from Bi can be expressed as sequential choices, adding each item with probability q/|R′|.Source: D Omitted Proofs from Section 5 · p. 29
• The sequential selection probability is always at most 1, so the procedure is well-defined.Source: D Omitted Proofs from Section 5 · p. 29
• The sequential procedure has the same distribution as choosing a uniformly random s-subset of Bi, as shown by coupling it to a random permutation.Source: D Omitted Proofs from Section 5 · p. 29
• Fixing each item according to the lower conditional potential preserves the bound E[Φ(Bi \ S, n − i) | (F, U)] ≤ Φ(Ri, n − i + 1).Source: D Omitted Proofs from Section 5 · pp. 29–30
• The conditional potential can be computed in polynomial time by classifying subsets according to their items from U and R′ and precomputing binomial coefficients.Source: D Omitted Proofs from Section 5 · p. 30

• For k = 2, a deterministic online algorithm computes an exact MMS allocation for binary additive costs.The proof maintains an invariant for both types across rounds and gives the last agent all remaining items.Source: E The Existence of Exact MMS for… · pp. 31–32
• For two types, the algorithm allocates zero-cost items first, then selects shared-cost items and, if needed, type-1-only items to preserve both types’ invariants.Source: E The Existence of Exact MMS for… · pp. 31–32
• For k = 7, no deterministic algorithm can guarantee an approximation ratio strictly below 3/2.An 8-agent, 16-item instance forces some agent to receive two costly items despite MMS 1.Source: E The Existence of Exact MMS for… · p. 32