AFTD Auto-Formalizing Theoretical Domains

MultipleParameterMechanism.VCGMechanism_truthful_quasiLinearUtility_nonneg

theoremverifiedformalizationimported Lean

If agent i reports truthfully in the VCG mechanism, then their quasi-linear utility is nonnegative against arbitrary reports by the other agents, assuming i's true valuation is nonnegative.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open MultipleParameterMechanism in
open scoped BigOperators in
variable {I A : Type*} [Fintype I] [Fintype A] [Nonempty A] in
variable [DecidableEq I] in
theorem MultipleParameterMechanism.VCGMechanism_truthful_quasiLinearUtility_nonneg
    (v : ∀ _ : I, Valuation A ℝ)
    (hnonneg : ∀ i : I, ∀ a : A, 0 ≤ v i a)
    (i : I) (r : ∀ _ : I, Valuation A ℝ) :
    0 ≤ MechanismWithTransfers.quasiLinearUtility
      VCGTransferMechanism valueOfAllocation id id (Function.update r i (v i)) v i
Formalizes
EconCSLib, `MultipleParameterMechanism.VCGMechanism_truthful_quasiLinearUtility_nonneg`
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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 15
Used by 2

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen MultipleParameterMechanism inopen scoped BigOperators invariable {I A : Type*} [Fintype I] [Fintype A] [Nonempty A] invariable [DecidableEq I] in/-- If agent `i` reports truthfully in the VCG mechanism, then their quasi-linear utility is nonnegative against arbitrary reports by the other agents, assuming `i`'s true valuation is nonnegative. -/theorem MultipleParameterMechanism.VCGMechanism_truthful_quasiLinearUtility_nonneg    (v : ∀ _ : I, Valuation A ℝ)    (hnonneg : ∀ i : I, ∀ a : A, 0 ≤ v i a)    (i : I) (r : ∀ _ : I, Valuation A ℝ) :    0 ≤ MechanismWithTransfers.quasiLinearUtility      VCGTransferMechanism valueOfAllocation id id (Function.update r i (v i)) v i := by  let reports := Function.update r i (v i)  let aStar := efficientAllocation reports  have hi_nonneg : ∀ a : A, 0 ≤ reports i a := by    intro a    simp [reports, hnonneg i a]  have hmax_le :      maxWelfareWithout reports i ≤ socialWelfare reports aStar := by    rw [maxWelfareWithout]    exact Finset.sup'_le Finset.univ_nonempty (welfareWithout reports i)      (fun a _ =>        le_trans (welfareWithout_le_socialWelfare_of_nonneg_i reports i hi_nonneg a)          (efficientAllocation_isOptimal reports a))  have hdecomp :      socialWelfare reports aStar = reports i aStar + welfareWithout reports i aStar :=    socialWelfare_eq_value_add_welfareWithout reports i aStar  have hreport_i : reports i aStar = v i aStar := by    simp [reports]  simp [MechanismWithTransfers.quasiLinearUtility, valueOfAllocation,    VCGTransferMechanism, VCGMechanism, vcgPayment]  dsimp [reports, aStar] at hmax_le hdecomp hreport_i  linarith
See it in the graphDiscuss this resultChallenge it