Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 (Market-Maker Pareto Improvement) (corrected: β>0\beta>0β>0, Cov(ℓ,c)≤0\mathrm{Cov}(\ell,c)\le0Cov(ℓ,c)≤0, E[ℓ]>0\mathbf E[\ell]>0E[ℓ]>0)

Proved
MarketMakerAds.theorem_3

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

auctionsmechanism-designonline-advertisingp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1risk-aversion

A seller sells III identical units. On a probability space (Ω,P)(\Omega,\mathbb P)(Ω,P) the market outcome is a random list of nonnegative unit values: a random number of units demanded, with values that may be correlated, and a buyer of demand kkk counted as kkk units. Without the contract, the III highest units win the (I+1)(I+1)(I+1)-th price auction and pay the clearing price ccc, the (I+1)(I+1)(I+1)-th highest unit value. Every buyer evaluates the auction with the law ggg of ccc. The seller offers the Market-Maker contract at

p=pM∗={μA+βσA2,1αlog⁡E[eαc],p=p^*_M=\begin{cases}\mu_A+\beta\sigma_A^2,\\ \tfrac1\alpha\log\mathbf E[e^{\alpha c}],\end{cases}p=pM∗​={μA​+βσA2​,α1​logE[eαc],​

computed from ggg, with β≥0\beta\ge0β≥0 (mean-variance), resp. α>0\alpha>0α>0 (CARA). A unit of value vvv buys the contract if p≤vp\le vp≤v and UA(v)≤Ubuy(v,p)U_A(v)\le U_{\mathrm{buy}}(v,p)UA​(v)≤Ubuy​(v,p) (ties to the contract). The other units go to the (I−ℓ+1)(I-\ell+1)(I−ℓ+1)-th price auction for the remaining units, where ℓ\ellℓ is the number of contract units. Let pmax⁡p_{\max}pmax​ be the top of the support of ccc with no atom there: c≤pmax⁡c\le p_{\max}c≤pmax​ almost surely, P(c>v)>0\mathbb P(c>v)>0P(c>v)>0 for every v<pmax⁡v<p_{\max}v<pmax​, and P(c=pmax⁡)=0\mathbb P(c=p_{\max})=0P(c=pmax​)=0. Then:

  1. Each buyer's utility remains the same. A unit that buys the contract gets Ubuy(v,p)=UA(v)U_{\mathrm{buy}}(v,p)=U_A(v)Ubuy​(v,p)=UA​(v). The buyers are exactly the units with v≥max⁡(pmax⁡,p)v\ge\max(p_{\max},p)v≥max(pmax​,p). In every outcome the sum of the buyers' utilities with the contract equals the sum without it.
  2. Efficiency remains optimal. Almost surely, ℓ≤I\ell\le Iℓ≤I, the auction clearing price with the contract equals ccc, and the allocated value with the contract equals the sum Eff0\mathrm{Eff}_0Eff0​ of the III highest unit values. No choice of at most III units has a larger total value than Eff0\mathrm{Eff}_0Eff0​.
  3. Revenue strictly increases. If β>0\beta>0β>0 (resp. α>0\alpha>0α>0), E[ℓ]>0\mathbf E[\ell]>0E[ℓ]>0 and E[ℓ c]≤E[ℓ] E[c]\mathbf E[\ell\,c]\le\mathbf E[\ell]\,\mathbf E[c]E[ℓc]≤E[ℓ]E[c], then E[R0]<E[R1]\mathbf E[R_0]<\mathbf E[R_1]E[R0​]<E[R1​].
  4. Welfare strictly increases. Under the hypotheses of 3, if the buyers' utility sum without the contract is integrable, then E[W0]<E[W1]\mathbf E[W_0]<\mathbf E[W_1]E[W0​]<E[W1​], where welfare is the buyers' utilities plus the revenue.

Here R0=IcR_0=IcR0​=Ic and R1=ℓp+(I−ℓ)c1R_1=\ell p+(I-\ell)c_1R1​=ℓp+(I−ℓ)c1​, with c1c_1c1​ the clearing price of the second-stage auction, are computed from the two outcomes.

Offering the contract at pM∗p^*_MpM∗​ is thus a Pareto improvement: buyers keep their utility, the allocation stays efficient, and the seller gains the markup on every contract unit.

Differences from the source:

  • correction: β≥0\beta\ge0β≥0 → β>0\beta>0β>0 for the strict revenue and welfare clauses; reason: at β=0\beta=0β=0, pM∗=μAp^*_M=\mu_ApM∗​=μA​; with I=1I=1I=1, one buyer of value 222 and one of value U∼U[0,1]U\sim U[0,1]U∼U[0,1], ℓ=1\ell=1ℓ=1 and E[R1−R0]=E[1/2−U]=0\mathbf E[R_1-R_0]=\mathbf E[1/2-U]=0E[R1​−R0​]=E[1/2−U]=0.
  • correction: no hypothesis on the joint law of ℓ\ellℓ and ccc → E[ℓc]≤E[ℓ]E[c]\mathbf E[\ell c]\le\mathbf E[\ell]\mathbf E[c]E[ℓc]≤E[ℓ]E[c]; reason: the model allows correlated values and a random number of buyers; with I=1I=1I=1, β=1\beta=1β=1, and two equally likely scenarios (values {5,U}\{5,U\}{5,U}, U∼U[0.9,1]U\sim U[0.9,1]U∼U[0.9,1], or two i.i.d. U[0,0.1]U[0,0.1]U[0,0.1] values), ggg has a density, pmax⁡=1p_{\max}=1pmax​=1, pM∗≈0.702p^*_M\approx0.702pM∗​≈0.702 and E[R1−R0]=12(pM∗−0.95)≈−0.124<0\mathbf E[R_1-R_0]=\tfrac12(p^*_M-0.95)\approx-0.124<0E[R1​−R0​]=21​(pM∗​−0.95)≈−0.124<0. Independence of ℓ\ellℓ and ccc is a special case.
  • correction: no hypothesis on ℓ\ellℓ → E[ℓ]>0\mathbf E[\ell]>0E[ℓ]>0; reason: with I=1I=1I=1 and two buyers with i.i.d. U[0,1]U[0,1]U[0,1] values, pmax⁡=1p_{\max}=1pmax​=1 and ℓ=0\ell=0ℓ=0 almost surely, so revenue is unchanged.
  • generalization: the clearing price has a density ggg → only no atom at pmax⁡p_{\max}pmax​, the top of the support of ccc; reason: a density has no atoms; without this, more than III buyers can choose the contract (Remark 1).
  • reading: a buyer "opts for" the contract → p≤vp\le vp≤v and UA(v)≤Ubuy(v,p)U_A(v)\le U_{\mathrm{buy}}(v,p)UA​(v)≤Ubuy​(v,p), ties to the contract, every other buyer receives UA(v)U_A(v)UA​(v) even when negative; reason: p.10 (utility comparison), p.18 (indifferent buyers opt for the contract), eq. (2) (no purchase below pMp_MpM​), and Step 1 of p.11 (the clearing price is the (I+1)(I+1)(I+1)-th value of all buyers); p.14's remark that an agent with negative utility does not participate is not built in, and it would not change any buyer's utility, since contract buyers have Ubuy=UA≥0U_{\mathrm{buy}}=U_A\ge0Ubuy​=UA​≥0 there.
  • reading: the market → a random list of nonnegative unit values, ccc its (I+1)(I+1)(I+1)-th highest entry (000 if at most III units are demanded), R0=IcR_0=IcR0​=Ic; reason: Assumption 2 (p.11) puts everything on a per-unit basis; values are nonnegative because the paper's clearing prices live on [0,∞)[0,\infty)[0,∞) (pp.30–31).
  • reading: the market with the contract → contract units first, then the (I−ℓ+1)(I-\ell+1)(I−ℓ+1)-th price auction on the other units; efficiency = allocated value, "optimal" = no III units have a larger total, welfare = buyers' utilities plus revenue; reason: proof of Theorem 3 (pp.18–19) and §3.4 (p.13).
  • encoding: α≥0\alpha\ge0α≥0 → α>0\alpha>0α>0; reason: pM∗p^*_MpM∗​ is undefined at α=0\alpha=0α=0.
  • encoding: welfare compared in expectation → the buyers' utility sum without the contract is integrable; reason: the welfare comparison is between finite expectations.
  • encoding: I−ℓI-\ellI−ℓ → natural-number subtraction cast to R\mathbb RR; reason: the theorem proves ℓ≤I\ell\le Iℓ≤I almost surely, where it is the real difference.
Preamble
import Mathlib
import Definitions.Def_MarketMakerAds_Market

open MeasureTheory
Formal statement
namespace MarketMakerAds

/-- **Theorem 3 (Market-Maker Pareto Improvement), p.18 (corrected: β > 0, Cov(ℓ, c) ≤ 0,
E[ℓ] > 0).**
Cohen, Désir, Korula, Sivan, *Best of Both Worlds Ad Contracts*, SSRN 3088600, Theorem 3, p.18
(proof pp.18–19): "When offering the Market-Maker contract at price p*_M, both the seller's revenue
and the welfare strictly increase. Moreover, the efficiency remains optimal and each buyer's
utility remains the same."

The seller sells `I` units; the market outcome `ω` is a random list of nonnegative unit values
(`Market`), `c` is the `(I+1)`-th highest unit value with law `g`, and every buyer evaluates the
auction with `g`. The contract is offered at `p = p*_M = pStar m g`. Assume `β ≥ 0`, resp. `α > 0`,
and that `p_max` is the top of the support of `c` (`c ≤ p_max` a.s., `P(c > v) > 0` for all
`v < p_max`) with no atom at `p_max`. Then:
1. **each buyer's utility remains the same**: a unit that buys the contract gets
   `U_buy(v, p) = U_A(v)`, the buyers are exactly those with `v ≥ max(p_max, p)`, and the sum of the
   buyers' utilities is unchanged in every outcome;
2. **efficiency remains optimal**, almost surely: at most `I` units buy the contract, the auction
   clearing price is unchanged, the allocated value is unchanged, and no `I` units have a larger
   total value;
3. **revenue strictly increases**, `E[R₀] < E[R₁]`, if `β > 0` (resp. `α > 0`), `E[ℓ] > 0` and
   `E[ℓ c] ≤ E[ℓ] E[c]`, where `ℓ` is the number of contract units;
4. **welfare strictly increases**, `E[W₀] < E[W₁]`, under the hypotheses of 3 and integrability of
   the buyers' utility sum.

**Formalization Note** Corrections: with `β = 0`, `p*_M = µ_A` and revenue does not strictly
increase; with `E[ℓ] = 0` nobody buys; with `ℓ` positively correlated with `c` revenue can fall
(the model allows correlated values and a random number of buyers). Independence of `ℓ` and `c` is
a special case of `E[ℓ c] ≤ E[ℓ] E[c]`. The paper's density for `c` is replaced by "no atom at
`p_max`". -/
theorem theorem_3 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (M : Market Ω) (m : RiskModel) (hm : m.IsAdmissible) (pmax : ℝ)
    (h_le : ∀ᵐ ω ∂P, M.c ω ≤ pmax) (h_top : ∀ v < pmax, 0 < P {ω | v < M.c ω})
    (h_atom : P {ω | M.c ω = pmax} = 0) :
    -- 1. each buyer's utility remains the same
    ((∀ v : ℝ, buysMM m (M.priceLaw P) (M.mmPrice m P) v →
        Ubuy m v (M.mmPrice m P) = UA m (M.priceLaw P) v) ∧
      (∀ v : ℝ, buysMM m (M.priceLaw P) (M.mmPrice m P) v ↔ max pmax (M.mmPrice m P) ≤ v) ∧
      (∀ ω, M.util1 m P ω = M.util0 m P ω)) ∧
    -- 2. efficiency remains optimal
    (∀ᵐ ω ∂P, M.nMM m P ω ≤ M.I ∧ M.c1 m P ω = M.c ω ∧ M.eff1 m P ω = M.eff0 ω ∧
      ∀ s : List ℝ, s.Sublist (M.units ω) → s.length ≤ M.I → s.sum ≤ M.eff0 ω) ∧
    -- 3. revenue strictly increases
    (m.IsPositive → 0 < ∫ ω, (M.nMM m P ω : ℝ) ∂P →
      ∫ ω, (M.nMM m P ω : ℝ) * M.c ω ∂P ≤ (∫ ω, (M.nMM m P ω : ℝ) ∂P) * ∫ ω, M.c ω ∂P →
      ∫ ω, M.rev0 ω ∂P < ∫ ω, M.rev1 m P ω ∂P) ∧
    -- 4. welfare strictly increases
    (m.IsPositive → 0 < ∫ ω, (M.nMM m P ω : ℝ) ∂P →
      ∫ ω, (M.nMM m P ω : ℝ) * M.c ω ∂P ≤ (∫ ω, (M.nMM m P ω : ℝ) ∂P) * ∫ ω, M.c ω ∂P →
      Integrable (M.util0 m P) P →
      ∫ ω, M.welfare0 m P ω ∂P < ∫ ω, M.welfare1 m P ω ∂P) := by sorry

end MarketMakerAds
Source
Cohen, Désir, Korula, Sivan, Best of Both Worlds Ad Contracts, SSRN 3088600, Theorem 3, p.18 (proof pp.18–19)
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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