SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized
theoremverifiedformalizationimported Lean
Explicit payment identity used in Myerson's Lemma: for a DSIC single-parameter mechanism with zero-normalized payments, the payment rule is given pointwise by the Myerson payment identity.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open SingleParameterMechanism in variable {I : Type*} in theorem SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized [DecidableEq I] {x p : (I → ℝ) → I → ℝ} (hdsic : ({ allocationRule := x, paymentRule := p } : SingleParameterMechanism I ℝ).IsDSIC) (h0 : ZeroNormalized p) (b : I → ℝ) (i : I) : p b i = b i * x b i - ∫ z in 0..b i, x (Function.update b i z) i
- Formalizes
- EconCSLib, `SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized`
- 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.SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized← SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized (EconCSLib/MechanismDesign/Auction/Myerson.lean:252): adapted
What was changed in
SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized--- EconCSLib/MechanismDesign/Auction/Myerson.lean:252 (SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized) +++ as compiled here @@ -1,5 +1,6 @@ -/-- Explicit payment identity used in Myerson's Lemma: -for a DSIC single-parameter mechanism with zero-normalized payments, the payment -rule is given pointwise by the Myerson payment identity. -/ -theorem payment_formula_of_isDSIC_of_zeroNormalized [DecidableEq I] +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open SingleParameterMechanism in +variable {I : Type*} in +theorem SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized [DecidableEq I] {x p : (I → ℝ) → I → ℝ} @@ -73,3 +74,3 @@ simpa [add_comm, add_left_comm, add_assoc] using - add_le_add_left (mul_le_mul_of_nonneg_right hkcast hh_nonneg) a + add_le_add_right (mul_le_mul_of_nonneg_right hkcast hh_nonneg) a simpa [htstep k] using hcompare' (t (k + 1)) (t k) hkord - Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- SingleParameterMechanism.withMyersonPayment_isDSIC_of_isMonotoneMyerson Lemma, Property 2: a monotone allocation rule is DSIC when paired with the canonical Myerson payment rule.
- SingleParameterMechanism.payment_difference_boundIf two payment rules implement the same allocation rule in DSIC form, then their difference along a one-dimensional deviation is…
- SingleParameterMechanism.IsDSICDominant-strategy incentive compatibility in the single-parameter, quasi-linear setting. Truthful reporting
θᵢis weakly dominant for… - SingleParameterMechanism.isMonotone_of_isDSICMyerson Lemma, Property 1: every DSIC single-parameter mechanism has a monotone allocation rule.
- SingleParameterMechanismA single-parameter mechanism. Each agent
ihas a single private typeθ_i : R(their "value per unit"). The allocation gives each agent… - MechanismWithTransfersA mechanism with monetary transfers. -
I— agents -T— report/type space of each agent -A— allocation space -P— payment space… - SingleParameterMechanism.ZeroNormalizedZero normalization for payment rules: reporting
0yields payment0, holding the other reports fixed. - SingleParameterMechanism.IsMonotoneMonotonicity of the allocation rule. Agent
i's allocation is non-decreasing ini's reported type, holding all other reports fixed.… - SingleParameterMechanism.myersonPaymentThe canonical Myerson payment formula associated with an allocation rule
x. Holding all other bids fixed, agentipays… - SingleParameterMechanism.myersonPayment_zeroNormalizedThe canonical Myerson payment rule is zero-normalized.
- EconCSLib.StrategicGame.Profile.deviate_selfDeviating to the same strategy is the identity.
- EconCSLib.StrategicGame.Profile.deviate_sameAt the deviated player, the updated profile returns the new strategy.
- EconCSLib.StrategicGame.Profile.deviate_of_neAt every other player, the updated profile is unchanged.
- SingleParameterMechanism.withMyersonPayment_quasiLinearUtility_eqUtility under the canonical Myerson payment rule can be written in the standard envelope-friendly form.
- Used by 2
- SingleParameterMechanism.payment_eq_myersonPayment_of_isDSIC_of_zeroNormalizedUniqueness of zero-normalized DSIC payment rules: among zero-normalized payment rules, the canonical Myerson payment rule is the unique…
- SingleParameterMechanism.payment_formula_of_zeroNormalized_and_isDSICMyerson Lemma
(c): the unique zero-normalized DSIC payment rule from(b)is given by the explicit formula…
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 SingleParameterMechanism invariable {I : Type*} in/-- Explicit payment identity used in Myerson's Lemma: for a DSIC single-parameter mechanism with zero-normalized payments, the payment rule is given pointwise by the Myerson payment identity. -/theorem SingleParameterMechanism.payment_formula_of_isDSIC_of_zeroNormalized [DecidableEq I] {x p : (I → ℝ) → I → ℝ} (hdsic : ({ allocationRule := x, paymentRule := p } : SingleParameterMechanism I ℝ).IsDSIC) (h0 : ZeroNormalized p) (b : I → ℝ) (i : I) : p b i = b i * x b i - ∫ z in 0..b i, x (Function.update b i z) i := by have hx : IsMonotone ({ allocationRule := x, paymentRule := p } : SingleParameterMechanism I ℝ) := isMonotone_of_isDSIC hdsic have hmyersonDSIC : ({ allocationRule := x, paymentRule := myersonPayment x } : SingleParameterMechanism I ℝ).IsDSIC := by exact withMyersonPayment_isDSIC_of_isMonotone (x := x) hx have hcompare : ∀ y z : ℝ, z ≤ y → |(p (Function.update b i y) i - myersonPayment x (Function.update b i y) i) - (p (Function.update b i z) i - myersonPayment x (Function.update b i z) i)| ≤ (y - z) * (x (Function.update b i y) i - x (Function.update b i z) i) := by intro y z hyz simpa using payment_difference_bound (x := x) (p := p) (q := myersonPayment x) hdsic hmyersonDSIC b i y z have hzero_compare : p (Function.update b i 0) i - myersonPayment x (Function.update b i 0) i = 0 := by rw [h0] exact myersonPayment_zeroNormalized x i b |> Eq.symm |> sub_eq_zero.mpr let g : ℝ → ℝ := fun t => x (Function.update b i t) i let d : ℝ → ℝ := fun t => p (Function.update b i t) i - myersonPayment x (Function.update b i t) i have hgmono : Monotone g := by intro s t hst exact hx i s t hst b have hcompare' : ∀ y z : ℝ, z ≤ y → |d y - d z| ≤ (y - z) * (g y - g z) := by intro y z hyz simpa [d, g] using hcompare y z hyz have hd0 : d 0 = 0 := by simpa [d] using hzero_compare have hpartition : ∀ a c : ℝ, a ≤ c → ∀ N : ℕ, 0 < N → |d c - d a| ≤ ((c - a) * (g c - g a)) / N := by intro a c hac N hN let h : ℝ := (c - a) / N let t : ℕ → ℝ := fun k => a + k * h have hN0 : (N : ℝ) ≠ 0 := by exact_mod_cast (Nat.ne_of_gt hN) have hh_nonneg : 0 ≤ h := by dsimp [h] exact div_nonneg (sub_nonneg.mpr hac) (by positivity) have ht0 : t 0 = a := by simp [t] have htN : t N = c := by dsimp [t, h] field_simp [hN0] ring have htstep : ∀ k : ℕ, t (k + 1) - t k = h := by intro k simp [t, Nat.cast_add, Nat.cast_one] ring have hstep_bound : ∀ k ∈ Finset.range N, |d (t (k + 1)) - d (t k)| ≤ h * (g (t (k + 1)) - g (t k)) := by intro k hk have hkcast : (k : ℝ) ≤ (k + 1 : ℕ) := by exact_mod_cast (Nat.le_succ k) have hkord : t k ≤ t (k + 1) := by dsimp [t] simpa [add_comm, add_left_comm, add_assoc] using add_le_add_right (mul_le_mul_of_nonneg_right hkcast hh_nonneg) a simpa [htstep k] using hcompare' (t (k + 1)) (t k) hkord calc |d c - d a| = |d (t N) - d (t 0)| := by rw [htN, ht0] _ = |Finset.sum (Finset.range N) (fun k => d (t (k + 1)) - d (t k))| := by rw [← Finset.sum_range_sub fun k => d (t k)] _ ≤ Finset.sum (Finset.range N) (fun k => |d (t (k + 1)) - d (t k)|) := by simpa using Finset.abs_sum_le_sum_abs (fun k => d (t (k + 1)) - d (t k)) (Finset.range N) _ ≤ Finset.sum (Finset.range N) (fun k => h * (g (t (k + 1)) - g (t k))) := by exact Finset.sum_le_sum hstep_bound _ = h * Finset.sum (Finset.range N) (fun k => g (t (k + 1)) - g (t k)) := by rw [← Finset.mul_sum] _ = h * (g (t N) - g (t 0)) := by rw [Finset.sum_range_sub fun k => g (t k)] _ = ((c - a) / N) * (g c - g a) := by simp [h, htN, ht0] _ = ((c - a) * (g c - g a)) / N := by rw [div_eq_mul_inv, div_eq_mul_inv] ring have hzero_of_abs_le_div_nat : ∀ {u A : ℝ}, 0 ≤ A → (∀ N : ℕ, 0 < N → |u| ≤ A / N) → u = 0 := by intro u A _ hbound have hlim0 : Filter.Tendsto (fun N : ℕ => A / N) Filter.atTop (nhds 0) := by simpa [div_eq_mul_inv, one_div] using (tendsto_const_nhds.mul tendsto_one_div_atTop_nhds_zero_nat : Filter.Tendsto (fun N : ℕ => A * (1 / (N : ℝ))) Filter.atTop (nhds (A * 0))) have hlim : Filter.Tendsto (fun N : ℕ => A / ((N + 1 : ℕ) : ℝ)) Filter.atTop (nhds 0) := by simpa [Function.comp_def] using hlim0.comp (Filter.tendsto_add_atTop_nat 1) have hzero : Filter.Tendsto (fun _ : ℕ => |u|) Filter.atTop (nhds 0) := squeeze_zero (fun _ => abs_nonneg u) (fun N => hbound (N + 1) (Nat.succ_pos N)) hlim exact abs_eq_zero.mp (tendsto_nhds_unique tendsto_const_nhds hzero) have hdb0 : d (b i) - d 0 = 0 := by by_cases hbi : 0 ≤ b i · let A : ℝ := (b i - 0) * (g (b i) - g 0) have hA_nonneg : 0 ≤ A := by dsimp [A] exact mul_nonneg (sub_nonneg.mpr hbi) (sub_nonneg.mpr (hgmono hbi)) have hA_bound : ∀ N : ℕ, 0 < N → |d (b i) - d 0| ≤ A / N := by intro N hN simpa [A, div_eq_mul_inv, mul_assoc, mul_left_comm, mul_comm] using hpartition 0 (b i) hbi N hN exact hzero_of_abs_le_div_nat hA_nonneg hA_bound · have hbi' : b i ≤ 0 := le_of_not_ge hbi let A : ℝ := (0 - b i) * (g 0 - g (b i)) have hA_nonneg : 0 ≤ A := by dsimp [A] exact mul_nonneg (sub_nonneg.mpr hbi') (sub_nonneg.mpr (hgmono hbi')) have hA_bound : ∀ N : ℕ, 0 < N → |d (b i) - d 0| ≤ A / N := by intro N hN simpa [A, abs_sub_comm, div_eq_mul_inv, mul_assoc, mul_left_comm, mul_comm] using hpartition (b i) 0 hbi' N hN exact hzero_of_abs_le_div_nat hA_nonneg hA_bound have hdb : d (b i) = 0 := by rw [hd0, sub_zero] at hdb0 exact hdb0 have hp_eq : p b i - myersonPayment x b i = 0 := by simpa [d, Function.update_eq_self] using hdb simpa [myersonPayment] using sub_eq_zero.mp hp_eq