Lemma 7 — smoothing atoms preserves interim allocations: , and at atoms
ProvedLargeSupplyFPA.Asymptotic.lemma_7bayes-nash-equilibriumfirst-price-auctionmulti-unit-auctionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1price-of-anarchy
Consider a -unit first-price auction with agents, value laws and strategy profile . Let and weights (, the atoms of the marginal bid distributions) with . Let be the interim allocation when every agent's bid is replaced by the smoothed bid of (37)–(38). Then for every agent and every bid :
(i) if , then ;
(ii) if , then
This is the key step of Theorem 3(c). The cumulative shifts keep the order of bids, and the uniform jitter at an atom reproduces uniform tie-breaking.
Differences from the source:
- encoding: a strategy is a map E_i : V_i → Δ(ℝ≥0) from values to bid distributions → a Markov kernel E i : Kernel ℝ ℝ with E i v ((−∞, 0)) = 0 for every v; reason: measurability in v is what makes the marginal bid distribution ∫ E_{i,v} dV_i defined; a law on ℝ with no mass below 0 is a law on ℝ≥0
- generalization: the construction starts from an ϵ-approximate equilibrium E → any strategy profile E; reason: Lemma 7 concerns allocation probabilities only and its proof uses no equilibrium property; the printed setting is the special case
- encoding: x_i(b_i) = E[x̃_i(b̃_i)] for the random bid b̃_i of (38) → x_i(b) = ∫_{[0,1]} x̃_i(b + shift(b) + s_b u) du; reason: the expectation over U ∼ U[0,1] written as a Lebesgue integral
- encoding: bid b_i ∈ ℝ≥0; weights s_p ∈ ℝ>0 for p ∈ P with ∑ s_p < ω → b : ℝ with 0 ≤ b; s : ℝ → ℝ positive on P, summable over P, ∑' < ω; reason: Lean types; values of s off P are irrelevant
Preamble
import Mathlib import Definitions.Def_LargeSupplyFPA_Asymptotic_Model import Definitions.Def_LargeSupplyFPA_Asymptotic_Smoothing open MeasureTheory ProbabilityTheory
Formal statement
namespace LargeSupplyFPA.Asymptotic
theorem lemma_7 {n : ℕ} (k : ℕ) (V : Fin n → Measure ℝ) (E : Fin n → Kernel ℝ ℝ)
(hV : IsValueProfile V) (hE : IsStrategyProfile E)
(ω : ℝ) (hω : 0 < ω) (s : ℝ → ℝ) (hs : IsSmoothingWeights V E ω s)
(i : Fin n) (b : ℝ) (hb : 0 ≤ b) :
(b ∉ atomSet V E →
alloc k V E i b = smoothedAlloc k V E s i (b + atomShift V E s b)) ∧
(b ∈ atomSet V E →
alloc k V E i b =
∫ u in Set.Icc (0 : ℝ) 1, smoothedAlloc k V E s i (b + atomShift V E s b + s b * u)) := by sorry
end LargeSupplyFPA.Asymptotic
Source
Hartline, Shah, vonAllmen, Robust Analysis of First-Price Auctions with Large Supply, STOC 2027 submission (manuscript of November 3, 2026, sha256 2ad8363b…), p. 30, Lemma 7 (construction (37)–(38) p. 29; proof pp. 31–32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.