MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout
theoremverifiedformalizationimported Lean
VCG utility can be rewritten as total welfare under the profile that uses agent i's true valuation and keeps all other reports fixed, minus the maximal welfare achievable by the other agents alone.
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 lemma MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout (reports trueTypes : ∀ _ : I, Valuation A ℝ) (i : I) : MechanismWithTransfers.quasiLinearUtility VCGTransferMechanism valueOfAllocation id id reports trueTypes i = socialWelfare (Function.update reports i (trueTypes i)) (efficientAllocation reports) - maxWelfareWithout reports i
- Formalizes
- EconCSLib, `MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout`
- 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.MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout← MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout (EconCSLib/MechanismDesign/Auction/VCG.lean:193): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- MultipleParameterMechanism.VCGMechanismThe finite-allocation VCG mechanism induced by welfare maximization and Clarke-pivot payments.
- MultipleParameterMechanism.VCGTransferMechanismThe underlying transfer mechanism of
VCGMechanism. This is the object to which the generic definitions inTransfer.lean, such as… - MultipleParameterMechanism.ValuationThe valuation/type space of an agent in a multiple-parameter mechanism.
- MechanismWithTransfers.quasiLinearUtilityQuasi-linear utility induced by: - a valuation function on allocations - an embedding of payments into utility space - subtraction in the…
- MultipleParameterMechanism.valueOfAllocationThe value extractor used by the generic quasi-linear transfer definitions: agent
ievaluates allocationaby applying their valuation… - MultipleParameterMechanism.socialWelfareReported social welfare of allocation
aunder a profile of valuations. - MultipleParameterMechanism.efficientAllocationA welfare-maximizing allocation, chosen noncomputably from finite
A. - MultipleParameterMechanism.maxWelfareWithoutThe maximum reported welfare of agents other than
i. - MultipleParameterMechanism.welfareWithoutReported social welfare of all agents except
i. - MultipleParameterMechanism.welfareWithout_update_selfChanging agent
i's report does not change the welfare of agents other thani. - MultipleParameterMechanism.socialWelfare_eq_value_add_welfareWithoutSocial welfare decomposes into agent
i's value plus the welfare of the other agents. - MultipleParameterMechanismA multiple-parameter mechanism with transfers. Here
Ais the type of feasible allocations andVis the codomain of valuations. Agent… - MultipleParameterMechanism.vcgPaymentThe Clarke-pivot VCG payment charged to agent
i: the best welfare that the other agents could get withouti, minus the other agents'…
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 MultipleParameterMechanism inopen scoped BigOperators invariable {I A : Type*} [Fintype I] [Fintype A] [Nonempty A] invariable [DecidableEq I] in/-- VCG utility can be rewritten as total welfare under the profile that uses agent `i`'s true valuation and keeps all other reports fixed, minus the maximal welfare achievable by the other agents alone. -/lemma MultipleParameterMechanism.VCGMechanism_quasiLinearUtility_eq_socialWelfare_sub_maxWelfareWithout (reports trueTypes : ∀ _ : I, Valuation A ℝ) (i : I) : MechanismWithTransfers.quasiLinearUtility VCGTransferMechanism valueOfAllocation id id reports trueTypes i = socialWelfare (Function.update reports i (trueTypes i)) (efficientAllocation reports) - maxWelfareWithout reports i := by let aStar := efficientAllocation reports have hdecomp : socialWelfare (Function.update reports i (trueTypes i)) aStar = trueTypes i aStar + welfareWithout reports i aStar := by simpa [Function.update, welfareWithout_update_self reports i (trueTypes i) aStar] using socialWelfare_eq_value_add_welfareWithout (Function.update reports i (trueTypes i)) i aStar simp [MechanismWithTransfers.quasiLinearUtility, valueOfAllocation, VCGTransferMechanism, VCGMechanism, vcgPayment] dsimp [aStar] at hdecomp linarith