Auction.SecondPrice.valuation_is_dominant
theoremverifiedformalizationimported Lean
Vickrey's Theorem (core form): Truthful bidding dominates any other bid. For any bid profile b, replacing i's bid with v i does not decrease i's utility.
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 {v : I → U} in theorem Auction.SecondPrice.valuation_is_dominant (v : I → U) (i : I) (b : I → U) : utility v b i ≤ utility v (Function.update b i (v i)) i
- Formalizes
- EconCSLib, `Auction.SecondPrice.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.SecondPrice.valuation_is_dominant← Auction.SecondPrice.valuation_is_dominant (EconCSLib/MechanismDesign/Auction/Vickrey.lean:139): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- Auction.maxBidExcluding_update_selfChanging
i's bid does not affect the highest bid among the others. - Auction.maxBidExcludingThe highest bid excluding bidder
i. - Auction.SecondPrice.bid_winner_eq_maxBidAuction.SecondPrice.bid_winner_eq_maxBid
- Auction.SecondPrice.utility_winnerIf
iis the winner, utility isv i − secondPrice b. - Auction.SecondPrice.bid_le_bid_winnerAuction.SecondPrice.bid_le_bid_winner
- Auction.SecondPrice.maxBidExcluding_eq_maxBid_if_loserAuction.SecondPrice.maxBidExcluding_eq_maxBid_if_loser
- Auction.SecondPrice.utility_nonnegTruthful bidding yields nonneg utility.
- Auction.SecondPrice.secondPriceThe second price: the highest bid among all bidders other than the winner.
- Auction.SecondPrice.utility_loserIf
iis not the winner, utility is0. - Auction.SecondPrice.winnerThe winner of the second-price auction: the bidder with the highest bid. Uses
Auction.argmaxBidfrom… - Auction.maxBidThe highest bid in a profile.
- Auction.SecondPrice.utilityUtility of bidder
iin a second-price auction: winner getsv i − secondPrice b, losers get0.
- Auction.maxBidExcluding_update_selfChanging
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 {v : I → U} in/-- **Vickrey's Theorem** (core form): Truthful bidding dominates any other bid. For any bid profile `b`, replacing `i`'s bid with `v i` does not decrease `i`'s utility. -/theorem Auction.SecondPrice.valuation_is_dominant (v : I → U) (i : I) (b : I → U) : utility v b i ≤ utility v (Function.update b i (v i)) i := by -- Key: maxBidExcluding is unchanged by updating i's bid have key : maxBidExcluding (Function.update b i (v i)) i = maxBidExcluding b i := maxBidExcluding_update_self b i (v i) by_cases h1 : i = winner b · -- Case 1: i wins with current bid b rw [utility_winner h1] by_cases h2 : i = winner (Function.update b i (v i)) · -- Case 1a: i also wins with truthful bid — same maxBidExcluding, same payoff rw [utility_winner h2, sub_le_sub_iff_left] show secondPrice (Function.update b i (v i)) ≤ secondPrice b simp only [secondPrice, ← h1, ← h2, key, le_refl] · -- Case 1b: i loses with truthful bid — utility becomes 0 rw [utility_loser h2, sub_nonpos] -- Goal: v i ≤ secondPrice b = maxBidExcluding b (winner b) = maxBidExcluding b i show v i ≤ secondPrice b rw [secondPrice, ← h1] -- Goal: v i ≤ maxBidExcluding b i set b' := Function.update b i (v i) have hle := bid_le_bid_winner b' i have hmbe := maxBidExcluding_eq_maxBid_if_loser (b := b') h2 rw [bid_winner_eq_maxBid b', ← hmbe, key] at hle rwa [show b' i = v i from Function.update_self i (v i) b] at hle · -- Case 2: i loses with current bid b — utility = 0 rw [utility_loser h1] -- Truthful bid gives nonneg utility exact utility_nonneg (Function.update_self i (v i) b)