Online Supplement A, pp. 33–34 — the chain of inequalities for a nonzero relaxation optimum
ProvedConstrNestedLogit.UpperBound.key_inequalityConsider the nested logit model with preference weights , arbitrary revenues and no within-nest no-purchase weight, and fix a nest with . Let be a nonempty assortment satisfying the space constraint , let be a real number with , and set
If is an optimal solution of the linear programming relaxation of the knapsack problem (10) of nest at , then, writing and ,
This is the first and last link of the chain of inequalities in the proof of Proposition 7; together with a constraint of the linear program (13), it gives the proof's claim in the case .
Formalization Note The left side is the published NestedLogitVariants.General.F I i x z, which equals the displayed term because . The positivity is an added hypothesis.
import Mathlib import Definitions.Def_NestedLogitVariants_General_Model import Definitions.Def_NestedLogitVariants_General_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_Relaxation import Definitions.Def_ConstrNestedLogit_UpperBound_LP13 open NestedLogitVariants.General
namespace ConstrNestedLogit.UpperBound
/-- Online Supplement A, proof of Proposition 7 (pp. 33–34), the chain of inequalities: let
`γ_i ∈ (0, 1]`, let `S` be a nonempty assortment satisfying the space constraint of nest `i` with
`R_i(S) > z`, put `û = γ_i z + (1 − γ_i) R_i(S)`, and let `x ≠ 0` be an optimal solution of the
linear programming relaxation of (10) at `û`. Then
`V_i(x)^{γ_i} (R_i(x) − z) ≥ V_i(S)^{γ_i} (R_i(S) − z)`, where the left side is `F I i x z`. -/
theorem key_inequality {ι : Type*} {n : ℕ} (I : Instance ι n)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ i j, 0 < I.v i j)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (i : ι) (hγ : 0 < I.γ i ∧ I.γ i ≤ 1)
(S : Finset (Fin n)) (hS : SpaceFeasible w c i S) (hSne : S.Nonempty)
(z : ℝ) (hRz : z < R I i S) (x : Fin n → ℝ)
(hx : RelaxOptimal I w c i (I.γ i * z + (1 - I.γ i) * R I i S) x) (hx0 : x ≠ 0) :
nestWeight I i S * (R I i S - z) ≤ F I i x z := by sorry
end ConstrNestedLogit.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.