SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one
IsMaxminShare from Fairness.lean coincides with IsAlphaMMS 1. → direction (IsMaxminShare → IsAlphaMMS 1): for every complete B, there exists j with v_i(B_j) ≤ v_i(A_i), so iInf_j v_i(B_j) ≤ v_i(A_i). Then ciSup_le gives mmsValue ≤ v_i(A_i), and 1 * mmsValue = mmsValue by one_mul. ← direction (IsAlphaMMS 1 → IsMaxminShare): for any complete B, iInf_j v_i(B_j) ≤ mmsValue ≤ v_i(A_i). Since N is Nonempty and Fintype, the infimum is achieved at some j*, giving v_i(B_{j*}) ≤ v_i(A_i). [Nonempty N] ensures iInf is nonempty. [Fintype G] makes the allocation subtype [Finite], enabling Finite.le_ciSup in the ← direction. hne is required by the → direction (to call ciSup_le).
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in variable {N G : Type*} in variable [Fintype N] [DecidableEq G] in theorem SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one [Nonempty N] [Fintype G] (v : Valuation N G) (allGoods : Finset G) (A : Allocation N G) (hne : Nonempty {A' : Allocation N G // IsAllocation allGoods A'}) : IsMaxminShare v allGoods A ↔ IsAlphaMMS 1 v allGoods A
- Formalizes
- EconCSLib, `SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one`
- 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_iff_isAlphaMMS_one← SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one (EconCSLib/SocialChoice/FairDivision/Indivisible/MMS.lean:247): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.IsAlphaMMSAn allocation
Ais α-MMS if every agent receives at leastαtimes their MMS value.… - SocialChoice.FairDivision.Indivisible.IsAllocationA complete allocation partitions all goods among agents. *
disjoint: distinct agents receive disjoint bundles. *complete: every good… - SocialChoice.FairDivision.Indivisible.IsMaxminShareMaximin share (MMS) guarantee: each agent's bundle is at least as valuable as their maximin share value — the best worst-piece they could…
- 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.mmsValueThe maximin share (MMS) value of agent
iwith respect to valuationvand good setallGoods.…
- SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
- Used by 1
- SocialChoice.FairDivision.Indivisible.IsMaxminShare.isAlphaMMS
IsMaxminShareimplies α-MMS forα ≤ 1and nonneg MMS values.
- SocialChoice.FairDivision.Indivisible.IsMaxminShare.isAlphaMMS
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset invariable {N G : Type*} invariable [Fintype N] [DecidableEq G] in/-- `IsMaxminShare` from `Fairness.lean` coincides with `IsAlphaMMS 1`. **→ direction** (`IsMaxminShare → IsAlphaMMS 1`): for every complete `B`, there exists `j` with `v_i(B_j) ≤ v_i(A_i)`, so `iInf_j v_i(B_j) ≤ v_i(A_i)`. Then `ciSup_le` gives `mmsValue ≤ v_i(A_i)`, and `1 * mmsValue = mmsValue` by `one_mul`. **← direction** (`IsAlphaMMS 1 → IsMaxminShare`): for any complete `B`, `iInf_j v_i(B_j) ≤ mmsValue ≤ v_i(A_i)`. Since `N` is `Nonempty` and `Fintype`, the infimum is achieved at some `j*`, giving `v_i(B_{j*}) ≤ v_i(A_i)`. `[Nonempty N]` ensures `iInf` is nonempty. `[Fintype G]` makes the allocation subtype `[Finite]`, enabling `Finite.le_ciSup` in the ← direction. `hne` is required by the → direction (to call `ciSup_le`). -/theorem SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one [Nonempty N] [Fintype G] (v : Valuation N G) (allGoods : Finset G) (A : Allocation N G) (hne : Nonempty {A' : Allocation N G // IsAllocation allGoods A'}) : IsMaxminShare v allGoods A ↔ IsAlphaMMS 1 v allGoods A := by constructor · intro hmms simp only [IsAlphaMMS, one_mul] intro i haveI : Nonempty {A' : Allocation N G // IsAllocation allGoods A'} := hne apply ciSup_le intro ⟨B, hB⟩ obtain ⟨j, hj⟩ := hmms i B hB exact le_trans (Finite.ciInf_le (fun j' => v.val i (B j')) j) hj · intro halpha i B hB simp only [IsAlphaMMS, one_mul] at halpha haveI : Fintype (Finset G) := Finset.fintype haveI : DecidableEq N := Classical.typeDecidableEq N haveI : Fintype (Allocation N G) := @Pi.instFintype N (fun _ => Finset G) _ _ (fun _ => inferInstance) haveI : DecidablePred (fun A' : Allocation N G => IsAllocation allGoods A') := Classical.decPred _ haveI : Finite {A' : Allocation N G // IsAllocation allGoods A'} := inferInstance obtain ⟨j, _, hj_min⟩ := Finset.exists_min_image Finset.univ (fun j => v.val i (B j)) ⟨Classical.choice ‹Nonempty N›, Finset.mem_univ _⟩ refine ⟨j, ?_⟩ by_contra h_neg push_neg at h_neg have h1 : iInf (fun j' : N => v.val i (B j')) = v.val i (B j) := le_antisymm (Finite.ciInf_le _ j) (le_ciInf fun j' => hj_min j' (Finset.mem_univ _)) have h2 : v.val i (A i) < iInf (fun j' : N => v.val i (B j')) := h1 ▸ h_neg have h3 : iInf (fun j' : N => v.val i (B j')) ≤ mmsValue v allGoods i := Finite.le_ciSup (fun B' : {A' : Allocation N G // IsAllocation allGoods A'} => iInf fun j' => v.val i (B'.val j')) ⟨B, hB⟩ exact absurd (lt_of_lt_of_le h2 (le_trans h3 (halpha i))) (lt_irrefl _)