SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additive
theoremverifiedformalizationimported Lean
For additive valuations, the MMS value is at most the proportional share: n * mmsValue ≤ v_i(allGoods). *Proof*: For any complete B, min_j v_i(B_j) ≤ avg_j v_i(B_j) = v_i(allGoods)/n (minimum ≤ average). Since this bound holds for every B, it holds for the supremum mmsValue = sup_B min_j v_i(B_j). Uses mmsValue_le_of_forall. i : N guarantees Fintype.card N ≥ 1, so division by n is safe. [Budish 2011]
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 lemma SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additive (w : AdditiveValuation N G) (allGoods : Finset G) (i : N) (hne : Nonempty {A : Allocation N G // IsAllocation allGoods A}) : (Fintype.card N : ℝ) * mmsValue w.toValuation allGoods i ≤ w.toValuation.val i allGoods
- Formalizes
- EconCSLib, `SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additive`
- 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.mmsValue_le_proportional_share_additive← SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additive (EconCSLib/SocialChoice/FairDivision/Indivisible/MMS.lean:198): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - 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.mmsValue_le_of_forallThe MMS value is at most any upper bound on all per-allocation minimum bundle values. If
ubis an upper bound — for every complete… - 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.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
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/-- For additive valuations, the MMS value is at most the proportional share: `n * mmsValue ≤ v_i(allGoods)`. *Proof*: For any complete `B`, `min_j v_i(B_j) ≤ avg_j v_i(B_j) = v_i(allGoods)/n` (minimum ≤ average). Since this bound holds for every `B`, it holds for the supremum `mmsValue = sup_B min_j v_i(B_j)`. Uses `mmsValue_le_of_forall`. `i : N` guarantees `Fintype.card N ≥ 1`, so division by `n` is safe. [Budish 2011] -/lemma SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additive (w : AdditiveValuation N G) (allGoods : Finset G) (i : N) (hne : Nonempty {A : Allocation N G // IsAllocation allGoods A}) : (Fintype.card N : ℝ) * mmsValue w.toValuation allGoods i ≤ w.toValuation.val i allGoods := by have hn_pos : (0 : ℝ) < Fintype.card N := Nat.cast_pos.mpr (Fintype.card_pos_iff.mpr ⟨i⟩) have hmms_bound : mmsValue w.toValuation allGoods i ≤ w.toValuation.val i allGoods / (Fintype.card N : ℝ) := by apply mmsValue_le_of_forall w.toValuation allGoods i hne intro B hB rw [le_div_iff₀ hn_pos] calc iInf (fun j : N => w.toValuation.val i (B j)) * (Fintype.card N : ℝ) = (Fintype.card N : ℝ) * iInf (fun j : N => w.toValuation.val i (B j)) := mul_comm _ _ _ = ∑ _j : N, iInf (fun j' : N => w.toValuation.val i (B j')) := by simp [Finset.sum_const, Finset.card_univ, nsmul_eq_mul] _ ≤ ∑ j : N, w.toValuation.val i (B j) := Finset.sum_le_sum (fun j _ => Finite.ciInf_le _ j) _ = w.toValuation.val i allGoods := by simp only [AdditiveValuation.toValuation] rw [hB.complete, Finset.sum_biUnion (fun a _ b _ hab => hB.disjoint a b hab)] calc (Fintype.card N : ℝ) * mmsValue w.toValuation allGoods i ≤ (Fintype.card N : ℝ) * (w.toValuation.val i allGoods / (Fintype.card N : ℝ)) := mul_le_mul_of_nonneg_left hmms_bound (le_of_lt hn_pos) _ = w.toValuation.val i allGoods := by field_simp