Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

1 Introduction

• The online model reveals each arriving agent’s cost function only upon arrival and requires immediate, irrevocable allocation; the paper studies guarantees without prior future-cost information against an oblivious adversary.The objective is to bound the expected ex-post MMS ratio and also establish constant bounds with probability tending to one as n grows.Source: §1 · p. 2

1.1 Our Contributions

• 3/2 + o(1) is both achievable and asymptotically unavoidable for the expected MMS ratio with binary additive costs.The paper also gives an expected ratio below 1.755 for every n.Source: §1.1 · p. 3
• With binary costs, a randomized variant achieves ratio at most 2 except with probability e−Ω(n), and no algorithm can guarantee the expected 3/2 + o(1) ratio with high probability.Every randomized online algorithm has a fixed oblivious binary instance with realized ratio at least 2 with constant probability.Source: §1.1 · p. 3
• For general additive costs, a randomized algorithm achieves expected MMS ratio 2 + o(1), also with high probability.A variant achieves expected ratio at most 2.594 for every n.Source: §1.1 · p. 3
• For additive rewards, the paper gives expected MMS ratio 1/10 and a hardness result of 0.5, while for 0 < x ≤ 1/15 it guarantees an x-fraction of MMS with probability at least 1 − 85 · x2.At x = 1/15, the stated guarantee is probability 0.62, compared with 0.423 for a 1/24 ratio in.Source: §1.1 · p. 3

1.2 Overview of the Techniques

• For binary chores, randomizing the transition from aggressive to cautious rounds balances an agent’s allocation against the workload left for later arrivals.The analysis compares dependent allocations with an independent sampling process; simply assigning roughly 3µi/2 costly chores yields an expected ratio below 1.755.Source: §1.2 · p. 4

General additive costs.

• For general additive chores, the algorithm fractionally allocates a scheduled share of each remaining chore, then uses weighted pairwise rounding to limit each agent’s rounding error to at most one chore’s cost.A schedule controls the largest fractional workload across arrivals, yielding expected ratio 2 + o(1).Source: General additive costs · pp. 4–5

1.3 Related Work

• Earlier offline MMS results assume all preferences are available before allocation, while online work studies irrevocable allocation under partial information and includes fairness notions other than MMS.Related work covers online cake cutting, sequential goods allocation, and agent-arrival results for goods and chores.Source: §1.3 · pp. 5–6

2 Preliminaries

• The chore set and number of agents are known in advance, costs are nonnegative and additive, and each arriving agent must receive an irrevocable subset of the remaining chores.The complete allocation must partition all chores; the arrival sequence is fixed before the algorithm draws its random coins.Source: §2 · p. 6
• An allocation is α-MMS when every agent’s allocated cost is at most α times her MMS, and the realized MMS ratio is the maximum agent-wise cost-to-MMS ratio.Computing MMS is NP-hard for additive costs, so the algorithms use its value only in the analysis.Source: §2 · p. 6
• An algorithm is α-competitive in expectation when the expected realized ratio is at most α on every instance; a high-probability guarantee has failure probability o(1) as n grows.Source: §2 · p. 6

3 Binary Additive Costs

• The binary allocation rule gives each arriving agent all zero-cost chores and a uniformly random set of roughly α times her MMS in costly chores.The parameter α controls how cautious the algorithm is and can be optimized for the expected ratio.Source: §3 · pp. 6–7

3.1 Two Simple Hard Instances

• A fixed binary instance gives every randomized online algorithm an expected-ratio lower bound tending to 1.5 as n grows.A preceding construction gives a lower bound of 1 + 1/e asymptotically; for n = 2 and n = 3, it gives 5/4 and 35/27, respectively.Source: §3.1 · p. 7

3.2 The Online Algorithm

• For T = n, the expected ratios are at most 1.25, 1.2985, and 1.6722 for n = 2, 3, and 4, respectively.By contrast, T = 0 makes the algorithm cautious from the beginning, with very small probability that many chores remain for the last agent, but its expected-ratio bound does not approach 1.5.Source: §3.2 · p. 10
• A randomized switching time balances aggressive and cautious rounds, yielding an expected ratio approaching 3/2 as n grows.The switching time is drawn before agents arrive; the algorithm uses aggressive quotas initially and cautious quotas after the switch.Source: §3.1 · p. 8, §3.2 · p. 10

Independent-sampling Comparison.

