chore_maximin_share
def
The 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 supremum over bundles k : Fin n of the total cost of bundle P k to the agent.
Statement
noncomputable def chore_maximin_share {m : ℕ} (n : ℕ) (u : Fin m → ℝ) : ℝ
- Defined in
- arXiv:2611.00432, Section 2.1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 2
- 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 18
- two_agent_common_bivalued_safe_partitionFor any ratio r with 1 ≤ r ≤ 2, any number of chores m, and any two-agent chore cost profile c satisfying is_scaled_bivalued_chores r c,…
- ido_chore_opposite_pairs_cost_boundsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
- two_agent_bivalued_equal_marginal_sharp_mmsFor two agents (n = 2), ratio r with 1 ≤ r and r ≤ 2, and m chores with a cost profile c : Fin 2 → Fin m → ℝ satisfying…
- three_agent_seven_chores_equal_marginal_sharp_mmsFor three agents, seven chores, any ratio r in [1,2], and any scaled bivalued additive cost profile with common ratio r, there is a…
- ido_opposite_pair_cost_le_four_thirdsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
- 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…
- balanced_high_counts_insufficient_for_sharp_mmsThere are seven chores, costs equal to 1 or 3/2, and a bundle S such that three times the number of chores in S is at most 9, three times…
- ido_remaining_chores_cost_le_one_thirdIn an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at…
- 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 σ…
- balanced_high_count_chore_mms_boundFor n at least two, k at least two and n*k bivalued chores, a bundle of size k whose high-cost count times n is at most the total…
- two_agent_balanced_symmetric_swap_lotteryIf both bundles of a two-way partition cost at most alpha times the maximin share of each agent, the equal mixture of that allocation and…
- ex_post_one_mms_chore_lottery_single_agentFor a single agent (n = 1) and any m indivisible chores with nonnegative additive costs c, there exists an allocation lottery that is…
- op913_randomized_mms_barrier_under_upgrade_recourseOpen problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n…
- chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
- has_randomized_online_mms_barrier_breakerThere exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n…
- randomized_mms_barrier_breaker_monoMonotonicity of the randomized MMS barrier guarantee: for any number of agents n : ℕ, real numbers ε' ≤ ε, and randomized online chore…
- 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.
- large_low_quota_sharp_mms_counterexampleWith eleven agents and sixty-five chores, there is a bivalued cost function with ratio 7/4 and a bundle of six chores that meets the…
Read back from the Lean
Given an implicit natural number m, an explicit natural number n, and a valuation function u : Fin m → ℝ, chore_maximin_share is the real number defined as the infimum over all assignments P : Fin m → Fin n of the supremum over all partition indices k : Fin n of the additive valuation of bundle_of P k.
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
/-- The maximin share (MMS) of an agent with additive chore costs among n agents. -/ noncomputable def chore_maximin_share {m : ℕ} (n : ℕ) (u : Fin m → ℝ) : ℝ := ⨅ P : Fin m → Fin n, ⨆ k : Fin n, additive_valuation u (bundle_of P k)