Theorem 2 — random rescaling turns a UT, EPIR α-approximation for welfare into E[RS] ≥ W(N)/(12α(L+1)), L = ⌈log₂(6αn)⌉
OpenMoneyBurningSurplus.Harmonic.Supplement.theorem_2Let agents have valuations in domains of nonnegative valuations on a nonempty finite outcome set , each closed under multiplication by every real . Let . Let be a randomized mechanism with seed that is universally truthful, ex-post individually rational and has nonnegative payments on these domains, and is an -approximation for welfare: for every admissible profile ,
Let be the random-rescaling mechanism with , : independent levels with for and for , scales , one run of on , and payments . Then
- is universally truthful (every pair of a scaling vector and a seed of gives a truthful deterministic mechanism);
- is ex-post individually rational and has nonnegative payments, for every such pair;
- for every admissible profile ,
- , so the surplus approximation factor is .
This is the paper's black-box reduction from welfare to residual surplus; the constant is the one its proof establishes, and the last clause is the step from it to the printed .
Formalization Note The expectation in 3 is a finite sum over level vectors of the Bochner integral over . Measurability of in its seed at admissible profiles is assumed so that expectations are defined; with finitely many outcomes this makes every integrand bounded and integrable. The sentence on invoking once and computational efficiency has no cost model in the paper and is not a Lean clause: the single invocation is the explicit construction.
Differences from the source:
- encoding: agents N = {1,…,n} with n ≥ 2, nonnegative valuations on a nonempty finite outcome set O → Fin n with 2 ≤ n, real-valued functions O → ℝ with pointwise nonnegativity carried by the domain, Fintype O, Nonempty O, DecidableEq O; reason: relabeling and decidable finite membership change no instance
- encoding: a randomized mechanism with internal random seed r drawn independently of the reports → a seed-indexed family (o^r, p^r) on a measurable space with a probability measure μ, measurable in r at admissible profiles; reason: the expectations of §2 require measurability; it excludes no mechanism with finitely many outcomes whose randomness is a random variable
- encoding: UT, EPIR and nonnegative payments of M and of the converted mechanism (EPIR and payments for every (o,p) in the support) → AGT.MechIncentiveCompatible, AGT.IndividuallyRational and AGT.NoPositiveTransfers for every seed; reason: §2 defines UT seedwise, and the proof (PDF 10–11) uses and proves EPIR and nonnegative payments seedwise
- encoding: scalable valuation domains of valuations O → ℝ≥0 → IsScalableDomain V: every member pointwise nonnegative, s • u ∈ V i for every real s > 0; reason: this is the definition on PDF 8; all reports and deviations lie in V
- reading: can be converted into a mechanism with the same properties and surplus approximation factor O(α log n) → the explicit random-rescaling mechanism of PDF 10 is UT, EPIR, has nonnegative payments and E[RS] ≥ W(N)/(12α(L+1)), and L ≤ ⌈log₂(6n²)⌉; reason: the theorem refers to that construction; the explicit constant is the proof's (PDF 12) and implies the printed O(α log n); "the same properties" are the three the proof establishes
- reading: the reduction invokes the starting mechanism once and preserves computational efficiency whenever scaled valuations can be accessed efficiently → no Lean clause; the construction calls M once on the scaled profile; reason: the paper gives no cost model for efficiency, and the single call is visible in the definition of M̃
import Mathlib import Definitions.Def_MoneyBurningSurplus_Harmonic_Model import Definitions.Def_MoneyBurningSurplus_Harmonic_Supplement_Rescaling
namespace MoneyBurningSurplus.Harmonic.Supplement
open MeasureTheory
theorem theorem_2
{n : ℕ} (hn : 2 ≤ n) {O : Type*} [Fintype O] [Nonempty O] [DecidableEq O]
(α : ℝ) (hα1 : 1 ≤ α) (hαn : α ≤ (n : ℝ))
(V : Fin n → Set (O → ℝ)) (hV : IsScalableDomain V)
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(M : SeededMech n O Ω) (hmeas : IsSeedMeasurable V M)
(hUT : IsUniversallyTruthful V M) (hIR : IsExPostIR V M) (hNN : HasNonnegPayments V M)
(hwel : ∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
welfare v Finset.univ / α ≤ expectedWelfare μ M v) :
IsUniversallyTruthful V (rescaledMech M (rescaleLevels n α)) ∧
IsExPostIR V (rescaledMech M (rescaleLevels n α)) ∧
HasNonnegPayments V (rescaledMech M (rescaleLevels n α)) ∧
(∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
welfare v Finset.univ / (12 * α * ((rescaleLevels n α : ℝ) + 1)) ≤
rescaledSurplus μ M (rescaleLevels n α) v) ∧
rescaleLevels n α ≤ ⌈Real.logb 2 (6 * (n : ℝ) ^ 2)⌉₊ := by sorry
end MoneyBurningSurplus.Harmonic.Supplement