• An auxiliary process replaces dependent selections without replacement with independent uniform samples with replacement, enabling comparison with the algorithm’s selections.The comparison supports bounds for convex decreasing losses and lower-tail estimates, while a repeated-hit argument handles the all-aggressive regime.Source: Independent-sampling Comparison · pp. 11–13

3.4 Expected-Ratio Guarantees

• The next subsection applies the comparison framework to the switching-time choices used in Theorems 3.5 and 3.6.The supplied passage introduces these applications but does not state their guarantees.Source: §3.4 · p. 13
• E[ρ(X)] ≤ 3/2 + 22781/(30e8) < 1.755 for every n, and choosing L = ⌊n^2/5⌋ yields an asymptotic bound of 3/2 + o(1).The finite-n bound follows from max_k≥0 s_k = s_6 = 22781/(30e8); the asymptotic bound uses L = ⌊n^2/5⌋ for n ≥ 16.Source: §3.4 · pp. 15–16

3.5 High-Probability Ratio

• P[ρ(X) ≥ 2] ≥ (n − 2)/(4(2n − 1)) = 1/8 − o(1) for every randomized online algorithm on some fixed oblivious binary instance.The instance has 2n chores and the guarantee holds for every n ≥ 3.Source: §3.5 · p. 16
• P[ρ(X) > 2] ≤ e^(−n/48) for every fixed binary additive instance under the always-cautious algorithm.This algorithm fixes T = 0 and, in each large-core round, assigns a uniformly random set of up to ⌊3κ_i/2⌋ costly chores.Source: §3.5 · p. 17

4.3 Choosing the Schedule

• 2 + o(1) is achieved in expectation and with probability at least 1 − 1/n for general additive costs.A different schedule gives an expected ratio below 2.594 for every n ≥ 2.Source: §4 · p. 17, §4.3 · p. 23

4.1 The Online Algorithm

• A fixed schedule assigns each arriving agent a fraction of every remaining chore before rounding, and the schedule does not depend on reported costs.The last agent receives all chores still unallocated.Source: §4.1 · pp. 18–19
• Weighted Pairwise Rounding preserves total fractional cost and coordinate expectations while making at least one coordinate integral at each pair step.At most one fractional coordinate remains, so the final random choice concerns only one chore.Source: §4.1 · pp. 18–19

4.2 Load Analysis for a General Schedule

• The rounding step keeps each arriving agent’s realized cost within one item of her fractional cost, reducing the ratio analysis to the maximum fractional cost across agents.The bound uses the normalization c_i(e) ≤ 1.Source: §4 · p. 17, §4.2 · p. 20
• The general-schedule analysis compares the dependent remaining set with independent retention through a product invariant, then uses exponential moments to bound fractional costs.The benchmark survival probability before round i is s_i, defined by s_1 = 1 and s_{i+1} = s_i(1 − p_i).Source: §4.2 · p. 20

4.3 Choosing the Schedule

• The schedule is chosen by parameterizing fractions through β_i = n s_i p_i and selecting values so the probability bounds hold simultaneously across rounds.The backward recurrence equalizes the Chernoff exponent at a common threshold.Source: §4.3 · pp. 21–22

• GPT-6 Astra assisted with mathematical analysis and language editing.Source: Declaration for the Use of AI · p. 23
• The assistance also covered notation consistency checks and LaTeX formatting.Source: Declaration for the Use of AI · p. 23
• The authors state that they reviewed and verified the mathematical statements, proofs, calculations, and citations and take full responsibility.Source: Declaration for the Use of AI · p. 23

• For a nonnegative, nonincreasing, convex function, binomial averaging preserves those properties, enabling the repeated nested-core comparison.Source: A Missing Proofs from the Binary-Cost… · p. 27
• The nested-core proof bounds the actual expected truncated payoff by a relaxed continuation value through backward induction.The comparison uses uniform mark locations within a core and a hypergeometric-to-binomial convex comparison.Source: A Missing Proofs from the Binary-Cost… · p. 27
• The relaxed terminal count is a sum of independent Bernoulli variables, whose convex payoff is bounded using a Poisson comparison.This yields an exponential-moment route to the probability estimate.Source: A Missing Proofs from the Binary-Cost… · pp. 27–28
• A Chernoff bound for the relaxed count gives an exponential estimate involving λψ(y/λ), with a quadratic lower bound on that rate function.Source: A Missing Proofs from the Binary-Cost… · p. 28
• The proof of the bound on ratios above two separates cases according to when the core becomes small and conditions on the number of cautious rounds.When all rounds retain large cores, it applies the probability bound to the final core; exhausted-core branches have zero truncated payoff.Source: A Missing Proofs from the Binary-Cost… · pp. 27–28

