Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition F.5 — Closed-form relaxation bound

Proved
GaoImpatientMNL.Pricing.proposition_F_5

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

multinomial-logitoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-v1pricing

Let T>0T>0T>0 and l≥1l\ge1l≥1. On 1=q0≥q1≥⋯≥ql≥01=q_0\ge q_1\ge\cdots\ge q_l\ge01=q0​≥q1​≥⋯≥ql​≥0, let RT(l)R_T^{(l)}RT(l)​ be the extended-real objective (20), with value −∞-\infty−∞ at ql=0q_l=0ql​=0, zero entropy term at ql=1q_l=1ql​=1, and zero contributions from equal positive neighbors. Write z^T(l)\widehat z_T^{(l)}zT(l)​ for its supremum, with z^T(0)=0\widehat z_T^{(0)}=0zT(0)​=0. Define GT(x)=(1+4T/ex+1)/2G_T(x)=(\sqrt{1+4T/e^x}+1)/2GT​(x)=(1+4T/ex​+1)/2 for real xxx. Then

z^T(l)≤2log⁡GT(1)+1GT(1+GT(1)/l)−1+GT(1)l.\widehat z_T^{(l)}\le2\log G_T(1)+\frac1{G_T(1+G_T(1)/l)}-1+\frac{G_T(1)}l.zT(l)​≤2logGT​(1)+GT​(1+GT​(1)/l)1​−1+lGT​(1)​.

The bound retains both finite-stage correction terms and applies to every positive integer lll.

Differences from the source:

  • encoding: The finite vector q_0,...,q_l with q_0=1 → A sequence of real numbers with constraints only through l and later entries ignored; reason: Every finite vector has an extension and all objectives depend only on the displayed finite coordinates.
  • reading: The formulas (19)-(22) on the closed monotone region → EReal values, zero for zero drops, minus infinity for a positive drop with zero endpoint or zero stage mass; R is minus infinity at q_l=0 and has zero entropy term at q_l=1; reason: The source invokes the limit x log x=0 in F.1 and explicitly assigns R^(1)(0)=-infinity in F.2; no boundary point is removed.
Preamble
import Mathlib
import Definitions.Def_GaoImpatientMNL_Pricing_Relaxation
Formal statement
/- BEGIN IMPORTED LEAN FOR BLIND AUDIT
noncomputable section
namespace MultiStoreAssort.Pricing
variable {n : ℕ}
noncomputable def rev14 (a b : Fin n → ℝ) (S : Finset (Fin n)) (p : Fin n → ℝ) : ℝ :=
  (∑ k ∈ S, p k * Real.exp (a k - b k * p k)) / (1 + ∑ k ∈ S, Real.exp (a k - b k * p k))
end MultiStoreAssort.Pricing
end

open scoped BigOperators
noncomputable section
namespace GaoImpatientMNL.Pricing
def Parameters {n m : ℕ} (β : ℝ) (lam : Fin m → ℝ) : Prop :=
  0 < n ∧ 0 < m ∧ 0 < β ∧
    (∀ k, k.val = 0 → lam k = 1) ∧ (∀ k, 0 < lam k) ∧ Antitone lam
def Feasible {n m : ℕ} (S : Fin m → Finset (Fin n)) : Prop :=
  ∀ k h, k ≠ h → Disjoint (S k) (S h)
def attraction {n : ℕ} (α : Fin n → ℝ) (β : ℝ) (p : Fin n → ℝ)
    (s : Finset (Fin n)) : ℝ := ∑ i ∈ s, Real.exp (α i - β * p i)
def prefixWeight {n m : ℕ} (v : Fin n → ℝ) (S : Fin m → Finset (Fin n)) (k : Fin m) : ℝ :=
  ∑ h ∈ Finset.univ.filter (fun h => h < k), ∑ i ∈ S h, v i
def choiceFormula {n m : ℕ} (v : Fin n → ℝ) (lam : Fin m → ℝ)
    (S : Fin m → Finset (Fin n)) (k : Fin m) (i : Fin n) : ℝ :=
  lam k * v i / ((1 + prefixWeight v S k) * (1 + prefixWeight v S k + ∑ j ∈ S k, v j))
