AFTD Auto-Formalizing Theoretical Domains

is_prefix_alpha_mms_chores

deforiginal

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