MultipleParameterMechanism.VCGMechanism_isExPostIR_of_all_nonnegative
theoremverifiedformalizationimported Lean
VCG satisfies the MechanismWithTransfers.isExPostIR predicate under the ambient assumption that every valuation in the unrestricted type space is nonnegative. For concrete domains, this assumption is usually enforced by choosing a nonnegative valuation subtype.
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_isExPostIR_of_all_nonnegative (hnonneg : ∀ v : (∀ _ : I, Valuation A ℝ), ∀ i : I, ∀ a : A, 0 ≤ v i a) : MechanismWithTransfers.isQuasiLinearExPostIR (M := (VCGTransferMechanism : MechanismWithTransfers I (fun _ => Valuation A ℝ) A ℝ)) valueOfAllocation id id
- Formalizes
- EconCSLib, `MultipleParameterMechanism.VCGMechanism_isExPostIR_of_all_nonnegative`
- 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_isExPostIR_of_all_nonnegative← MultipleParameterMechanism.VCGMechanism_isExPostIR_of_all_nonnegative (EconCSLib/MechanismDesign/Auction/VCG.lean:256): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- MultipleParameterMechanism.VCGMechanismThe finite-allocation VCG mechanism induced by welfare maximization and Clarke-pivot payments.
- MultipleParameterMechanism.VCGMechanism_truthful_quasiLinearUtility_nonnegIf agent
ireports truthfully in the VCG mechanism, then their quasi-linear utility is nonnegative against arbitrary reports by the… - 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.isQuasiLinearExPostIREx-post IR for quasi-linear utility, as a specialization of
isExPostIR. - MultipleParameterMechanism.valueOfAllocationThe value extractor used by the generic quasi-linear transfer definitions: agent
ievaluates allocationaby applying their valuation… - MechanismWithTransfersA mechanism with monetary transfers. -
I— agents -T— report/type space of each agent -A— allocation space -P— payment space… - MultipleParameterMechanism.vcgPaymentThe Clarke-pivot VCG payment charged to agent
i: the best welfare that the other agents could get withouti, minus the other agents'… - MultipleParameterMechanism.efficientAllocationA welfare-maximizing allocation, chosen noncomputably from finite
A. - MechanismWithTransfers.quasiLinearUtilityQuasi-linear utility induced by: - a valuation function on allocations - an embedding of payments into utility space - subtraction in the…
- MultipleParameterMechanismA multiple-parameter mechanism with transfers. Here
Ais the type of feasible allocations andVis the codomain of valuations. Agent… - MechanismWithTransfers.isExPostIREx-post individual rationality for a mechanism with transfers, relative to an externally supplied utility rule.
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 satisfies the `MechanismWithTransfers.isExPostIR` predicate under the ambient assumption that every valuation in the unrestricted type space is nonnegative. For concrete domains, this assumption is usually enforced by choosing a nonnegative valuation subtype. -/theorem MultipleParameterMechanism.VCGMechanism_isExPostIR_of_all_nonnegative (hnonneg : ∀ v : (∀ _ : I, Valuation A ℝ), ∀ i : I, ∀ a : A, 0 ≤ v i a) : MechanismWithTransfers.isQuasiLinearExPostIR (M := (VCGTransferMechanism : MechanismWithTransfers I (fun _ => Valuation A ℝ) A ℝ)) valueOfAllocation id id := by intro trueTypes i r simpa [MechanismWithTransfers.quasiLinearUtility, MechanismWithTransfers.isQuasiLinearExPostIR, valueOfAllocation, VCGTransferMechanism, VCGMechanism] using VCGMechanism_truthful_quasiLinearUtility_nonneg (v := trueTypes) (hnonneg trueTypes) i r