is_prefix_alpha_mms_chores
An allocation σ of m chores between two agents is α-MMS after every prefix if for every k with 1 ≤ k ≤ m, the restriction of σ to the first k chores is α-MMS for the first k chores.
Statement
def is_prefix_alpha_mms_chores (m : ℕ) (α : ℝ) (c : Fin 2 → Fin m → ℝ) (σ : Fin m → Fin 2) : Prop
- Related work
- arXiv:2505.24321
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Built on 1
- is_alpha_mms_choresAn allocation σ of m chores among n agents is α-MMS for cost functions c if each agent i's total cost for her assigned bundle bundle_of σ…
- Used by 2
- has_consistent_online_alpha_mmsGiven ratio r and approximation factor α, there exists a consistent online allocator for two agents that, whenever each agent's cost for…
- adversary_forces_ratioGiven ratio r, factor α, and horizon H, an adversary forces factor α by prefix H on two agents if for every online allocator on H chores,…
Read back from the Lean
For a given number of chores $m : \mathbb{N}$, approximation factor $\alpha : \mathbb{R}$, cost functions $c : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$ for 2 agents, and chore allocation $\sigma : \text{Fin } m \to \text{Fin } 2$:
The predicate is_prefix_alpha_mms_chores m α c σ asserts that for every natural number $k$ such that $1 \le k \le m$, the restriction of the allocation $\sigma$ to the prefix of the first $k$ chores $\{0, \dots, k-1\}$ is an $\alpha$-maximin share allocation for chores (is_alpha_mms_chores) among the 2 agents with cost functions $c$ restricted to the first $k$ chores. That is, for each agent $i \in \text{Fin } 2$, the total cost of the chores allocated to $i$ from the first $k$ chores is at most $\alpha$ times agent $i$'s chore maximin share among 2 agents for the first $k$ chores.
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
/-- An allocation of m chores is alpha-MMS after every prefix if for every prefix length 1 <= k <= m, the restriction of the allocation is alpha-MMS for the restriction of the cost functions. -/ def is_prefix_alpha_mms_chores (m : ℕ) (α : ℝ) (c : Fin 2 → Fin m → ℝ) (σ : Fin m → Fin 2) : Prop := ∀ (k : ℕ) (_ : 1 ≤ k) (hkm : k ≤ m), is_alpha_mms_chores α (fun i (s : Fin k) => c i ⟨s.val, lt_of_lt_of_le s.isLt hkm⟩) (fun (s : Fin k) => σ ⟨s.val, lt_of_lt_of_le s.isLt hkm⟩)