Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — average utility minus excess requests ≥ OPT^{n,m}/(2 + e/(e − 1)) − nm/√T − n(δ + γ)

Proved
ConsumerUtilityApprox.UnitDemand.lemma_12

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

consumer-utilitymechanism-designonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1

Work in normalized units: an instance with n,m≥1n,m\ge1n,m≥1 and ∑i,jE[Vij]=1\sum_{i,j}\mathbb E[V_{ij}]=1∑i,j​E[Vij​]=1. Fix δ,γ∈(0,1]\delta,\gamma\in(0,1]δ,γ∈(0,1] and T≥1T\ge1T≥1 rounds, step size η=1/(nT)\eta=1/(n\sqrt T)η=1/(nT​), initial demand weights λ1=0\lambda^1=0λ1=0. In round ttt, buyer iii's mechanism MitM^t_iMit​ is Mhet1,mM^{1,m}_{\mathrm{het}}Mhet1,m​ for λt\lambda^tλt: with probability e/(3e−2)e/(3e-2)e/(3e−2) independent posted prices drawn from two-point laws implementing OPT1,1(Vij;qjt,i)\mathrm{OPT}^{1,1}(V_{ij};q^{t,i}_j)OPT1,1(Vij​;qjt,i​), where the caps qt,iq^{t,i}qt,i are feasible for the cap program (5.4) and within δ\deltaδ of its optimum RλtR_{\lambda^t}Rλt​; otherwise free lotteries ℓj(b)\ell_j(b)ℓj​(b) with b>0b>0b>0 and 2b−2γ≤U(Mbfree)≤2b2b-2\gamma\le U(M^{\mathrm{free}}_b)\le2b2b−2γ≤U(Mbfree​)≤2b. With rjt=∑iqjalloc(Mit)r^t_j=\sum_iq^{\mathrm{alloc}}_j(M^t_i)rjt​=∑i​qjalloc​(Mit​) and λjt+1=min⁡{1,max⁡{0,λjt+η(rjt−1)}}\lambda^{t+1}_j=\min\{1,\max\{0,\lambda^t_j+\eta(r^t_j-1)\}\}λjt+1​=min{1,max{0,λjt​+η(rjt​−1)}}, let Uˉ=1T∑t∑iU(Mit)\bar U=\frac1T\sum_t\sum_iU(M^t_i)Uˉ=T1​∑t​∑i​U(Mit​) and rˉj=1T∑trjt\bar r_j=\frac1T\sum_tr^t_jrˉj​=T1​∑t​rjt​. Then

Uˉ−∑j(rˉj−1)+ ≥ OPTn,m2+e/(e−1)−nmT−n(δ+γ).\bar U-\sum_j(\bar r_j-1)^+\ \ge\ \frac{\mathrm{OPT}^{n,m}}{2+e/(e-1)}-\frac{nm}{\sqrt T}-n(\delta+\gamma).Uˉ−j∑​(rˉj​−1)+ ≥ 2+e/(e−1)OPTn,m​−T​nm​−n(δ+γ).

With (C.5) this gives Lemma 6.

Differences from the source:

  • encoding: values in R_+, laws F_j, items 1..m → ℝ≥0, ProbabilityMeasure ℝ≥0, Fin m; product law vecLaw; reason: Lean conventions for the same objects
  • encoding: rounds t = 1, …, T with λ^1 = 0 → rounds t = 0, …, T − 1 with lam 0 = 0; reason: index shift
  • reading: δ and γ are the additive errors in cap optimization and free-lottery computation for each buyer at each round → hypotheses: the caps are feasible for (5.4) with objective ≥ R_λ − δ (Lemma 11's guarantee), the prices implement OPT^{1,1} at those caps, and the lottery parameter b > 0 has 2b − 2γ ≤ U(M^free_b) ≤ 2b (Appendix C.3's guarantee); reason: these are exactly the guarantees the proof of Lemma 12 uses (p. 46), and the greedy caps and the bisection output satisfy them
Preamble
import Mathlib
import Definitions.Def_MultiItemRev_BundlingOpt_Model
import Definitions.Def_ConsumerUtilityApprox_UnitDemand_Model
import Definitions.Def_ConsumerUtilityApprox_UnitDemand_Mechanisms
open MeasureTheory ProbabilityTheory
open scoped NNReal ENNReal
open MultiItemRev.BundlingOpt
Formal statement
namespace ConsumerUtilityApprox.UnitDemand

theorem lemma_12 {n m : ℕ} (hn : 1 ≤ n) (hm : 1 ≤ m) (I : Instance n m)
    (hnorm : ∑ i, ∑ j, mean (I.F i j) = 1)
    (δ γ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ ≤ 1) (hγ0 : 0 < γ) (hγ1 : γ ≤ 1)
    (T : ℕ) (hT : 1 ≤ T)
    (lam : ℕ → Fin m → ℝ) (caps : ℕ → Fin n → Fin m → ℝ)
    (pr : ℕ → Fin n → Fin m → TwoPointPrice) (b : ℕ → Fin n → ℝ)
    (hcaps : ∀ t < T, ∀ i, IsFeasibleCaps (caps t i) ∧
      capOpt (I.F i) (lam t) - δ ≤ capObjective (I.F i) (lam t) (caps t i))
    (hpr : ∀ t < T, ∀ i j, IsImplementing (I.F i j) (caps t i j) (pr t i j))
    (hb : ∀ t < T, ∀ i, 0 < b t i ∧
      2 * b t i - 2 * γ
        ≤ utility (I.buyerLaw i) (freeLotteryMech (lotteryProb (lam t) (b t i))).reduced ∧
      utility (I.buyerLaw i) (freeLotteryMech (lotteryProb (lam t) (b t i))).reduced
        ≤ 2 * b t i)
    (hlam0 : ∀ j, lam 0 j = 0)
    (hlam : ∀ t < T, ∀ j, lam (t + 1) j =
      min 1 (max 0 (lam t j + 1 / ((n : ℝ) * Real.sqrt T) *
        (∑ i, qAlloc (I.buyerLaw i)
          (hetMech (pr t i) (lotteryProb (lam t) (b t i))).reduced j - 1)))) :
    OPT I / (2 + Real.exp 1 / (Real.exp 1 - 1)) - (n : ℝ) * m / Real.sqrt T - n * (δ + γ)
      ≤ (1 / (T : ℝ)) * ∑ t ∈ Finset.range T, ∑ i,
          utility (I.buyerLaw i) (hetMech (pr t i) (lotteryProb (lam t) (b t i))).reduced
        - ∑ j, max ((1 / (T : ℝ)) * ∑ t ∈ Finset.range T, ∑ i,
            qAlloc (I.buyerLaw i) (hetMech (pr t i) (lotteryProb (lam t) (b t i))).reduced j
              - 1) 0 := by sorry

end ConsumerUtilityApprox.UnitDemand
Source
Goldner, Lundy, Tsilivis, A Constant-Factor Approximation to Multidimensional Consumer Utility, arXiv:2610.10516 (version of November 3, 2026, sha256 94e0dd44…), p. 45, Lemma 12 (proof pp. 46–48)
Human review
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 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