Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 (corrected: C1 on [A I]) — a feasible direction d from μ_* with dᵀAʲ = 0 on E₀ ∪ E₁ and dᵀx = 0 is zero

Proved
RLPBidPrice.Unbiased.lemma3_direction_eq_zero

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

linear-programminglp-dualityp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Let AAA be a 0/1 incidence matrix with nonzero columns, r≥0r \ge 0r≥0, Y≥0Y \ge 0Y≥0, and x≥0x \ge 0x≥0 satisfying Condition C1′ (whenever xxx lies in the span of a set of columns of [A I][A\ I][A I], that set spans Rm\mathbb{R}^mRm). Let μ∗\mu_*μ∗​ be an optimal dual price vector, i.e. a minimizer of L(x,⋅)L(x, \cdot)L(x,⋅) over μ≥0\mu \ge 0μ≥0. Let d∈Rmd \in \mathbb{R}^md∈Rm be a feasible direction from μ∗\mu_*μ∗​: for some ϵ>0\epsilon > 0ϵ>0,

μ∗+hd≥0,h∈[0,ϵ].(15)\mu_* + h d \ge 0, \qquad h \in [0, \epsilon]. \tag{15}μ∗​+hd≥0,h∈[0,ϵ].(15)

Fix h∈(0,ϵ]h \in (0, \epsilon]h∈(0,ϵ] and define

E0={j:rj−μ∗⊤Aj>0},(16)E_0 = \{j : r^j - \mu_*^\top A^j > 0\}, \tag{16}E0​={j:rj−μ∗⊤​Aj>0},(16) E1={j:rj−μ∗⊤Aj=0, rj−μ∗⊤Aj−hd⊤Aj>0}.(17)E_1 = \{j : r^j - \mu_*^\top A^j = 0,\ r^j - \mu_*^\top A^j - h d^\top A^j > 0\}. \tag{17}E1​={j:rj−μ∗⊤​Aj=0, rj−μ∗⊤​Aj−hd⊤Aj>0}.(17)

If d⊤Aj=0d^\top A^j = 0d⊤Aj=0 for all j∈E0∪E1j \in E_0 \cup E_1j∈E0​∪E1​ and d⊤x=0d^\top x = 0d⊤x=0, then d=0d = 0d=0.

In the paper this is the step showing that no nonzero feasible direction leaves L(x,⋅)L(x, \cdot)L(x,⋅) constant, which is how uniqueness of μ∗\mu_*μ∗​ is obtained.

Formalization Note. The context of Eqs. (15)–(17) — the optimal μ∗\mu_*μ∗​, the feasible direction ddd with its ϵ\epsilonϵ, and the step hhh used in E1E_1E1​ — is carried as hypotheses. d⊤Ajd^\top A^jd⊤Aj is written d ⬝ᵥ (fun i => A i j).

Correction. The printed lemma assumes Condition 1 (only the columns of AAA); it is stated here under C1′ (the columns of [A I][A\ I][A I]). With the printed condition it is false: for AAA with rows (0,1,1),(1,1,0),(1,0,1)(0,1,1), (1,1,0), (1,0,1)(0,1,1),(1,1,0),(1,0,1), r=(100,1,1)r = (100,1,1)r=(100,1,1), x=(1,1,1)x = (1,1,1)x=(1,1,1) and Y=(2,1/2,1/2)Y = (2, 1/2, 1/2)Y=(2,1/2,1/2) (for instance), μ∗=(0,50,50)\mu_* = (0, 50, 50)μ∗​=(0,50,50) is optimal and d=(0,1,−1)d = (0, 1, -1)d=(0,1,−1) gives E0=E1=∅E_0 = E_1 = \emptysetE0​=E1​=∅ and d⊤x=0d^\top x = 0d⊤x=0 with d≠0d \neq 0d=0, while Condition 1 holds at xxx.

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Unbiased_Model

open MeasureTheory Matrix
Formal statement
namespace RLPBidPrice.Unbiased

theorem lemma3_direction_eq_zero {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : Fin n → ℝ)
    (hA : IsIncidence A) (hr : 0 ≤ r) (x : Fin m → ℝ) (hx : 0 ≤ x)
    (hC1 : ConditionOnePrime A x) (y₀ : Fin n → ℝ) (hy₀ : 0 ≤ y₀)
    (μs : Fin m → ℝ) (hμs : IsDualOpt A r x y₀ μs)
    (d : Fin m → ℝ) (ε : ℝ) (hε : 0 < ε)
    (hfeas : ∀ h ∈ Set.Icc (0 : ℝ) ε, 0 ≤ μs + h • d)
    (h : ℝ) (hh : h ∈ Set.Ioc (0 : ℝ) ε)
    (E₀ E₁ : Set (Fin n))
    (hE₀ : E₀ = {j | r j - μs ⬝ᵥ (fun i => A i j) > 0})
    (hE₁ : E₁ = {j | r j - μs ⬝ᵥ (fun i => A i j) = 0 ∧
      r j - μs ⬝ᵥ (fun i => A i j) - h * d ⬝ᵥ (fun i => A i j) > 0})
    (hdA : ∀ j ∈ E₀ ∪ E₁, d ⬝ᵥ (fun i => A i j) = 0)
    (hdx : d ⬝ᵥ x = 0) :
    d = 0 := by sorry

