Eq. (32) — v^FR ≥ E[Σ_t Σ_j r_j x_j(t)] − Σ_j r_j (log T + 1) − Σ_j r_j λ_j
ProvedResolvingNRM.FRUpper.fr_revenue_accountingConsider the network revenue management model with Poisson rates , revenues , nonnegative consumption matrix , initial capacity , and an integer horizon . Run the Frequent Re-solving policy FR (Algorithm 2) with any optimal-solution selector: at the start of period it solves the DLP with right-hand side , obtains , and accepts class- arrivals in with probability subject to the capacity check. Then the expected revenue of FR satisfies
Since , this is equivalent to eq. (32):
The inequality separates the revenue FR would earn if its LP targets were met exactly from the losses caused by the capacity check, which are logarithmic in . It reduces Proposition 3 to a comparison of LP values.
Formalization Note. is the natural logarithm. is written as with frStateExp. The statement is the display at the foot of p. 34, which the paper rewrites as (32) by adding to both sides. , , , are the model's standing assumptions (p. 7).
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_FRUpper_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.FRUpper
/-- Eq. (32), App. C.2, pp. 34–35, in the form of the display at the foot of p. 34:
`v^FR ≥ E[∑_{t=0}^{T-1} ∑_j r_j x_j(t)] − ∑_j r_j (log T + 1) − ∑_j r_j λ_j`, where
`x(t) = sel (b(t))` and `b(t) = C(t) / (T − t)` along FR. -/
theorem fr_revenue_accounting {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r lam : Fin n → ℝ)
(hlam : ∀ j, 0 < lam j) (hr : 0 ≤ r) (hA : ∀ l j, 0 ≤ A l j)
(sel : (Fin m → ℝ) → (Fin n → ℝ)) (hsel : ResolvingNRM.IRT.IsDLPSelector A r lam sel)
(T : ℕ) (hT : 1 ≤ T) (C : Fin m → ℝ) (hC : 0 ≤ C) :
(∑ t ∈ Finset.range T,
frStateExp A r lam sel T t
(fun c => r ⬝ᵥ sel (fun l => c l / ((T : ℝ) - t))) C)
- (∑ j, r j) * (Real.log T + 1) - ∑ j, r j * lam j
≤ frValue A r lam sel T C := by sorry
end ResolvingNRM.FRUpper
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.