Fact 3 — , and without atoms
ProvedLargeSupplyFPA.Asymptotic.fact_3bayes-nash-equilibriumfirst-price-auctionmulti-unit-auctionp2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Consider one -unit first-price auction with agents, value laws and any strategy profile . Let be agent 's interim allocation (uniform tie-breaking) and the distribution function of the -th highest bid. For every bid and every agent :
and if no agent's marginal bid distribution has an atom, then .
This relates the order statistic of the bids to an individual agent's chance of winning. It is used to lower-bound utilities in Theorem 1 and Lemma 4.
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
- encoding: B^(k)(b) = Pr[k-th highest bid ≤ b] = Pr[#{j : b_j > b} ≤ k − 1] → Pr[#{j : b_j > b} < k]; reason: identical for k ≥ 1; at k = 0 both sides of Fact 3 involve B = 0
Preamble
import Mathlib import Definitions.Def_LargeSupplyFPA_Asymptotic_Model import Definitions.Def_LargeSupplyFPA_Asymptotic_Assumptions open MeasureTheory ProbabilityTheory
Formal statement
namespace LargeSupplyFPA.Asymptotic
theorem fact_3 {n : ℕ} (k : ℕ) (V : Fin n → Measure ℝ) (E : Fin n → Kernel ℝ ℝ)
(hV : IsValueProfile V) (hE : IsStrategyProfile E) (b : ℝ) (hb : 0 ≤ b) (i : Fin n) :
(∀ Δ : ℝ, 0 < Δ → kthBidCDF k V E b ≤ alloc k V E i (b + Δ)) ∧
(IsAtomless V E → kthBidCDF k V E b ≤ alloc k V E i b) := 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. 45, Fact 3 (Appendix A.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.