KnapsackAuction.welfareMaximizingAllocationRule_isMonotone
theoremverifiedformalizationimported Lean
KnapsackAuction.welfareMaximizingAllocationRule_isMonotone
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] in lemma KnapsackAuction.welfareMaximizingAllocationRule_isMonotone (A : KnapsackAuction I ℝ) (hW : 0 ≤ A.totalCapacity) : SingleParameterMechanism.IsMonotone ({ allocationRule := A.welfareMaximizingAllocationRule hW paymentRule := A.welfareMaximizingPaymentRule hW } : SingleParameterMechanism I ℝ)
- Formalizes
- EconCSLib, `KnapsackAuction.welfareMaximizingAllocationRule_isMonotone`
- 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.welfareMaximizingAllocationRule_isMonotone← KnapsackAuction.welfareMaximizingAllocationRule_isMonotone (EconCSLib/MechanismDesign/Auction/Knapsack.lean:258): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- KnapsackAuction.feasibleBinaryAllocationsThe finite list of binary allocations satisfying the knapsack constraint.
- KnapsackAuction.welfareMaximizerKnapsackAuction.welfareMaximizer
- KnapsackAuction.welfareMaximizer_geKnapsackAuction.welfareMaximizer_ge
- KnapsackAuction.welfareMaximizingAllocationRuleThe welfare-maximizing allocation rule for the knapsack auction, obtained by choosing a feasible binary allocation with maximal social…
- KnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocationsKnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocations
- KnapsackAuction.welfareMaximizingPaymentRuleThe Myerson payment formula associated with the welfare-maximizing knapsack allocation rule.
- KnapsackAuctionA knapsack auction with public weights
w iand total capacityW. The underlying strategic object is aSingleParameterMechanism I U,… - SingleParameterMechanism.IsMonotoneMonotonicity of the allocation rule. Agent
i's allocation is non-decreasing ini's reported type, holding all other reports fixed.… - SingleParameterMechanismA single-parameter mechanism. Each agent
ihas a single private typeθ_i : R(their "value per unit"). The allocation gives each agent… - MechanismWithTransfersA mechanism with monetary transfers. -
I— agents -T— report/type space of each agent -A— allocation space -P— payment space… - KnapsackAuction.binaryToAllocationThe
0/1allocation vector associated with a binary allocation profile. - KnapsackAuction.BinaryAllocationA discrete knapsack allocation profile: each agent is either selected or not.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - KnapsackAuction.binarySocialWelfareSocial welfare of a binary allocation profile at valuation profile
b. - KnapsackAuction.binarySocialWelfare_updateKnapsackAuction.binarySocialWelfare_update
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] inlemma KnapsackAuction.welfareMaximizingAllocationRule_isMonotone (A : KnapsackAuction I ℝ) (hW : 0 ≤ A.totalCapacity) : SingleParameterMechanism.IsMonotone ({ allocationRule := A.welfareMaximizingAllocationRule hW paymentRule := A.welfareMaximizingPaymentRule hW } : SingleParameterMechanism I ℝ) := by intro i θ θ' hθ b by_cases hEq : θ = θ' · simp [welfareMaximizingAllocationRule, hEq] · have hlt : θ < θ' := lt_of_le_of_ne hθ hEq let bLo := Function.update b i θ let bHi := Function.update b i θ' let xLo := A.welfareMaximizer bLo hW let xHi := A.welfareMaximizer bHi hW have hxLo_feas : xLo ∈ A.feasibleBinaryAllocations := by exact A.welfareMaximizer_mem_feasibleBinaryAllocations bLo hW have hxHi_feas : xHi ∈ A.feasibleBinaryAllocations := by exact A.welfareMaximizer_mem_feasibleBinaryAllocations bHi hW have hLo : binarySocialWelfare bLo xHi ≤ binarySocialWelfare bLo xLo := by exact A.welfareMaximizer_ge bLo hW hxHi_feas have hHi : binarySocialWelfare bHi xLo ≤ binarySocialWelfare bHi xHi := by exact A.welfareMaximizer_ge bHi hW hxLo_feas by_cases hxLo_i : xLo i <;> by_cases hxHi_i : xHi i · simp [welfareMaximizingAllocationRule, bLo, bHi, xLo, xHi, binaryToAllocation, hxLo_i, hxHi_i] · exfalso have hLo' : binarySocialWelfare bLo xHi - binarySocialWelfare bLo xLo ≤ 0 := by linarith have hHi' : 0 ≤ binarySocialWelfare bHi xHi - binarySocialWelfare bHi xLo := by linarith have hHi_eq : binarySocialWelfare bHi xHi = binarySocialWelfare bLo xHi := by rw [binarySocialWelfare_update (b := b) (i := i) (θ := θ') (x := xHi), binarySocialWelfare_update (b := b) (i := i) (θ := θ) (x := xHi)] simp [binaryToAllocation, hxHi_i] have hLo_eq : binarySocialWelfare bHi xLo = binarySocialWelfare bLo xLo + (θ' - θ) := by rw [binarySocialWelfare_update (b := b) (i := i) (θ := θ') (x := xLo), binarySocialWelfare_update (b := b) (i := i) (θ := θ) (x := xLo)] simp [binaryToAllocation, hxLo_i] ring have : 0 < θ' - θ := sub_pos.mpr hlt rw [hHi_eq, hLo_eq] at hHi' linarith · simp [welfareMaximizingAllocationRule, bLo, bHi, xLo, xHi, binaryToAllocation, hxLo_i, hxHi_i] · simp [welfareMaximizingAllocationRule, bLo, bHi, xLo, xHi, binaryToAllocation, hxLo_i, hxHi_i]