Auction.ReserveSecondPrice.valuation_is_dominant
theoremverifiedformalizationimported Lean
Truthful bidding dominates any other bid in the reserve second-price auction.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in variable {I : Type*} [Fintype I] [Nontrivial I] [DecidableEq I] in variable {U : Type*} [AddCommGroup U] [LinearOrder U] [IsOrderedAddMonoid U] in variable {reserve : U} {v : I → U} in theorem Auction.ReserveSecondPrice.valuation_is_dominant (reserve : U) (v : I → U) (i : I) (b : I → U) : utility reserve v b i ≤ utility reserve v (Function.update b i (v i)) i
- Formalizes
- EconCSLib, `Auction.ReserveSecondPrice.valuation_is_dominant`
- 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.Auction.ReserveSecondPrice.valuation_is_dominant← Auction.ReserveSecondPrice.valuation_is_dominant (EconCSLib/MechanismDesign/Auction/ReserveVickrey.lean:235): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- Auction.ReserveSecondPrice.utility_loserAuction.ReserveSecondPrice.utility_loser
- Auction.maxBidExcluding_update_selfChanging
i's bid does not affect the highest bid among the others. - Auction.ReserveSecondPrice.utility_winnerAuction.ReserveSecondPrice.utility_winner
- Auction.ReserveSecondPrice.utility_nonnegTruthful bidding yields nonnegative utility.
- Auction.ReserveSecondPrice.utilityUtility of bidder
i: the allocated bidder receives value minus the clearing price; all others receive0. - Auction.maxBidExcludingThe highest bid excluding bidder
i. - Auction.ReserveSecondPrice.allocationThe item is sold exactly when the winning bid meets the reserve.
- Auction.ReserveSecondPrice.clearingPriceThe price paid by the winner: the maximum of the reserve and the second price.
- Auction.ReserveSecondPrice.clearingPrice_eq_max_reserve_excluding_of_allocation_eq_someWhen bidder
ireceives the item, the clearing price is the maximum of the reserve and the highest bid excludingi. - Auction.ReserveSecondPrice.bid_le_clearing_threshold_of_not_allocation_update_selfAuction.ReserveSecondPrice.bid_le_clearing_threshold_of_not_allocation_update_self
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 invariable {I : Type*} [Fintype I] [Nontrivial I] [DecidableEq I] invariable {U : Type*} [AddCommGroup U] [LinearOrder U] [IsOrderedAddMonoid U] invariable {reserve : U} {v : I → U} in/-- Truthful bidding dominates any other bid in the reserve second-price auction. -/theorem Auction.ReserveSecondPrice.valuation_is_dominant (reserve : U) (v : I → U) (i : I) (b : I → U) : utility reserve v b i ≤ utility reserve v (Function.update b i (v i)) i := by let bTruth := Function.update b i (v i) by_cases hcurrent : allocation reserve b = some i · rw [utility_winner hcurrent] by_cases htruth : allocation reserve bTruth = some i · rw [utility_winner htruth] have hcurrent_price : clearingPrice reserve b = max reserve (Auction.maxBidExcluding b i) := clearingPrice_eq_max_reserve_excluding_of_allocation_eq_some hcurrent have htruth_price : clearingPrice reserve bTruth = max reserve (Auction.maxBidExcluding b i) := by calc clearingPrice reserve bTruth = max reserve (Auction.maxBidExcluding bTruth i) := clearingPrice_eq_max_reserve_excluding_of_allocation_eq_some htruth _ = max reserve (Auction.maxBidExcluding b i) := by simp [bTruth, Auction.maxBidExcluding_update_self] rw [hcurrent_price, htruth_price] · rw [utility_loser htruth] have hthreshold : v i ≤ clearingPrice reserve b := by have hprice : clearingPrice reserve b = max reserve (Auction.maxBidExcluding b i) := clearingPrice_eq_max_reserve_excluding_of_allocation_eq_some hcurrent have hle : v i ≤ max reserve (Auction.maxBidExcluding b i) := by simpa [bTruth] using bid_le_clearing_threshold_of_not_allocation_update_self reserve b i (v i) htruth simpa [hprice] using hle exact sub_nonpos.mpr hthreshold · rw [utility_loser hcurrent] exact utility_nonneg (reserve := reserve) (v := v) (b := Function.update b i (v i)) (i := i) (by simp)