(29), p. 25 — nk Σ r⁽ℓ⁾Bℓ(1 − e^{−α⁽ℓ⁾}) = (1 − e^{−α⁽¹⁾}) Σ (r⁽ℓ⁾ − r⁽ℓ⁻¹⁾)Bℓnk
ProvedMultiPriceOnline.Hardness.eq_29competitive-ratiomulti-pricep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a price set with booking limits (Proposition 1), and recall . For all real numbers and all ,
The left side is the value (28) at , . The right side is times the expression (25) for OPT. This identity is the step of the proof of Theorem 3 that produces the factor .
Preamble
import Mathlib import Definitions.Def_MultiPriceOnline_Hardness_PriceSet
Formal statement
namespace MultiPriceOnline.Hardness
open Finset
theorem eq_29 {m : ℕ} {r α : ℕ → ℝ} (hr : MultiPriceOnline.Balance.IsPriceSet m r) (hα : MultiPriceOnline.Balance.IsBookingLimits m r α)
(B : ℕ → ℝ) (n k : ℕ) :
(n : ℝ) * k * ∑ l ∈ Icc 1 m, r l * B l * (1 - Real.exp (-α l)) =
(1 - Real.exp (-α 1)) * ∑ l ∈ Icc 1 m, (price r l - price r (l - 1)) * B l * n * k := by sorry
end MultiPriceOnline.Hardness
Source
Ma, Simchi-Levi, Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-dependent Competitive Ratios, arXiv:1905.04770v1, p. 25, eq. (29) in the proof of Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.