KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest
theoremverifiedformalizationimported Lean
KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open KnapsackAuction in open scoped BigOperators in variable {I : Type*} [Fintype I] [DecidableEq I] [LinearOrder I] [Nonempty I] in omit [LinearOrder I] in lemma KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest (w b : I → Nat) (hwpos : ∀ i, 0 < w i) : ∀ {items : List I}, items.Nodup → ∀ remaining, fractionalSocialWelfare (realBidOfNat b) (natFractionalGreedyList w items remaining) ≤ (natBinarySocialWelfare b (integralGreedyList w items remaining) : ℝ) + highestBidValue b
- Formalizes
- EconCSLib, `KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest`
- 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.KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest← KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest (EconCSLib/MechanismDesign/Auction/Knapsack.lean:923): adapted
What was changed in
KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest--- EconCSLib/MechanismDesign/Auction/Knapsack.lean:923 (KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest) +++ as compiled here @@ -1,3 +1,8 @@ +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open KnapsackAuction in +open scoped BigOperators in +variable {I : Type*} [Fintype I] [DecidableEq I] [LinearOrder I] [Nonempty I] in omit [LinearOrder I] in -lemma natFractionalGreedyList_le_integralGreedyList_plus_highest +lemma KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest (w b : I → Nat) (hwpos : ∀ i, 0 < w i) : @@ -54,3 +59,3 @@ simpa [add_assoc, add_left_comm, add_comm] using - add_le_add_left hfracTail (b i : ℝ) + add_le_add_right hfracTail (b i : ℝ) _ = (natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) : ℝ) + - Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- KnapsackAuction.natFractionalGreedyListFractional greedy prefix algorithm on a natural-number remaining capacity: take each whole item if it fits, and otherwise take exactly the…
- KnapsackAuction.integralGreedyList_supportedOnKnapsackAuction.integralGreedyList_supportedOn
- KnapsackAuction.natFractionalGreedyList_supportedOnKnapsackAuction.natFractionalGreedyList_supportedOn
- KnapsackAuction.integralGreedyListThe integral greedy prefix algorithm: process items in a fixed order, take each whole item if it fits, and halt when the first item fails…
- KnapsackAuction.fractionalSocialWelfareFractional social welfare for a
U-valued allocation vector. - KnapsackAuction.realBidOfNatNatural-number bids viewed as real-valued bids.
- KnapsackAuction.natBinarySocialWelfareInteger-valued welfare of a binary allocation profile.
- KnapsackAuction.highestBidValueHighest single-item value.
- KnapsackAuction.BinaryAllocationA discrete knapsack allocation profile: each agent is either selected or not.
- KnapsackAuction.eq_zero_of_fractionalSupportedOn_of_not_memKnapsackAuction.eq_zero_of_fractionalSupportedOn_of_not_mem
- KnapsackAuction.eq_false_of_supportedOn_of_not_memKnapsackAuction.eq_false_of_supportedOn_of_not_mem
- KnapsackAuction.natBinarySocialWelfare_update_true_of_falseKnapsackAuction.natBinarySocialWelfare_update_true_of_false
- KnapsackAuction.fractionalSocialWelfare_update_one_of_zeroKnapsackAuction.fractionalSocialWelfare_update_one_of_zero
- KnapsackAuction.fractionalSocialWelfare_singletonKnapsackAuction.fractionalSocialWelfare_singleton
- KnapsackAuction.le_highestBidValueKnapsackAuction.le_highestBidValue
- KnapsackAuctionA knapsack auction with public weights
w iand total capacityW. The underlying strategic object is aSingleParameterMechanism I U,…
- Used by 1
- KnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highestKnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highest
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 KnapsackAuction inopen scoped BigOperators invariable {I : Type*} [Fintype I] [DecidableEq I] [LinearOrder I] [Nonempty I] inomit [LinearOrder I] inlemma KnapsackAuction.natFractionalGreedyList_le_integralGreedyList_plus_highest (w b : I → Nat) (hwpos : ∀ i, 0 < w i) : ∀ {items : List I}, items.Nodup → ∀ remaining, fractionalSocialWelfare (realBidOfNat b) (natFractionalGreedyList w items remaining) ≤ (natBinarySocialWelfare b (integralGreedyList w items remaining) : ℝ) + highestBidValue b := by intro items hitems induction items with | nil => intro remaining have hnil : (0 : ℝ) ≤ (natBinarySocialWelfare b (fun _ => false) : ℝ) + highestBidValue b := by positivity simpa [natFractionalGreedyList, integralGreedyList, fractionalSocialWelfare] using hnil | cons i items ih => intro remaining have hnotin : i ∉ items := (List.nodup_cons.mp hitems).1 have htailNodup : items.Nodup := (List.nodup_cons.mp hitems).2 by_cases hfit : w i ≤ remaining · have hfracTail := ih htailNodup (remaining - w i) have hfracZero : natFractionalGreedyList w items (remaining - w i) i = 0 := by exact eq_zero_of_fractionalSupportedOn_of_not_mem (natFractionalGreedyList_supportedOn w items (remaining - w i)) hnotin have hintFalse : integralGreedyList w items (remaining - w i) i = false := by exact eq_false_of_supportedOn_of_not_mem (integralGreedyList_supportedOn w items (remaining - w i)) hnotin have hintEq : (natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) : ℝ) = (b i : ℝ) + natBinarySocialWelfare b (integralGreedyList w items (remaining - w i)) := by exact_mod_cast (show natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) = b i + natBinarySocialWelfare b (integralGreedyList w items (remaining - w i)) by simpa [integralGreedyList, hfit] using (natBinarySocialWelfare_update_true_of_false (b := b) (x := integralGreedyList w items (remaining - w i)) (i := i) hintFalse)) calc fractionalSocialWelfare (realBidOfNat b) (natFractionalGreedyList w (i :: items) remaining) = (b i : ℝ) + fractionalSocialWelfare (realBidOfNat b) (natFractionalGreedyList w items (remaining - w i)) := by simp [natFractionalGreedyList, hfit] simpa [realBidOfNat] using (fractionalSocialWelfare_update_one_of_zero (b := realBidOfNat b) (x := natFractionalGreedyList w items (remaining - w i)) (i := i) hfracZero) _ ≤ (b i : ℝ) + ((natBinarySocialWelfare b (integralGreedyList w items (remaining - w i)) : ℝ) + highestBidValue b) := by simpa [add_assoc, add_left_comm, add_comm] using add_le_add_right hfracTail (b i : ℝ) _ = (natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) : ℝ) + highestBidValue b := by rw [hintEq] ring · have hwipos : 0 < w i := hwpos i have hrem_le : remaining ≤ w i := Nat.le_of_lt (lt_of_not_ge hfit) have hratio_le_one : (remaining : ℝ) / w i ≤ 1 := by exact (div_le_one (by exact_mod_cast hwipos)).2 (by exact_mod_cast hrem_le) calc fractionalSocialWelfare (realBidOfNat b) (natFractionalGreedyList w (i :: items) remaining) = (b i : ℝ) * ((remaining : ℝ) / w i) := by simp [natFractionalGreedyList, hfit] simp [fractionalSocialWelfare_singleton, realBidOfNat] _ ≤ b i := by have hmul : (b i : ℝ) * ((remaining : ℝ) / w i) ≤ (b i : ℝ) * 1 := by exact mul_le_mul_of_nonneg_left hratio_le_one (show 0 ≤ (b i : ℝ) by positivity) simpa using hmul _ ≤ highestBidValue b := by exact_mod_cast le_highestBidValue b i _ ≤ (natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) : ℝ) + highestBidValue b := by have hnonneg : (0 : ℝ) ≤ (natBinarySocialWelfare b (integralGreedyList w (i :: items) remaining) : ℝ) := by positivity exact le_add_of_nonneg_left hnonneg