is_alpha_mms_chores
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
- uniform_bivalued_obstruction_no_equal_marginal_exact_mmsFor every integer t at least 2 and every real ratio r strictly between 1 + 1/t and 1 + 1/(t-1), the instance with 4t chores where agent 0…
- equal_weight_allocation_family_lotteryFor at least one agent, if a family of n allocations assigns each chore once to each agent across the n allocations and every family…
- all_agent_bivalued_equal_marginal_divisible_choresFor every n at least two and k at least two, any common ratio r at least one, and any n-agent scaled bivalued additive cost profile on n*k…
- ef1_implies_two_sub_one_div_n_mms_choresFor any n ≥ 2 agents with nonnegative additive costs over m indivisible chores, any EF1 allocation satisfies (2 - 1/n)-MMS.
- is_prefix_alpha_mms_choresAn 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…
- is_ex_post_alpha_mms_choresAn allocation lottery p over allocations of m chores among n agents is ex-post α-MMS for chore costs c if every allocation σ in the…
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)