Two agents

• For two agents, the first receives all zero-cost chores and a uniformly random half-sized subset of the costly chores, while the second gets the remainder.The first agent’s ratio is at most one.Source: B Binary Parameter Choices · p. 29

Three agents

• 4733/3645 < 1.2985 bounds the expected ratio in the three-agent calculation, with maximum excess 1088/3645 at k = 6.Source: B Binary Parameter Choices · p. 29

Four agents

• For four agents, the proof treats early small-core cases separately and otherwise partitions the final core into blocks of at most four chores.The supplied passage describes the method but gives no numerical bound.Source: B Binary Parameter Choices · p. 30

Uniform always-cautious bound

• 1.755 is a uniform upper bound on the expected ratio for every n.Source: B Binary Parameter Choices · p. 30

C Missing Proofs from the General-Additive Analysis

• The pairwise update moves two fractional coordinates in opposite cost-weighted directions, and choosing an endpoint makes at least one coordinate integral.The endpoint probabilities give zero-mean displacement, preserving the coordinates’ conditional expectations.Source: C Missing Proofs from the… · p. 30
• Each pairwise-rounding step preserves both updated coordinates’ conditional expectations and total fractional cost, while making at least one coordinate integral.Thus, after at most |R| − 1 steps, at most one fractional coordinate remains.Source: C Missing Proofs from the… · p. 30
• The induction for the remaining-item process applies the invariant to a deterministic transformed test vector whose coordinates are at least one.The proof also uses the relation s_{i+1} = s_i · (1 − p_i) to establish the next-round invariant.Source: C Missing Proofs from the… · pp. 30–31
• For normalized costs fixed independently of the algorithm’s random choices, the proof substitutes z_e = e^{λp_i c_i(e)} into the invariant and bounds the resulting expression using convexity.The normalization is 0 ≤ c_i(e) ≤ 1 and c_i(M) ≤ n.Source: C Missing Proofs from the… · p. 31
• With K = 2 log n, Lemma 4.8 bounds each deficit 1 − β̂_i using increment B̂_i − B̂_{i+1}; summing by elementary-integral comparison yields σ = 1 + o(1).Source: C Missing Proofs from the… · pp. 31–33

D The Schedule for the Uniform Bound

• The schedule sets β_i = B_i − B_{i+1} and p_i = β_i/B_i, with 0 < β_i ≤ 6/5 and p_n = 1.For rounds where n − i + 1 > q, β_i = 1; the fractions form a valid schedule.Source: D The Schedule for the Uniform Bound · p. 33
• The proof combines one-round moment bounds to establish the schedule’s aggregate bound, then uses fractional-cost probability bounds to obtain the stated guarantee.For n ≥ 200, it separates the final 200 rounds from earlier rounds, where β_i = 1.Source: D The Schedule for the Uniform Bound · pp. 34–35
• The conditional rounding error has exponential moment at most e^{χ(λ)}, uniformly over the final fractional item’s value and cost.The representation is c_i(X_i) = p_i · c_i(R_i) + d · (Z − x), with Z Bernoulli and 0 ≤ d, x ≤ 1.Source: D The Schedule for the Uniform Bound · p. 34
• 2.594: the explicit schedule gives a uniform expected-ratio bound below 2.594 for every n ≥ 2.For 2 ≤ n ≤ 200, the certificate is below 2.5936; for n ≥ 200, it is below 2.579.Source: D The Schedule for the Uniform Bound · p. 35

E Supplementary results for goods

• The goods results use the agent-arrival model with valuations and arrival order fixed before the algorithm’s random choices.The stated algorithms use each arriving agent’s MMS and require no prior information about future valuations.Source: E Supplementary results for goods · p. 35
• The section states an expected-guarantee result for a randomized online algorithm for additive goods for every n.The supplied theorem statement does not include the guarantee’s value.Source: E Supplementary results for goods · p. 35
• A probability-guarantee result is stated for additive goods for every n and 0 < x ≤ 1/15.The theorem statement supplied here does not include the probability bound.Source: E Supplementary results for goods · p. 36
• The section also states an upper bound for every randomized online algorithm on some fixed binary goods instance with 2n items, for even n ≥ 2.The supplied theorem statement does not include the bound’s value.Source: E Supplementary results for goods · p. 36

E.1 The allocation rule and the current agent’s shortfall

