SocialChoice.FairDivision.Indivisible.IsMaxminShare
Maximin share (MMS) guarantee: each agent's bundle is at least as valuable as their maximin share value — the best worst-piece they could guarantee by self-partitioning. Formally: for each agent i, for every complete allocation B of allGoods, some bundle in B has value ≤ v_i(A_i) (agent i's bundle in A). This is equivalent to the standard MMS definition: v_i(A_i) ≥ MMS_i where MMS_i = max_{B complete} min_j v_i(B_j) (the maximum over all complete n-partitions of the minimum bundle value for agent i). The equivalence holds because ∀ B, ∃ j, v_i(B_j) ≤ v_i(A_i) is the same as ∀ B, min_j v_i(B_j) ≤ v_i(A_i), i.e., v_i(A_i) ≥ max_B min_j v_i(B_j). This formulation avoids iSup/iInf and is stated directly in the real-valued order. MMS is the weakest standard fairness guarantee in the hierarchy: EF → EFX → EF1 → PROP → MMS (for additive normalized valuations). Key results: - IsProportional.isMaxminShare (in Implications): PROP implies MMS. - MMS allocations almost always exist for additive preferences (Bouveret-Lemaître 2014). - MMS allocations need not always exist (Procaccia-Wang 2014 counterexample). - At least (3/4)-MMS is always achievable for additive preferences. [Fintype N] and [DecidableEq G] are required by IsAllocation. [BCM Ch.12; Budish 2011]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in variable {N G : Type*} in def SocialChoice.FairDivision.Indivisible.IsMaxminShare [Fintype N] [DecidableEq G] (v : Valuation N G) (allGoods : Finset G) (A : Allocation N G) : Prop
- Defined in
- EconCSLib, `SocialChoice.FairDivision.Indivisible.IsMaxminShare`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.SocialChoice.FairDivision.Indivisible.IsMaxminShare← SocialChoice.FairDivision.Indivisible.IsMaxminShare (EconCSLib/SocialChoice/FairDivision/Indivisible/Fairness.lean:179): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 3
- SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
i : Na bundle (a finite subset of goodsG). This is a plain function type alias. The partition… - SocialChoice.FairDivision.Indivisible.IsAllocationA complete allocation partitions all goods among agents. *
disjoint: distinct agents receive disjoint bundles. *complete: every good… - SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in…
- SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
- Used by 2
- SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one
IsMaxminSharefromFairness.leancoincides withIsAlphaMMS 1. → direction (IsMaxminShare → IsAlphaMMS 1): for every complete… - SocialChoice.FairDivision.Indivisible.IsMaxminShare.isAlphaMMS
IsMaxminShareimplies α-MMS forα ≤ 1and nonneg MMS values.
- SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in variable {N G : Type*} in /-- Maximin share (MMS) guarantee: each agent's bundle is at least as valuable as their maximin share value — the best worst-piece they could guarantee by self-partitioning. Formally: for each agent `i`, for every complete allocation `B` of `allGoods`, some bundle in `B` has value ≤ `v_i(A_i)` (agent `i`'s bundle in `A`). This is equivalent to the standard MMS definition: `v_i(A_i) ≥ MMS_i` where `MMS_i = max_{B complete} min_j v_i(B_j)` (the maximum over all complete `n`-partitions of the minimum bundle value for agent `i`). The equivalence holds because `∀ B, ∃ j, v_i(B_j) ≤ v_i(A_i)` is the same as `∀ B, min_j v_i(B_j) ≤ v_i(A_i)`, i.e., `v_i(A_i) ≥ max_B min_j v_i(B_j)`. This formulation avoids `iSup`/`iInf` and is stated directly in the real-valued order. MMS is the weakest standard fairness guarantee in the hierarchy: `EF → EFX → EF1 → PROP → MMS` (for additive normalized valuations). Key results: - `IsProportional.isMaxminShare` (in `Implications`): PROP implies MMS. - MMS allocations almost always exist for additive preferences (Bouveret-Lemaître 2014). - MMS allocations need not always exist (Procaccia-Wang 2014 counterexample). - At least (3/4)-MMS is always achievable for additive preferences. `[Fintype N]` and `[DecidableEq G]` are required by `IsAllocation`. [BCM Ch.12; Budish 2011] -/ def SocialChoice.FairDivision.Indivisible.IsMaxminShare [Fintype N] [DecidableEq G] (v : Valuation N G) (allGoods : Finset G) (A : Allocation N G) : Prop := ∀ i : N, ∀ B : Allocation N G, IsAllocation allGoods B → ∃ j : N, v.val i (B j) ≤ v.val i (A i)