Theorem 5 — harmonic MIDR sampling is TIE, EPIR with E[RS] ≥ W_D(N)/H_n, hence αH_n for an α-approximate distributional range
OpenMoneyBurningSurplus.Harmonic.Supplement.theorem_5Let agents have valuations in domains of nonnegative valuations on a nonempty finite outcome set . Let be a nonempty fixed collection of probability distributions on such that, for every admissible profile and every set of agents , the maximum
is attained. Fix a rule choosing a member of every nonempty set of distributions. The harmonic MIDR mechanism draws with probability and a uniform -subset , selects the tie-broken maximizing distribution , draws , and charges
where and , all computed from reports; agents outside pay . Then
- the mechanism is truthful in expectation: for every admissible profile , agent and , agent 's expected utility (over , and , with her true ) at is at least that at ;
- it is ex-post individually rational: at every admissible profile, every seed and every outcome , every agent has ;
- every such payment is nonnegative;
- for every admissible profile, , the expectation over the harmonic sampling and ;
- consequently, for every , if at every admissible profile, then 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 and 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
import Mathlib import Definitions.Def_MoneyBurningSurplus_Harmonic_Model import Definitions.Def_MoneyBurningSurplus_Harmonic_Supplement_MIDR
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