AFTD Auto-Formalizing Theoretical Domains

revelation_principle_dominant_strategy

theoremverifiedformalization

The Revelation Principle for dominant-strategy equilibrium: if s is a dominant-strategy equilibrium of mechanism M with respect to valuation profile v, then the induced direct mechanism induced_direct_mechanism M s is dominant-strategy incentive-compatible (is_dominant_strategy_incentive_compatible).

Statement

theorem revelation_principle_dominant_strategy
    {Player : Type*} [DecidableEq Player]
    {Message : Player → Type*} {Theta : Player → Type*} {Outcome : Type*}
    (M : DirectMechanism Player Message Outcome)
    (s : (i : Player) → Theta i → Message i)
    (v : (i : Player) → Theta i → Outcome → ℝ)
    (hs : is_dominant_strategy_equilibrium M s v) :
    is_dominant_strategy_incentive_compatible (induced_direct_mechanism M s) v
Formalizes
Tilman Borgers, An Introduction to the Theory of Mechanism Design, Oxford University Press, 2015, Proposition 2.1
Verified
01 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • DirectMechanismA direct mechanism with player type Player, type spaces Theta i for each player i : Player, and outcome type Outcome, consists of an…
  • induced_direct_mechanismGiven a mechanism M with player type Player, message types Message, and outcome type Outcome, and a strategy profile s mapping each…
  • is_dominant_strategy_equilibriumA strategy profile s : (i : Player) → Theta i → Message i is a dominant-strategy equilibrium of mechanism M under valuation profile v if…
  • is_dominant_strategy_incentive_compatibleFor a direct mechanism (M : DirectMechanism Player Theta Outcome) with {Player : Type*} [DecidableEq Player], {Theta : Player → Type*},…
Used by 1
  • dsic_iff_truthful_dominant_strategyFor any direct mechanism M and valuation profile v, truthful reporting (the identity strategy profile fun _ => id) is a dominant-strategy…

Read back from the Lean

The Revelation Principle for dominant-strategy equilibrium: Let Player be a type with decidable equality, Message and Theta be families of types indexed by Player, and Outcome be a type. Let M be a mechanism with message spaces Message and outcome space Outcome, specified by an allocation rule M.allocation : (∀ i, Message i) → Outcome and payment rules M.payment : Player → (∀ i, Message i) → ℝ. Let s : (i : Player) → Theta i → Message i be a strategy profile, and let v : (i : Player) → Theta i → Outcome → ℝ be the players' quasi-linear valuation functions. If s is a dominant-strategy equilibrium in M with respect to v—meaning that for every player i, true type θ_i : Theta i, message profile m : ∀ j, Message j, and alternate message m_i' : Message i, player i's utility from playing s i θ_i against m is at least their utility from playing m_i' against m—then the direct mechanism induced by M and s is dominant-strategy incentive compatible with respect to v (that is, truth-telling is a dominant strategy in the induced direct mechanism).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Revelation Principle: if s is a dominant-strategy equilibrium of mechanism M, the induced direct mechanism is dominant-strategy incentive-compatible. -/theorem revelation_principle_dominant_strategy    {Player : Type*} [DecidableEq Player]    {Message : Player → Type*} {Theta : Player → Type*} {Outcome : Type*}    (M : DirectMechanism Player Message Outcome)    (s : (i : Player) → Theta i → Message i)    (v : (i : Player) → Theta i → Outcome → ℝ)    (hs : is_dominant_strategy_equilibrium M s v) :    is_dominant_strategy_incentive_compatible (induced_direct_mechanism M s) v := by  intro i θ θ_i'  have h_dev := hs i (θ i) (fun j => s j (θ j)) (s i θ_i')  have h1 : (fun j => s j (Function.update θ i θ_i' j)) =      Function.update (fun j => s j (θ j)) i (s i θ_i') := by    ext j    by_cases h : j = i    · subst h; simp    · simp [h]  rw [Function.update_eq_self i (fun j => s j (θ j))] at h_dev  dsimp [induced_direct_mechanism]  rw [h1]  exact h_dev
See it in the graphDiscuss this resultChallenge it