• For an agent with positive MMS, the rule divides item values by her original MMS and caps each processed item value at one, leaving the processed MMS exactly one.The proof argues that capping preserves an MMS partition and cannot increase the minimum value of any partition.Source: §E.1 · p. 36
• In a nonfinal round, the rule gives a singleton if a remaining good meets target a; otherwise it uses weighted pairwise rounding, while the final agent receives all remaining goods.If the current agent has zero MMS or zero remaining value, she receives nothing.Source: §E.1 · p. 36
• A singleton meets target a, while in a rounding round each remaining good is worth less than a and the final Bernoulli choice changes fractional value by less than a.The pair steps preserve the agent’s fractional value.Source: §E.1 · p. 36
• When β = p_i · v_i(R_i) ≥ 2a, the agent receives value at least a regardless of the random choices.For the rounding analysis, the received value is represented as β + d · (B − q), where 0 ≤ d ≤ a and B is Bernoulli with mean q.Source: §E.1 · pp. 36–37

E.2 The expected guarantee

• The expected-shortfall proof tracks each future agent’s remaining value relative to one unit per waiting agent and bounds rounding’s increase exponentially.Singleton or empty allocations cannot increase this shortage; the final agent’s shortfall is handled separately.Source: §E.2 · pp. 37, 39

E.3 The probability guarantee

• For probability guarantees, an explicit potential is needed because the exponential estimate loses too much near a failure threshold.The proposed function measures shortage linearly and decays geometrically when remaining value is in surplus.Source: §E.3 · p. 40

E.3.1 Comparing one allocation with independent deletions

• Weighted rounding is compared with independent deletions by showing that expected values of convex nonincreasing shortage functions are bounded by the independent-deletion expectation.The deletion count has independent Bernoulli contributions with means pi · vj(e), and total mean pi · vj(Ri).Source: §E.3.1 · pp. 40, 42

E.3.2 An explicit function measuring shortage

• The potential H(vj(Ri) − k) measures shortage against one unit per waiting agent and is at least the missing value whenever remaining value is below k.H must be nonnegative, nonincreasing, and convex, while dominating the positive part of the shortage.Source: §E.3.2 · p. 43
• H is linear on negative inputs and interpolates between geometrically decreasing values at nonnegative integers.The construction is nonnegative, nonincreasing, and convex, and satisfies H(t) ≥ (−t)+.Source: §E.3.2 · pp. 43–44
• The potential also has an exponential upper bound, enabling the analysis to control expected increases when remaining value is large.The proof gives νλ ≤ 2/e < 1 for later use.Source: §E.3.2 · pp. 44–45
• For independent Bernoulli deletion D with E[D] ≤ ν, the potential satisfies E[H(t + 1 − D)] ≤ H(t) for every real t.The inequality is first established for integer inputs and extended by linear interpolation.Source: §E.3.2 · pp. 44–45

E.3.3 Following the potential until the target arrives

• Tracking H(vj(Ri) − k + m) gives nonincreasing expected potential when remaining value is at most 3k/2 and a geometrically decaying increase otherwise.The shifted potential is followed over earlier rounds until the target arrives.Source: §E.3.3 · pp. 45–46
• Waiting-agent counts are grouped into triples so one integer shift makes all three failure thresholds negative, where H directly measures shortage.Markov’s inequality converts the potential bounds into individual failure-probability bounds.Source: §E.3.3 · pp. 46–47
• The probability bounds are summed across agents, with separate terms for the final agent and for nonfinal agents’ shifted potentials.The final agent receives the remaining set, and its bound is handled separately.Source: §E.3.3 · pp. 47–48
• The union of agent failure probabilities is bounded by 85x^2 for the stated range ending at x = 1/15.The coefficient is maximized at x = 1/15, where z = 3/20, and is less than 85.Source: §E.3.3 · p. 48

E.4 An upper bound for arbitrary online algorithms

• The construction uses 2n items and a uniformly random n-item set C; the first n/2 agents value all items and the remaining n/2 value only C.The two groups’ MMS values are respectively two and one.Source: §E.4 · p. 48
• If an early bundle has at most one item, the realized ratio is at most 1/2; otherwise, the early bundles contain a union U of at least n items.The argument fixes the algorithm’s random seed, making the early bundles independent of C.Source: §E.4 · p. 48
• When fewer than n/2 items of C remain in a selected n-item subset of U, some later agent receives value zero.The analysis averages over the algorithm’s random seed and C to obtain a fixed instance with the same upper-bound guarantee.Source: §E.4 · p. 48