end RLPBidPrice.Unbiased
Source
Talluri, van Ryzin, A Randomized Linear Programming Method for Computing Network Bid Prices, Transp. Sci. 33(2), 1999, p. 211, Lemma 3 with Eqs. (15)-(17)
Read-back

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

Let AAA be a real m×nm \times nm×n matrix whose entries are all 000 or 111 and whose every column AjA^jAj has a nonzero entry. Assume r∈Rnr \in \mathbb{R}^nr∈Rn with r≥0r \ge 0r≥0 and x∈Rmx \in \mathbb{R}^mx∈Rm with x≥0x \ge 0x≥0. Assume xxx satisfies Condition C1′:

for all finite S⊆{1,…,n}S \subseteq \{1,\dots,n\}S⊆{1,…,n} and T⊆{1,…,m}T \subseteq \{1,\dots,m\}T⊆{1,…,m}, if xxx is a real linear combination of {Aj:j∈S}∪{ei:i∈T}\{A^j : j\in S\} \cup \{e_i : i\in T\}{Aj:j∈S}∪{ei​:i∈T}, then those vectors span Rm\mathbb{R}^mRm.

Let y0∈Rny_0 \in \mathbb{R}^ny0​∈Rn with y0≥0y_0 \ge 0y0​≥0. Let μ∗∈Rm\mu^* \in \mathbb{R}^mμ∗∈Rm be dual-optimal: μ∗≥0\mu^* \ge 0μ∗≥0 and L(μ∗)≤L(μ′)L(\mu^*) \le L(\mu')L(μ∗)≤L(μ′) for all μ′≥0\mu' \ge 0μ′≥0, where

L(μ)=∑j(y0)jmax⁡(0,rj−μ⋅Aj)+μ⋅x.L(\mu) = \sum_j (y_0)_j \max(0, r_j - \mu\cdot A^j) + \mu \cdot x.L(μ)=j∑​(y0​)j​max(0,rj​−μ⋅Aj)+μ⋅x.

The remaining data and hypotheses are:

  • a vector d∈Rmd \in \mathbb{R}^md∈Rm and a real ε>0\varepsilon > 0ε>0 with μ∗+h′d≥0\mu^* + h' d \ge 0μ∗+h′d≥0 for every h′∈[0,ε]h' \in [0, \varepsilon]h′∈[0,ε];
  • a real h∈(0,ε]h \in (0, \varepsilon]h∈(0,ε];
  • the sets
E0={j:rj−μ∗⋅Aj>0},E1={j:rj−μ∗⋅Aj=0 and rj−μ∗⋅Aj−h d⋅Aj>0}.E_0 = \{j : r_j - \mu^* \cdot A^j > 0\}, \qquad E_1 = \{j : r_j - \mu^*\cdot A^j = 0 \text{ and } r_j - \mu^*\cdot A^j - h\, d\cdot A^j > 0\}.E0​={j:rj​−μ∗⋅Aj>0},E1​={j:rj​−μ∗⋅Aj=0 and rj​−μ∗⋅Aj−hd⋅Aj>0}.

Since h>0h > 0h>0, E1E_1E1​ is the set of jjj with rj=μ∗⋅Ajr_j = \mu^*\cdot A^jrj​=μ∗⋅Aj and d⋅Aj<0d \cdot A^j < 0d⋅Aj<0;

  • d⋅Aj=0d \cdot A^j = 0d⋅Aj=0 for every j∈E0∪E1j \in E_0 \cup E_1j∈E0​∪E1​;
  • d⋅x=0d \cdot x = 0d⋅x=0.

Conclusion: d=0d = 0d=0.

Degenerate cases.

  • E1E_1E1​ must be empty. Its members satisfy d⋅Aj<0d\cdot A^j < 0d⋅Aj<0, but the hypothesis requires d⋅Aj=0d \cdot A^j = 0d⋅Aj=0 on E1E_1E1​. So the hypotheses can hold together only when no jjj has rj=μ∗⋅Ajr_j = \mu^* \cdot A^jrj​=μ∗⋅Aj and d⋅Aj<0d \cdot A^j < 0d⋅Aj<0.
  • C1′ restricts xxx. Take S=∅S = \emptysetS=∅ and T={i:xi≠0}T = \{i : x_i \neq 0\}T={i:xi​=0}. Then C1′ forces every xi≠0x_i \neq 0xi​=0, so every xi>0x_i > 0xi​>0. In particular, for m≥1m \ge 1m≥1 and x=0x = 0x=0 the hypotheses cannot be satisfied and the statement is vacuous.
  • If m=0m = 0m=0, d=0d = 0d=0 holds trivially.
  • y0y_0y0​ enters only through the dual optimality of μ∗\mu^*μ∗.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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