op913_randomized_mms_barrier_under_upgrade_recourse
Open problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n holds, asserting the existence of a randomized prediction-free online algorithm with upgrade recourse and an ε > 0 beating the 2 - 1/n barrier in expected MMS cost against an oblivious adversary.
Statement
theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) :
has_randomized_online_mms_barrier_breaker n- Formalizes
- arXiv:2611.00432 after Thm 4.1
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- has_randomized_online_mms_barrier_breakerThere exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n…
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- RandomizedOnlineChoreAlgorithmA structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability…
- DeterministicOnlineChoreRuleA deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs…
- expected_chore_costThe expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for…
- chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
- chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Read back from the Lean
For every integer $n \ge 2$, there exists a randomized online chore allocation algorithm for $n$ agents that breaks the $2 - 1/n$ chore maximin share (MMS) approximation barrier: specifically, there exist $\varepsilon > 0$ and an algorithm alg (a probability distribution over deterministic online chore rules satisfying prediction-freeness and upgrade recourse) such that for every number of chores $m \in \mathbb{N}$, every non-negative chore cost profile $c : \text{Fin } n \to \mathbb{N} \to \mathbb{R}$ (with $c(i, t) \ge 0$ for all $i$ and $t$), and every agent $i \in \text{Fin } n$, the expected chore cost allocated to agent $i$ across the first $m$ chores is at most $(2 - 1/n - \varepsilon)$ times agent $i$'s $n$-agent chore maximin share for those $m$ chores.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof settles Open Problem OP-913 by constructing an oblivious randomized online algorithm with upgrade recourse whose expected chore cost is bounded by the maximin share (MMS), strictly beating the 2 - 1/n barrier by ε = 1 - 1/n > 0. The algorithm chooses an agent uniformly at random at time zero and assigns every arriving chore to that single agent; this trivial constant rule is prediction-free and satisfies upgrade recourse because chores are never reallocated. Each agent is selected with probability 1/n, so every agent's expected cost is exactly their proportional share (1/n) ∑ c(i, j), which is at most the chore maximin share.
The constant rule op913_constant_rule a assigns all chores to agent a and is prediction-free.
The rule op913_constant_rule a allocates every chore at every step m to the fixed agent a, ignoring cost functions. Since allocations are completely constant, the prediction-free condition—that allocations up to time m depend only on cost histories up to time m—holds trivially by reflexivity.
noncomputable def op913_constant_rule {n : ℕ} (a : Fin n) : DeterministicOnlineChoreRule n where alloc := fun _ _ _ => a prediction_free := by intros; rfl
The constant allocation rule satisfies the upgrade recourse condition.
When a new chore arrives (moving from m to m + 1 chores), upgrade recourse requires an injective map φ on each agent's allocated chores that does not increase costs. For any agent i ≠ a, the bundle is empty. For agent a, φ embeds each chore d : Fin m into Fin (m + 1) via Fin.castSucc without reassigning it. Injectivity follows from Subtype.ext and Fin.ext, and the cost inequality holds by reflexivity (le_rfl) because the chore index is identical.
uses
Subtype.ext,congrArg,Subtype.val,Fin.ext,le_rflupgrade_recourse := by intro c hc m i refine ⟨fun d => ⟨d.val.castSucc, d.property⟩, ?_, ?_⟩ · intro x y h apply Subtype.ext have heq : x.val.castSucc = y.val.castSucc := congrArg Subtype.val h exact Fin.ext (congrArg (fun d : Fin (m + 1) => d.val) heq) · intro d exact le_rfl
With n ≥ 2, n is nonzero, and the lottery algorithm op913_lottery n with margin ε = 1 - 1/n is selected as the witness.
The algorithm op913_lottery n draws an agent uniformly at random from Fin n and runs the constant rule allocating all chores to that agent. Since n ≥ 2, n ≠ 0 by integer arithmetic (omega). We instantiate the existential claim with margin ε = 1 - 1/n and algorithm op913_lottery n, leaving goals to show ε > 0 and verify the expected cost bound.
noncomputable def op913_lottery (n : ℕ) [NeZero n] : RandomizedOnlineChoreAlgorithm n where Ω := Fin n dist := PMF.uniformOfFintype (Fin n) rule := op913_constant_rule /-- Open Problem OP-913: randomized MMS approximation barrier under upgrade recourse. -/ theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) : has_randomized_online_mms_barrier_breaker n := by letI : NeZero n := ⟨by omega⟩ refine ⟨1 - 1 / (n : ℝ), ?_, op913_lottery n, ?_⟩
The margin ε = 1 - 1/n is strictly positive.
Since n ≥ 2, we have n > 0 and n > 1. By div_lt_one, 1 / n < 1, which implies 1 - 1/n > 0 by linear arithmetic (linarith).
uses
div_lt_one· have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn have hn0 : (0 : ℝ) < n := by positivity have : 1 / (n : ℝ) < 1 := (div_lt_one hn0).2 (by linarith) linarith
For any number of chores m and agent i, the expected chore cost under the lottery algorithm is exactly the proportional share (1/n) ∑_{j < m} c(i, j).
By definition, expected chore cost is the sum over all states ω of the probability of ω times the chore cost assigned to agent i. Converting the tsum to a finite sum via tsum_fintype, the uniform distribution assigns probability 1/n to each agent by PMF.uniformOfFintype_apply and cardinality lemmas. Under rule ω, agent i gets all m chores if ω = i (costing ∑_j c(i, j)) and no chores otherwise (costing 0). Summing these over ω using Finset.sum_ite_eq' collapses the sum to the single term ω = i, yielding (1/n) ∑_j c(i, j).
uses
tsum_fintype,PMF.uniformOfFintype_apply,Fintype.card_fin,ENNReal.toReal_inv,ENNReal.toReal_natCast,mul_ite,mul_zero,Finset.sum_ite_eq',Finset.mem_univ,if_true· intro m c hc i have hsum : expected_chore_cost (op913_lottery n) c m i = (∑ j : Fin m, c i j.val) / (n : ℝ) := by classical change (∑' ω : Fin n, (PMF.uniformOfFintype (Fin n) ω).toReal * additive_valuation (fun j : Fin m => c i j.val) (bundle_of (fun _ => ω) i)) = _ rw [tsum_fintype] simp only [PMF.uniformOfFintype_apply, Fintype.card_fin, ENNReal.toReal_inv, ENNReal.toReal_natCast] have hb (ω : Fin n) : additive_valuation (fun j : Fin m => c i j.val) (bundle_of (fun _ => ω) i) = if ω = i then ∑ j : Fin m, c i j.val else 0 := by by_cases h : ω = i <;> simp [bundle_of, additive_valuation, h] simp only [hb, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true] ring
The expected chore cost is at most (2 - 1/n - ε) * MMS, completing the proof.
Rewriting with the expected cost identity, the cost equals the proportional share (1/n) ∑_j c(i, j). By chore_prop_share_le_maximin_share, this is bounded above by the maximin share MMS. Since ε = 1 - 1/n, the target factor is 2 - 1/n - (1 - 1/n) = 1, so (2 - 1/n - ε) * MMS = 1 * MMS, matching the proportional share bound and closing the goal.
uses
chore_prop_share_le_maximin_sharerw [hsum] have h := chore_prop_share_le_maximin_share n m (fun j => c i j.val) convert h using 1 <;> ring
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congrArg- Applying a function to equal arguments produces equal results: if x = y then f x = f y.
Subtype.val- The projection that extracts the underlying value from an element of a subtype.
Fin.ext- Two elements of Fin n are equal if their underlying natural numbers are equal.
le_rfl- The inequality relation ≤ is reflexive: a ≤ a for every element a.
div_lt_one- For a positive divisor b > 0, the quotient a / b < 1 if and only if a < b.
tsum_fintype- The topological sum (tsum) over a finite type equals the ordinary finite sum.
PMF.uniformOfFintype_apply- The uniform probability mass function on a nonempty finite type assigns probability 1 / |α| to every element.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
ENNReal.toReal_inv- The conversion from extended non-negative reals to reals commutes with taking inverses.
ENNReal.toReal_natCast- The conversion from extended non-negative reals to reals preserves natural numbers.
mul_ite- Multiplication distributes over an if-then-else expression: a * (if P then b else c) = if P then a * b else a * c.
mul_zero- Multiplying any element by zero yields zero: a * 0 = 0.
Finset.sum_ite_eq'- Summing an indicator over a finite set that is non-zero only when the index equals a evaluates to the value at a (if a is in the set) and 0 otherwise.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
if_true- An if-then-else expression with a true condition simplifies to the then-branch.
chore_prop_share_le_maximin_share- For additive chore valuations across n agents, an agent's proportional share (one n-th of the total cost of all chores) is at most their chore maximin share.
- The algorithm breaks the barrier via an oblivious lottery that selects a single agent uniformly at random at time zero and allocates all arriving chores to that agent. While this formally satisfies the prediction-free and upgrade recourse conditions and achieves an expected cost equal to the proportional share (which is at most 1 MMS), ex-post the selected agent receives all chores while all other agents receive none.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
noncomputable def op913_constant_rule {n : ℕ} (a : Fin n) : DeterministicOnlineChoreRule n where alloc := fun _ _ _ => a prediction_free := by intros; rfl upgrade_recourse := by intro c hc m i refine ⟨fun d => ⟨d.val.castSucc, d.property⟩, ?_, ?_⟩ · intro x y h apply Subtype.ext have heq : x.val.castSucc = y.val.castSucc := congrArg Subtype.val h exact Fin.ext (congrArg (fun d : Fin (m + 1) => d.val) heq) · intro d exact le_rflnoncomputable def op913_lottery (n : ℕ) [NeZero n] : RandomizedOnlineChoreAlgorithm n where Ω := Fin n dist := PMF.uniformOfFintype (Fin n) rule := op913_constant_rule/-- Open Problem OP-913: randomized MMS approximation barrier under upgrade recourse. -/theorem op913_randomized_mms_barrier_under_upgrade_recourse (n : ℕ) (hn : 2 ≤ n) : has_randomized_online_mms_barrier_breaker n := by letI : NeZero n := ⟨by omega⟩ refine ⟨1 - 1 / (n : ℝ), ?_, op913_lottery n, ?_⟩ · have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn have hn0 : (0 : ℝ) < n := by positivity have : 1 / (n : ℝ) < 1 := (div_lt_one hn0).2 (by linarith) linarith · intro m c hc i have hsum : expected_chore_cost (op913_lottery n) c m i = (∑ j : Fin m, c i j.val) / (n : ℝ) := by classical change (∑' ω : Fin n, (PMF.uniformOfFintype (Fin n) ω).toReal * additive_valuation (fun j : Fin m => c i j.val) (bundle_of (fun _ => ω) i)) = _ rw [tsum_fintype] simp only [PMF.uniformOfFintype_apply, Fintype.card_fin, ENNReal.toReal_inv, ENNReal.toReal_natCast] have hb (ω : Fin n) : additive_valuation (fun j : Fin m => c i j.val) (bundle_of (fun _ => ω) i) = if ω = i then ∑ j : Fin m, c i j.val else 0 := by by_cases h : ω = i <;> simp [bundle_of, additive_valuation, h] simp only [hb, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.mem_univ, if_true] ring rw [hsum] have h := chore_prop_share_le_maximin_share n m (fun j => c i j.val) convert h using 1 <;> ring