randomized_mms_barrier_breaker_mono
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.
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).
intro m c hc i hMThe 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.
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
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.
/-- 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)