AFTD Auto-Formalizing Theoretical Domains

has_randomized_online_mms_barrier_breaker

def

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

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)
See it in the graphDiscuss this resultChallenge it