Lemma 2 — VCG restricted to a nonempty range S has total utility at least Δ(S) = F(S) − F(S∖{o_S})
OpenMoneyBurningSurplus.Harmonic.Supplement.lemma_2algorithmic-game-theorymechanism-designmoney-burningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents have nonnegative valuations on a nonempty finite outcome set , and write . For let if and . For a nonempty , let be the tie-broken maximizer of in and let VCG restricted to charge
With the outcome gap , for every nonempty ,
This is the per-range bound behind the surplus guarantee and the individual rationality of harmonic outcome sampling (Theorem 6).
Formalization Note is a finite maximum with the value on the empty set, exactly the paper's convention; the tie-break rule is the same fixed rule as the mechanism's.
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 fixed, report-independent tie-breaking rule among maximizing outcomes → a universally quantified tb : Finset O → O with IsTieBreak tb (it returns a member of every nonempty set), applied to the computed maximizer set; reason: the rule receives no reports; every instance of the paper's rule satisfies IsTieBreak
Preamble
import Mathlib import Definitions.Def_MoneyBurningSurplus_Harmonic_Model import Definitions.Def_MoneyBurningSurplus_Harmonic_Supplement_Range
Formal statement
namespace MoneyBurningSurplus.Harmonic.Supplement
theorem lemma_2
{n : ℕ} (hn : 2 ≤ n) {O : Type*} [Fintype O] [Nonempty O] [DecidableEq O]
(tb : Finset O → O) (htb : IsTieBreak tb)
(v : Fin n → O → ℝ) (hv : AGT.IsValProfile valuationDomain v)
(S : Finset O) (hS : S.Nonempty) :
outcomeGap tb S v ≤
∑ i : Fin n, (v i (rangeVCGOutcome tb S Finset.univ v) -
rangeVCGPay tb S Finset.univ i 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, Lemma 2, PDF p. 27 (printed p. 26); definitions of F, o_S and Δ, App. D.2, PDF p. 26 (printed p. 25); pivot payment p_i(S_s), App. D.1, PDF p. 26 (printed p. 25)