AFTD Auto-Formalizing Theoretical Domains

is_alpha_mms_chores

def

An 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 σ i is at most α times her maximin share chore_maximin_share n (c i).

Statement

def is_alpha_mms_chores {m n : ℕ} (α : ℝ) (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop
Defined in
arXiv:2611.00432, Section 2.1
Verified
03 Nov 2026
Axioms
none listed
Built on 3
  • 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…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 6

Read back from the Lean

Given implicit natural numbers $m$ and $n$, a real number $\alpha$, a cost function $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ assigning to each agent $i$ a cost for each chore $j$, and an allocation $\sigma : \text{Fin } m \to \text{Fin } n$ mapping chores to agents, is_alpha_mms_chores is the proposition that for every agent $i : \text{Fin } n$, the total cost of the chores assigned to $i$ under $\sigma$ is at most $\alpha$ times agent $i$'s chore maximin share (which is the infimum over all partitions/assignments $P : \text{Fin } m \to \text{Fin } n$ of the supremum over all bundles $k : \text{Fin } n$ of the cost to agent $i$ of the chores assigned to $k$ under $P$).

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 is α-MMS for chores if each agent's bundle costs at most α times her maximin share. -/
def is_alpha_mms_chores {m n : ℕ} (α : ℝ) (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : Prop := ∀ i : Fin n, additive_valuation (c i) (bundle_of σ i) ≤ α * chore_maximin_share n (c i)
See it in the graphDiscuss this resultChallenge it