AFTD Auto-Formalizing Theoretical Domains

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.
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
Used by 1

Lean source view module on GitHub

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
See it in the graphDiscuss this resultChallenge it