Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma F.3 — Two identities at a relaxation optimum

Proved
GaoImpatientMNL.Pricing.lemma_F_3

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. Every maximizer q∗q^*q∗ satisfies both identities

RT(l)(q∗)=log⁡q1∗−(1+q1∗)+ql−1∗ql∗−log⁡(ql−1∗ql∗)+ql∗,R_T^{(l)}(q^*)=\log q_1^*-(1+q_1^*)+\frac{q_{l-1}^*}{q_l^*}-\log(q_{l-1}^*q_l^*)+q_l^*,RT(l)​(q∗)=logq1∗​−(1+q1∗​)+ql∗​ql−1∗​​−log(ql−1∗​ql∗​)+ql∗​, 1−ql∗ql−1∗ql∗exp⁡ ⁣(ql−1∗ql∗)=T.\frac{1-q_l^*}{q_{l-1}^*q_l^*}\exp\!\left(\frac{q_{l-1}^*}{q_l^*}\right)=T.ql−1∗​ql∗​1−ql∗​​exp(ql∗​ql−1∗​​)=T.

The identities are conclusions from actual global optimality on the closed feasible region; no stationary-point equations are assumed.

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 lemma_F_3 (T : ℝ) (hT : 0 < T) (l : ℕ) (hl : 0 < l)
    (q : ℕ → ℝ) (hq : IsRelaxationMax T l q) :
    relaxation T l q =
      ((Real.log (q 1) - (1 + q 1) + q (l - 1) / q l -
        Real.log (q (l - 1) * q l) + q l : ℝ) : EReal) ∧
    (1 - q l) / (q (l - 1) * q l) * Real.exp (q (l - 1) / q l) = T := by sorry

end GaoImpatientMNL.Pricing
Source
Gao et al., DOI 10.1287/opre.2021.2127, Lemma F.3, PDF p.48, printed p.ec11, held source.pdf.
Read-back

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

Data. T>0T>0T>0, l>0l>0l>0, and qqq real with q0=1q_0=1q0​=1, 0≤qk+1≤qk0\le q_{k+1}\le q_k0≤qk+1​≤qk​ for k<lk<lk<l, and qqq a global maximizer over all such sequences of the objective FFF. Here 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.​

Conclusion. Both of the following hold:

F(q)=log⁡q1−(1+q1)+ql−1ql−log⁡(ql−1ql)+qlF(q)=\log q_1-(1+q_1)+\frac{q_{l-1}}{q_l}-\log(q_{l-1}q_l)+q_lF(q)=logq1​−(1+q1​)+ql​ql−1​​−log(ql−1​ql​)+ql​

(a finite real number), and

1−qlql−1 ql  e ql−1/ql=T.\frac{1-q_l}{q_{l-1}\,q_l}\;e^{\,q_{l-1}/q_l}=T.ql−1​ql​1−ql​​eql−1​/ql​=T.

Degenerate cases.

  • For l=1l=1l=1 (so ql−1=q0=1q_{l-1}=q_0=1ql−1​=q0​=1), the claims read F(q)=1/q1−1F(q)=1/q_1-1F(q)=1/q1​−1 and 1−q1q1e1/q1=T\frac{1-q_1}{q_1}e^{1/q_1}=Tq1​1−q1​​e1/q1​=T.
  • If qlq_lql​ were 000, then F(q)=−∞F(q)=-\inftyF(q)=−∞ while the right-hand side of the first claim is a real number. The divisions by qlq_lql​ would also give 000 and log⁡0=0\log0=0log0=0 by convention.
  • No existence of a maximizer is assumed; if none exists, the statement is vacuous.
  • 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