def revenue {n m : ℕ} (α : Fin n → ℝ) (β : ℝ) (lam : Fin m → ℝ)
    (S : Fin m → Finset (Fin n)) (p : Fin n → ℝ) : ℝ :=
  ∑ k, (lam k * ∑ i ∈ S k, p i * Real.exp (α i - β * p i)) /
    ((1 + prefixWeight (fun i => Real.exp (α i - β * p i)) S k) *
      (1 + prefixWeight (fun i => Real.exp (α i - β * p i)) S k + attraction α β p (S k)))
def firstSequence (n m : ℕ) : Fin m → Finset (Fin n) :=
  fun k => if k.val = 0 then Finset.univ else ∅
def firstRevenue {n : ℕ} (α : Fin n → ℝ) (β : ℝ) (p : Fin n → ℝ) : ℝ :=
  MultiStoreAssort.Pricing.rev14 α (fun _ => β) Finset.univ p
def jointRevenues {n m : ℕ} (α : Fin n → ℝ) (β : ℝ) (lam : Fin m → ℝ) : Set ℝ :=
  {r | ∃ S : Fin m → Finset (Fin n), Feasible S ∧ ∃ p : Fin n → ℝ, r = revenue α β lam S p}
def jointValue {n m : ℕ} (α : Fin n → ℝ) (β : ℝ) (lam : Fin m → ℝ) : ℝ :=
  sSup (jointRevenues α β lam)
def firstValue {n : ℕ} (α : Fin n → ℝ) (β : ℝ) : ℝ :=
  sSup (Set.range (firstRevenue α β))
def IsPricingMax {n m : ℕ} (α : Fin n → ℝ) (β : ℝ) (lam : Fin m → ℝ)
    (S : Fin m → Finset (Fin n)) (p : Fin n → ℝ) : Prop :=
  ∀ p', revenue α β lam S p' ≤ revenue α β lam S p
def MaximaExist {n m : ℕ} (α : Fin n → ℝ) (β : ℝ) (lam : Fin m → ℝ) : Prop :=
  (jointRevenues α β lam).Nonempty ∧ BddAbove (jointRevenues α β lam) ∧
  (Set.range (firstRevenue α β)).Nonempty ∧ BddAbove (Set.range (firstRevenue α β)) ∧
  (∃ S p, Feasible S ∧ revenue α β lam S p = jointValue α β lam) ∧
  (∃ p, firstRevenue α β p = firstValue α β) ∧ 0 < jointValue α β lam
end GaoImpatientMNL.Pricing

open scoped BigOperators
noncomputable section
namespace GaoImpatientMNL.Pricing
def totalAttraction {n : ℕ} (α : Fin n → ℝ) : ℝ := ∑ i, Real.exp (α i)
def stageAttraction {n m : ℕ} (α : Fin n → ℝ) (S : Fin m → Finset (Fin n))
    (k : Fin m) : ℝ := ∑ i ∈ S k, Real.exp (α i)
def QFeasible (l : ℕ) (q : ℕ → ℝ) : Prop :=
  q 0 = 1 ∧ ∀ k < l, 0 ≤ q (k + 1) ∧ q (k + 1) ≤ q k
def stageQ {n m : ℕ} (α : Fin n → ℝ) (β : ℝ)
    (S : Fin m → Finset (Fin n)) (ρ : Fin m → ℝ) (t : ℕ) : ℝ :=
  1 / (1 + ∑ k ∈ Finset.univ.filter (fun k => k.val < t),
    Real.exp (-β * ρ k) * stageAttraction α S k)
def recoveredPrice (β A a b : ℝ) : Option ℝ :=
  if 0 < β ∧ 0 < A ∧ 0 < b ∧ b < a then
    some ((Real.log A - Real.log (1 / b - 1 / a)) / β) else none
def relaxedStage (A a b : ℝ) : EReal :=
  if a = b then 0 else if A ≤ 0 ∨ b ≤ 0 ∨ a ≤ b then ⊥ else
    ((a - b) * (Real.log A - Real.log (1 / b - 1 / a)) : ℝ)
def infinitePatienceRevenue {n m : ℕ} (α : Fin n → ℝ)
    (S : Fin m → Finset (Fin n)) (q : ℕ → ℝ) : EReal :=
  ∑ k : Fin m, relaxedStage (stageAttraction α S k) (q k.val) (q (k.val + 1))
