Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6, p. 24 — for every τ > 0, E[Δ̂^τ_SP] = Ψ′_τ(ρ)

Proved
MarketInterference.FiniteSample.theorem_6

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

estimatorexperimentationlinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1poissonshadow-prices

Fix a matching network (any finite set of intermediate nodes, any arc values, any capacities k≥0k\ge0k≥0), a control demand rate λ≥0\lambda\ge0λ≥0, a treatment effect β\betaβ with λ+β≥0\lambda+\beta\ge0λ+β≥0, a supply rate π≥0\pi\ge0π≥0, a treatment fraction ρ∈(0,1)\rho\in(0,1)ρ∈(0,1) and a density τ>0\tau>0τ>0. Let Ψτ(η)=E[1τΦτ(Dτ,λ+ηβ,Sτ,π)]\Psi_\tau(\eta)=\mathbb E\big[\frac1\tau\Phi_\tau(D^{\tau,\lambda+\eta\beta},S^{\tau,\pi})\big]Ψτ​(η)=E[τ1​Φτ​(Dτ,λ+ηβ,Sτ,π)] be the finite-sample partial-treatment value function, and let Δ^SPτ\hat\Delta^\tau_{SP}Δ^SPτ​ be the shadow-price estimator computed from the experiment's independent control counts Diτ,control∼Poisson((1−ρ)λiτ)D^{\tau,\mathrm{control}}_i\sim\mathrm{Poisson}((1-\rho)\lambda_i\tau)Diτ,control​∼Poisson((1−ρ)λi​τ), treatment counts Diτ,treatment∼Poisson(ρ(λi+βi)τ)D^{\tau,\mathrm{treatment}}_i\sim\mathrm{Poisson}(\rho(\lambda_i+\beta_i)\tau)Diτ,treatment​∼Poisson(ρ(λi​+βi​)τ) and supply counts Sjτ∼Poisson(πjτ)S^\tau_j\sim\mathrm{Poisson}(\pi_j\tau)Sjτ​∼Poisson(πj​τ), with the negative-demand subgradient A−A^-A− of the experiment LP. Then Ψτ\Psi_\tauΨτ​ is differentiable at ρ\rhoρ and

E[Δ^SPτ]=∂∂η E[1τΦτ(Dτ,λ+ηβ,Sτ,π)]∣η=ρ=Ψτ′(ρ).(14)\mathbb E\big[\hat\Delta^\tau_{SP}\big]=\frac{\partial}{\partial\eta}\,\mathbb E\Big[\frac1\tau\Phi_\tau(D^{\tau,\lambda+\eta\beta},S^{\tau,\pi})\Big]\Big|_{\eta=\rho}=\Psi_\tau'(\rho). \tag{14}E[Δ^SPτ​]=∂η∂​E[τ1​Φτ​(Dτ,λ+ηβ,Sτ,π)]​η=ρ​=Ψτ′​(ρ).(14)

In expectation, the shadow-price estimator measures the slope of the partial-treatment value function at the experiment state, at every finite market size and with no uniqueness assumption on the optimal duals. Combined with a bound on Ψτ′′\Psi_\tau''Ψτ′′​ it bounds the estimator's expected bias (Corollary 2).

Formalization Note The expectation of Δ^SPτ\hat\Delta^\tau_{SP}Δ^SPτ​ is taken under the product law of the control, treatment and supply counts (not under the law of the total demand). The derivative is asserted with HasDerivAt, so differentiability is part of the conclusion. Assumptions 1–3 of the paper (random tie-breaking, unique optima of the fluid LP, sign-consistent β\betaβ) are not hypotheses: the proof on pp. 53–55 uses none of them, and the selection A=A−A=A^-A=A− is what makes the identity hold without uniqueness (p. 25). No integrality of capacities is assumed.

Preamble
import Mathlib
import Definitions.Def_MarketInterference_FiniteSample_Experiment
Formal statement
namespace MarketInterference.FiniteSample

open MeasureTheory ProbabilityTheory

theorem theorem_6 {nd ns : ℕ} {I E : Type} [Fintype E] [DecidableEq I]
    (N : MarketInterference.FluidBias.Network nd ns I E) (lam beta : Fin nd → ℝ) (pi : Fin ns → ℝ)
    (hlam : 0 ≤ lam) (hlamb : 0 ≤ lam + beta) (hpi : 0 ≤ pi)
    (ρ : ℝ) (hρ0 : 0 < ρ) (hρ1 : ρ < 1) (τ : ℝ) (hτ : 0 < τ) :
    HasDerivAt (PsiTau N lam beta pi τ)
      (∫ z, SPest N ρ τ z.1.1 z.1.2 z.2 ∂(experimentLaw lam beta pi ρ τ)) ρ := by sorry

end MarketInterference.FiniteSample
Source
Bright, Delarue and Lobel, Reducing Marketplace Interference Bias Via Shadow Prices, arXiv:2205.02274v4, p. 24, Theorem 6, (14)
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me