Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — harmonic MIDR sampling is TIE, EPIR with E[RS] ≥ W_D(N)/H_n, hence αH_n for an α-approximate distributional range

Open
MoneyBurningSurplus.Harmonic.Supplement.theorem_5

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmic-game-theorymechanism-designmoney-burningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let n≥2n\ge2n≥2 agents have valuations in domains ViV_iVi​ of nonnegative valuations on a nonempty finite outcome set OOO. Let D\mathcal DD be a nonempty fixed collection of probability distributions on OOO such that, for every admissible profile and every set of agents TTT, the maximum

WD(T)=max⁡D∈DEo∼D[∑i∈Tvi(o)]W_{\mathcal D}(T)=\max_{D\in\mathcal D}\mathbb E_{o\sim D}\Big[\sum_{i\in T}v_i(o)\Big]WD​(T)=D∈Dmax​Eo∼D​[i∈T∑​vi​(o)]

is attained. Fix a rule choosing a member of every nonempty set of distributions. The harmonic MIDR mechanism draws k∈{1,…,n}k\in\{1,\dots,n\}k∈{1,…,n} with probability 1/(kHn)1/(kH_n)1/(kHn​) and a uniform kkk-subset RkR_kRk​, selects the tie-broken maximizing distribution DRkD_{R_k}DRk​​, draws o∼DRko\sim D_{R_k}o∼DRk​​, and charges i∈Rki\in R_ki∈Rk​

