Theorem 6 — harmonic outcome sampling is UT, EPIR, nonnegative-payment with E[RS] ≥ W(N)/H_m, m = |O|
OpenMoneyBurningSurplus.Harmonic.Supplement.theorem_6algorithmic-game-theorymechanism-designmoney-burningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents have arbitrary nonnegative valuations on a nonempty finite outcome set with elements, and let . The harmonic outcome-sampling mechanism draws with probability and a uniform -subset , chooses the tie-broken maximizer of in , and charges every agent
Then
- for every and every range , the resulting deterministic mechanism is truthful, ex-post individually rational and has nonnegative payments;
- for every valuation profile,
The factor depends on the number of outcomes rather than the number of agents; combined with Theorem 1 it gives the factor .
Formalization Note The expectation is the finite average over and over the -subsets of ; is Mathlib's harmonic at Fintype.card O, cast to the reals.
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 theorem_6
{n : ℕ} (hn : 2 ≤ n) {O : Type*} [Fintype O] [Nonempty O] [DecidableEq O]
(tb : Finset O → O) (htb : IsTieBreak tb) :
(∀ s ∈ Finset.Icc 1 (Fintype.card O),
∀ S ∈ (Finset.univ : Finset O).powersetCard s,
AGT.MechIncentiveCompatible (valuationDomain (n := n))
(rangeVCGOutcome tb S Finset.univ) (rangeVCGPay tb S Finset.univ) ∧
AGT.IndividuallyRational (valuationDomain (n := n))
(rangeVCGOutcome tb S Finset.univ) (rangeVCGPay tb S Finset.univ) ∧
AGT.NoPositiveTransfers (valuationDomain (n := n))
(rangeVCGOutcome tb S Finset.univ) (rangeVCGPay tb S Finset.univ)) ∧
(∀ v : Fin n → O → ℝ, AGT.IsValProfile valuationDomain v →
welfare v Finset.univ / (harmonic (Fintype.card O) : ℝ) ≤
outcomeSamplingSurplus tb 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 6, PDF p. 26 (printed p. 25); harmonic outcome-sampling mechanism, App. D.1, PDF p. 26 (printed p. 25); proof PDF p. 27 (printed p. 26)