Auction.FirstPrice.no_dominant_strategy
theoremverifiedformalizationimported Lean
No dominant strategy exists in first-price auctions. For any bidder i and any bid bi, there exists a profile where bidding bi is not optimal for i. Counterexample (from xmum/gametheory): set all opponents to bid bi − a for some a > 0, then i wins with both bi and bi − a but pays less with bi − a.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Auction Auction.FirstPrice 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.FirstPrice.no_dominant_strategy (v : I → U) (i : I) (bi : U) (ha : ∃ a : U, 0 < a) : ¬ IsWeaklyDominant (game v) i bi
- Formalizes
- EconCSLib, `Auction.FirstPrice.no_dominant_strategy`
- 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.FirstPrice.no_dominant_strategy← Auction.FirstPrice.no_dominant_strategy (EconCSLib/MechanismDesign/Auction/FirstPrice.lean:110): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- IsWeaklyDominantStrategy
sis weakly dominant for playeri. - Auction.FirstPrice.gameFirst-price auction as a strategic game. This is also the game induced by
mechanismviaMechanismWithTransfers.toStrategicGame; see… - EconCSLib.StrategicGameA strategic game (normal-form game) with players
Nand utilities inU. The structure records only the bare data: strategy spaces and a… - EconCSLib.StrategicGame.deviateUnilateral deviation in a game-bound profile: player
iswitches tos', while all other players keep their current strategies. - Auction.FirstPrice.winnerThe winner of the first-price auction: the bidder with the highest bid. Uses
Auction.argmaxBidfrom… - Auction.FirstPrice.eq_winner_of_bid_gtAuction.FirstPrice.eq_winner_of_bid_gt
- Auction.FirstPrice.utilityUtility of bidder
iin a first-price auction: winner getsv i − b i(pays own bid), losers get0. - Auction.FirstPrice.utility_winnerIf
iis the winner, utility isv i − b i. - EconCSLib.StrategicGame.Profile.deviate_selfDeviating to the same strategy is the identity.
- EconCSLib.StrategicGame.Profile.deviate_sameAt the deviated player, the updated profile returns the new strategy.
- EconCSLib.StrategicGame.Profile.deviate_of_neAt every other player, the updated profile is unchanged.
- IsWeaklyDominantStrategy
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 Auction Auction.FirstPrice invariable {I : Type*} [Fintype I] [Nontrivial I] [DecidableEq I] invariable {U : Type*} [AddCommGroup U] [LinearOrder U] [IsOrderedAddMonoid U] invariable {v : I → U} in/-- **No dominant strategy exists in first-price auctions.** For any bidder `i` and any bid `bi`, there exists a profile where bidding `bi` is not optimal for `i`. Counterexample (from xmum/gametheory): set all opponents to bid `bi − a` for some `a > 0`, then `i` wins with both `bi` and `bi − a` but pays less with `bi − a`. -/theorem Auction.FirstPrice.no_dominant_strategy (v : I → U) (i : I) (bi : U) (ha : ∃ a : U, 0 < a) : ¬ IsWeaklyDominant (game v) i bi := by obtain ⟨a, ha⟩ := ha intro hdom -- Counterexample: others bid (bi - 2a), i bids (bi - a) vs bi. -- i wins both ways, but pays less with (bi - a), contradicting dominance of bi. set b : I → U := Function.update (fun _ => bi - a - a) i (bi - a) have hwd := hdom (bi - a) b have hb_other : ∀ j, j ≠ i → b j = bi - a - a := by intro j hj; exact Function.update_of_ne hj _ _ have hb_self : b i = bi - a := by simp [b, Function.update_self] -- bi - a - a < bi - a since a > 0 have hlt_a : bi - a - a < bi - a := sub_lt_self _ ha have hi_wins_b : i = winner b := by apply eq_winner_of_bid_gt intro j hj rw [hb_other j hj, hb_self] exact hlt_a -- bi - a - a < bi since a > 0 have hlt_bi : bi - a - a < bi := lt_trans hlt_a (sub_lt_self _ ha) have hi_wins_bi : i = winner (Function.update b i bi) := by apply eq_winner_of_bid_gt intro j hj rw [Function.update_of_ne hj, hb_other j hj, Function.update_self] exact hlt_bi -- Compute both payoffs have h1 : (game v).payoff (Function.update b i (bi - a)) i = v i - (bi - a) := by show utility v (Function.update b i (bi - a)) i = _ rw [show Function.update b i (bi - a) = b from by simp [b, Function.update_idem]] rw [utility_winner hi_wins_b] simp [b, Function.update_self] have h2 : (game v).payoff (Function.update b i bi) i = v i - bi := by show utility v (Function.update b i bi) i = _ rw [utility_winner hi_wins_bi] simp [Function.update_self] rw [h1, h2] at hwd -- hwd : v i - (bi - a) ≤ v i - bi -- i.e. v i - bi + a ≤ v i - bi, i.e. a ≤ 0, contradicting ha have : v i - bi < v i - (bi - a) := by rw [show v i - (bi - a) = v i - bi + a from by abel] exact lt_add_of_pos_right _ ha exact absurd hwd (not_le.mpr this)