AFTD Auto-Formalizing Theoretical Domains

randomized_mms_barrier_breaker_mono

theoremverified

Monotonicity of the randomized MMS barrier guarantee: for any number of agents n : ℕ, real numbers ε' ≤ ε, and randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n, if alg guarantees an expected cost at most (2 - 1/n - ε) * chore_maximin_share n (fun d => c i d.val) for all horizons m and nonnegative costs c, then for any m and nonnegative c where the maximin share is nonnegative, alg also guarantees expected cost at most (2 - 1/n - ε') * chore_maximin_share n (fun d => c i d.val).

Statement

theorem randomized_mms_barrier_breaker_mono (n : ℕ) {ε ε' : ℝ} (hle : ε' ≤ ε)
    (alg : RandomizedOnlineChoreAlgorithm n)
    (h : ∀ (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)) :
    ∀ (m : ℕ) (c : Fin n → ℕ → ℝ) (hc : ∀ i t, 0 ≤ c i t) (i : Fin n),
      0 ≤ chore_maximin_share n (fun (d : Fin m) => c i d.val) →
      expected_chore_cost alg c m i ≤
        (2 - 1 / (n : ℝ) - ε') * chore_maximin_share n (fun (d : Fin m) => c i d.val)
Source
arXiv:2611.00432 Sec 4
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
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…

Read back from the Lean

For any number of agents $n \in \mathbb{N}$, real numbers $\varepsilon, \varepsilon' \in \mathbb{R}$ with $\varepsilon' \le \varepsilon$, and any randomized online chore algorithm alg on $n$ agents: If, for every item count $m \in \mathbb{N}$, every non-negative chore cost function $c : \mathrm{Fin}(n) \to \mathbb{N} \to \mathbb{R}$ (i.e., $\forall i, t, 0 \le c(i, t)$), and every agent $i \in \mathrm{Fin}(n)$, the expected chore cost assigned to agent $i$ by alg on the first $m$ items is at most $$\left(2 - \frac{1}{n} - \varepsilon\right) \cdot \mathrm{chore\_maximin\_share}_n(c(i, \cdot)|_m),$$ then for every item count $m \in \mathbb{N}$, every non-negative chore cost function $c : \mathrm{Fin}(n) \to \mathbb{N} \to \mathbb{R}$, and every agent $i \in \mathrm{Fin}(n)$: if $\mathrm{chore\_maximin\_share}_n(c(i, \cdot)|_m) \ge 0$, then the expected chore cost assigned to agent $i$ by alg on the first $m$ items is at most $$\left(2 - \frac{1}{n} - \varepsilon'\right) \cdot \mathrm{chore\_maximin\_share}_n(c(i, \cdot)|_m).$$

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 theorem shows that the randomized MMS approximation guarantee is monotonic in the barrier parameter ε: an algorithm achieving an approximation factor of 2 - 1/n - ε also satisfies the weaker factor 2 - 1/n - ε' for any ε' ≤ ε, provided the chore maximin share is nonnegative. The proof applies the original guarantee and chains it via transitivity with the inequality (2 - 1/n - ε) * M ≤ (2 - 1/n - ε') * M, which holds because ε' ≤ ε and M ≥ 0.

  1. Fix a horizon m, cost matrix c with nonnegative entries, agent i, and assume that agent i's chore maximin share is nonnegative.

    We introduce the universally quantified variables m, c, and i, together with the nonnegativity hypothesis on costs (hc) and the assumption that the chore maximin share is nonnegative (hM).

    line 11

      intro m c hc i hM
  2. The expected chore cost of agent i is at most (2 - 1/n - ε') * chore_maximin_share n (fun d => c i d.val).

    Applying hypothesis h to m, c, hc, and i bounds the expected chore cost by (2 - 1/n - ε) times the chore maximin share. Since ε' ≤ ε (hle) and the maximin share is nonnegative (hM), we have (2 - 1/n - ε) * chore_maximin_share ≤ (2 - 1/n - ε') * chore_maximin_share, which nlinarith proves directly. Chaining these two inequalities by transitivity (trans) yields the required bound.

    line 12

      exact (h m c hc i).trans (by nlinarith)

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

/-- Monotonicity of the randomized MMS approximation factor. -/theorem randomized_mms_barrier_breaker_mono (n : ℕ) {ε ε' : ℝ} (hle : ε' ≤ ε)    (alg : RandomizedOnlineChoreAlgorithm n)    (h : ∀ (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)) :    ∀ (m : ℕ) (c : Fin n → ℕ → ℝ) (hc : ∀ i t, 0 ≤ c i t) (i : Fin n),      0 ≤ chore_maximin_share n (fun (d : Fin m) => c i d.val) →      expected_chore_cost alg c m i ≤        (2 - 1 / (n : ℝ) - ε') * chore_maximin_share n (fun (d : Fin m) => c i d.val) := by  intro m c hc i hM  exact (h m c hc i).trans (by nlinarith)
See it in the graphDiscuss this resultChallenge it