has_randomized_online_mms_barrier_breaker
There exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n with upgrade recourse such that for every horizon m : ℕ and every nonnegative arrival cost profile c : Fin n → ℕ → ℝ, every agent i : Fin n has expected cost at most (2 - 1/n - ε) * chore_maximin_share n (fun d => c i d.val).
Statement
def has_randomized_online_mms_barrier_breaker (n : ℕ) : Prop
- Defined in
- arXiv:2611.00432 Sec 4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 3
- expected_chore_costThe expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for…
- 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…
- RandomizedOnlineChoreAlgorithmA structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability…
- Used by 1
- op913_randomized_mms_barrier_under_upgrade_recourseOpen problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n…
Read back from the Lean
The predicate has_randomized_online_mms_barrier_breaker n asserts that for a fixed number of agents n : ℕ:
There exists a real number ε > 0 and a randomized online chore algorithm alg for n agents, such that:
For every number of items m : ℕ,
every cost function c : Fin n → ℕ → ℝ,
assuming all chore costs are non-negative (∀ i t, 0 ≤ c i t),
and for every agent i : Fin n:
The expected chore cost allocated to agent i by alg on the first m chores is at most (2 - 1/n - ε) times the chore maximin share (MMS) of agent i for those m chores (evaluated with respect to agent i's own costs c i).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Property that a randomized online chore algorithm beats the 2 - 1/n MMS factor under upgrade recourse. -/ def has_randomized_online_mms_barrier_breaker (n : ℕ) : Prop := ∃ (ε : ℝ) (_ : 0 < ε) (alg : RandomizedOnlineChoreAlgorithm n), ∀ (m : ℕ) (c : Fin n → ℕ → ℝ) (_ : ∀ i t, 0 ≤ c i t) (i : Fin n), expected_chore_cost alg c m i ≤ (2 - 1 / (n : ℝ) - ε) * chore_maximin_share n (fun (d : Fin m) => c i d.val)