pi(o;Rk)={pi(Rk) vi(o)/ai(Rk),ai(Rk)>0,0,ai(Rk)=0,p_i(o;R_k)=\begin{cases}p_i(R_k)\,v_i(o)/a_i(R_k),&a_i(R_k)>0,\\0,&a_i(R_k)=0,\end{cases}pi​(o;Rk​)={pi​(Rk​)vi​(o)/ai​(Rk​),0,​ai​(Rk​)>0,ai​(Rk​)=0,​

where ai(Rk)=Eo∼DRk[vi(o)]a_i(R_k)=\mathbb E_{o\sim D_{R_k}}[v_i(o)]ai​(Rk​)=Eo∼DRk​​​[vi​(o)] and pi(Rk)=WD(Rk∖{i})−Eo∼DRk[∑j∈Rk∖{i}vj(o)]p_i(R_k)=W_{\mathcal D}(R_k\setminus\{i\})-\mathbb E_{o\sim D_{R_k}}\big[\sum_{j\in R_k\setminus\{i\}}v_j(o)\big]pi​(Rk​)=WD​(Rk​∖{i})−Eo∼DRk​​​[∑j∈Rk​∖{i}​vj​(o)], all computed from reports; agents outside RkR_kRk​ pay 000. Then

  1. the mechanism is truthful in expectation: for every admissible profile vvv, agent iii and v~i∈Vi\tilde v_i\in V_iv~i​∈Vi​, agent iii's expected utility E[vi(o)−pi]\mathbb E[v_i(o)-p_i]E[vi​(o)−pi​] (over kkk, RkR_kRk​ and ooo, with her true viv_ivi​) at vvv is at least that at (v~i,v−i)(\tilde v_i,v_{-i})(v~i​,v−i​);
  2. it is ex-post individually rational: at every admissible profile, every seed (k,Rk)(k,R_k)(k,Rk​) and every outcome ooo, every agent has vi(o)−pi(o;Rk)≥0v_i(o)-p_i(o;R_k)\ge0vi​(o)−pi​(o;Rk​)≥0;
  3. every such payment is nonnegative;
  4. for every admissible profile, E[RS]≥WD(N)/Hn\mathbb E[RS]\ge W_{\mathcal D}(N)/H_nE[RS]≥WD​(N)/Hn​, the expectation over the harmonic sampling and o∼DRko\sim D_{R_k}o∼DRk​​;
  5. consequently, for every α>0\alpha>0α>0, if WD(N)≥W(N)/αW_{\mathcal D}(N)\ge W(N)/\alphaWD​(N)≥W(N)/α at every admissible profile, then E[RS]≥W(N)/(αHn)\mathbb E[RS]\ge W(N)/(\alpha H_n)E[RS]≥W(N)/(αHn​) at every admissible profile.

This extends harmonic sampling to maximal-in-distributional-range mechanisms, at the price of truthfulness only in expectation.

Formalization Note Distributions are probability vectors on the finite OOO and WDW_{\mathcal D}WD​ is a supremum whose attainment is the stated hypothesis. Expectations are finite sums.

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 nonempty fixed collection 𝒟 of distributions over O, maxima assumed attained, a fixed tie-break rule among maximizing distributions → a nonempty Set of probability vectors (IsDistRange), W_𝒟 as sSup with the attainment predicate AttainsDistMax as hypothesis, and a universally quantified rule tbD with IsDistTieBreak; reason: O is finite, so distributions are probability vectors; the attainment hypothesis is the paper's
  • generalization: every valuation profile (by default all nonnegative valuations) → every profile in arbitrary domains V i of nonnegative valuations, reports and deviations in V; reason: specializes to the paper's default domain
  • generalization: ex-post IR for every outcome-payment pair in the support → v_i(o) − p_i(o; R_k) ≥ 0 for every seed (k, R_k) and every outcome o ∈ O; reason: covers the support; the proof sketch (PDF 20) shows the bound for every realized o
  • reading: the theorem's conclusions (TIE, EPIR, the bound) → an additional conjunct: nonnegative payments for every seed and outcome; reason: §2 requires every mechanism's payments to lie in ℝ≥0; the proof sketch shows 0 ≤ p_i(o; T)
  • generalization: 𝒟 is an α-approximate distributional range (α ≥ 1 by §2) → every real α > 0; reason: covers every α ≥ 1; for α < 1 the hypothesis forces W(N) = 0
Preamble
import Mathlib
import Definitions.Def_MoneyBurningSurplus_Harmonic_Model
import Definitions.Def_MoneyBurningSurplus_Harmonic_Supplement_MIDR
Formal statement
namespace MoneyBurningSurplus.Harmonic.Supplement

theorem theorem_5
    {n : ℕ} (hn : 2 ≤ n) {O : Type*} [Fintype O] [Nonempty O] [DecidableEq O]
    (Dset : Set (O → ℝ)) (hD : IsDistRange Dset)
    (tbD : Set (O → ℝ) → (O → ℝ)) (htbD : IsDistTieBreak tbD)
    (V : Fin n → Set (O → ℝ)) (hV : ∀ i, ∀ u ∈ V i, ∀ o, 0 ≤ u o)
    (hatt : AttainsDistMax Dset V) :
    (∀ v : Fin n → O → ℝ, AGT.IsValProfile V v → ∀ i : Fin n, ∀ v' ∈ V i,
      midrExpectedUtility tbD Dset (v i) i (Function.update v i v') ≤
        midrExpectedUtility tbD Dset (v i) i v) ∧
    (∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
      ∀ k ∈ Finset.Icc 1 n, ∀ T ∈ (Finset.univ : Finset (Fin n)).powersetCard k,
        ∀ o : O, ∀ i : Fin n,
          0 ≤ v i o - midrPay tbD Dset T i v o) ∧
    (∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
      ∀ k ∈ Finset.Icc 1 n, ∀ T ∈ (Finset.univ : Finset (Fin n)).powersetCard k,
        ∀ o : O, ∀ i : Fin n, 0 ≤ midrPay tbD Dset T i v o) ∧
    (∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
      distWelfare Dset v Finset.univ / (harmonic n : ℝ) ≤ midrSurplus tbD Dset v) ∧
    (∀ α : ℝ, 0 < α →
      (∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
        welfare v Finset.univ / α ≤ distWelfare Dset v Finset.univ) →
      ∀ v : Fin n → O → ℝ, AGT.IsValProfile V v →
        welfare v Finset.univ / (α * (harmonic n : ℝ)) ≤ midrSurplus tbD Dset v) := by sorry

end MoneyBurningSurplus.Harmonic.Supplement
Source
Tomer Ezra, Money Burning Mechanism Design: From Welfare to Surplus, STOC 2027 submission #585 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/585.pdf, Theorem 5, PDF p. 19 (printed p. 18); App. B.2 (attainment assumption, W_D, D_{R_k}, a_i, p_i, realized payment), PDF p. 19 (printed p. 18); proof sketch PDF p. 20 (printed p. 19)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me