AFTD Auto-Formalizing Theoretical Domains

dsic_iff_truthful_dominant_strategy

theoremverifiedformalization

For any direct mechanism M and valuation profile v, truthful reporting (the identity strategy profile fun _ => id) is a dominant-strategy equilibrium of M if and only if M is dominant-strategy incentive-compatible.

Statement

theorem dsic_iff_truthful_dominant_strategy
    {Player : Type*} [DecidableEq Player]
    {Theta : Player → Type*} {Outcome : Type*}
    (M : DirectMechanism Player Theta Outcome)
    (v : (i : Player) → Theta i → Outcome → ℝ) :
    is_dominant_strategy_equilibrium M (fun _ => id) v ↔
    is_dominant_strategy_incentive_compatible M v
Formalizes
Tilman Borgers, An Introduction to the Theory of Mechanism Design, Oxford University Press, 2015, Section 2.3
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…
  • 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*},…
  • revelation_principle_dominant_strategyThe Revelation Principle for dominant-strategy equilibrium: if s is a dominant-strategy equilibrium of mechanism M with respect to…

Read back from the Lean

Given a type of players Player with decidable equality, a family of type spaces Theta : Player → Type*, an outcome type Outcome, a direct mechanism M (consisting of an allocation rule M.allocation : (∀ i, Theta i) → Outcome and a payment rule M.payment : Player → (∀ i, Theta i) → ℝ), and a valuation function v : (i : Player) → Theta i → Outcome → ℝ: The truthful strategy profile fun _ => id (where every player reports their true type) is a dominant-strategy equilibrium of M with respect to v if and only if M is dominant-strategy incentive-compatible (DSIC) with respect to v.

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

/-- A direct mechanism is dominant-strategy incentive-compatible if and only if truthful reporting is a dominant-strategy equilibrium. -/theorem dsic_iff_truthful_dominant_strategy    {Player : Type*} [DecidableEq Player]    {Theta : Player → Type*} {Outcome : Type*}    (M : DirectMechanism Player Theta Outcome)    (v : (i : Player) → Theta i → Outcome → ℝ) :    is_dominant_strategy_equilibrium M (fun _ => id) v ↔    is_dominant_strategy_incentive_compatible M v := by  constructor  · intro h i θ θ_i'    have h1 := h i (θ i) θ θ_i'    dsimp at h1    rw [Function.update_eq_self] at h1    exact h1  · intro h i θ_i m m_i'    have h1 := h i (Function.update m i θ_i) m_i'    rw [Function.update_self] at h1    rw [Function.update_idem] at h1    exact h1
See it in the graphDiscuss this resultChallenge it