Online Supplement A, p. 33 — every feasible solution of (13) has ŷ_i ≥ 0
ProvedConstrNestedLogit.UpperBound.y_nonnegConsider the nested logit model with preference weights , arbitrary revenues , dissimilarity parameters and no within-nest no-purchase weight. Let be space requirements and capacities with for every product (the paper's standing assumption, p. 8), and let be finite sets of vectors such that every vector of is feasible for the linear programming relaxation of the knapsack problem (10) of nest , and for every some vector of is optimal for that relaxation at . If is a feasible solution of the linear program (13) built on these sets, then
This is the first step of the proof of Proposition 7: it settles the claim whenever the right side is nonpositive.
Formalization Note The fact that the zero vector belongs to is not assumed; it follows from the two properties of the family. The statement is for every feasible ; the paper applies it to an optimal one. The positivity is added (the paper's weights are exponentials of utilities, p. 10, but positivity is not restated), and so is , which is the paper's model. The paper's assumption (p. 8) is kept, and is added; together they make the zero vector feasible for every relaxation (without them, e.g. and , the conclusion fails).
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 (p. 33): if the vectors `X i` are feasible for
the linear programming relaxation of the knapsack problem (10) and include an optimal solution of
that relaxation for every `u ≥ 0`, then every feasible solution `(z, y)` of the linear program
(13) has `y_i ≥ 0` for every nest `i`. -/
theorem y_nonneg {ι : Type*} [Fintype ι] {n : ℕ} (I : Instance ι n)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ i j, 0 < I.v i j) (hγ : ∀ i, 0 < I.γ i)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (X : ι → Finset (Fin n → ℝ))
(hw : ∀ i j, 0 < w i j) (hwc : ∀ i j, w i j ≤ c i)
(hX : IsRelaxSolutionFamily I w c X) (z : ℝ) (y : ι → ℝ) (hzy : LP13Feasible I X z y) :
∀ i, 0 ≤ y i := by sorry
end ConstrNestedLogit.UpperBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.