def patienceQRevenue {n m : ℕ} (α : Fin n → ℝ) (β : ℝ)
    (lam : Fin m → ℝ) (S : Fin m → Finset (Fin n)) (q : ℕ → ℝ) : EReal :=
  if 0 < β then ∑ k : Fin m,
    (↑(lam k / β) : EReal) * relaxedStage (stageAttraction α S k) (q k.val) (q (k.val + 1))
  else ⊥
def relaxationReal (T : ℝ) (l : ℕ) (q : ℕ → ℝ) : ℝ :=
  (∑ k ∈ Finset.range l, (q k - q (k + 1)) * Real.log (q k * q (k + 1))) +
    if q l = 1 then 0 else (1 - q l) * Real.log (T / (1 - q l))
def relaxation (T : ℝ) (l : ℕ) (q : ℕ → ℝ) : EReal :=
  if q l = 0 then ⊥ else (relaxationReal T l q : EReal)
def relaxationValue (T : ℝ) (l : ℕ) : EReal :=
  if l = 0 then 0 else sSup {r | ∃ q, QFeasible l q ∧ r = relaxation T l q}
def IsRelaxationMax (T : ℝ) (l : ℕ) (q : ℕ → ℝ) : Prop :=
  QFeasible l q ∧ ∀ r, QFeasible l r → relaxation T l r ≤ relaxation T l q
def G (T x : ℝ) : ℝ := (Real.sqrt (1 + 4 * T / Real.exp x) + 1) / 2
end GaoImpatientMNL.Pricing
END IMPORTED LEAN FOR BLIND AUDIT -/

namespace GaoImpatientMNL.Pricing

theorem proposition_F_5 (T : ℝ) (hT : 0 < T) (l : ℕ) (hl : 0 < l) :
    relaxationValue T l ≤
      ((2 * Real.log (G T 1) + 1 / G T (1 + G T 1 / (l : ℝ)) - 1 +
        G T 1 / (l : ℝ) : ℝ) : EReal) := by sorry

end GaoImpatientMNL.Pricing
Source
Gao et al., DOI 10.1287/opre.2021.2127, Proposition F.5, PDF p.49, printed p.ec12, held source.pdf.
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Data. T>0T>0T>0 and l>0l>0l>0. Call q=(q0,q1,… )q=(q_0,q_1,\dots)q=(q0​,q1​,…) feasible when q0=1q_0=1q0​=1 and 0≤qk+1≤qk0\le q_{k+1}\le q_k0≤qk+1​≤qk​ for k<lk<lk<l. Define F(q)=−∞F(q)=-\inftyF(q)=−∞ if ql=0q_l=0ql​=0, and otherwise

F(q)=∑k=0l−1(qk−qk+1)log⁡(qkqk+1)+{0ql=1,(1−ql)log⁡T1−qlql≠1,F(q)=\sum_{k=0}^{l-1}(q_k-q_{k+1})\log(q_kq_{k+1})+\begin{cases}0&q_l=1,\\(1-q_l)\log\frac{T}{1-q_l}&q_l\ne1,\end{cases}F(q)=k=0∑l−1​(qk​−qk+1​)log(qk​qk+1​)+{0(1−ql​)log1−ql​T​​ql​=1,ql​=1,​

with log⁡0=0\log0=0log0=0 and log⁡x=log⁡∣x∣\log x=\log|x|logx=log∣x∣ for x<0x<0x<0. Let V=sup⁡{F(q):q feasible}V=\sup\{F(q): q \text{ feasible}\}V=sup{F(q):q feasible} in the extended reals. Let

G(x)=1+4T/ex+12G(x)=\frac{\sqrt{1+4T/e^x}+1}{2}G(x)=21+4T/ex​+1​

and g=G(1)g=G(1)g=G(1). Since T>0T>0T>0, every G(x)>1G(x)>1G(x)>1.

Conclusion.

V≤2log⁡g+1G(1+g/l)−1+gl.V\le 2\log g+\frac{1}{G\bigl(1+g/l\bigr)}-1+\frac{g}{l}.V≤2logg+G(1+g/l)1​−1+lg​.

In particular, VVV is not +∞+\infty+∞.

Degenerate cases. With T>0T>0T>0 and l≥1l\ge1l≥1, all logarithms, square roots and divisions on the right are of positive quantities, so no conventions arise. The cases T≤0T\le0T≤0 and l=0l=0l=0 are excluded.

Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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