Proof of Lemma 9, p. 23 — for x ≥ 0, max_S V_i(S)^γ_i (R_i(S) − x) equals max_{ϵ≥0} (v_i0+ϵ)^γ_i [K_i(ϵ)/(v_i0+ϵ) − x]
ProvedNestedLogitVariants.PartialCompetitive.nest_max_eq_knapsack_maxConsider a nested logit instance in which every dissimilarity parameter satisfies , fix a nest and a number , and let be the knapsack value of display (9). Then
Equivalently, a number satisfies for every assortment if and only if for every .
This identity turns the per-nest constraint of the linear program (3), one inequality per assortment, into a constraint indexed by a single capacity parameter, and is the core of Lemma 9.
Formalization Note Both maxima are attained (the left one over a finite family; the right one at a capacity equal to the weight of a knapsack-optimal assortment), so the equality of the two maxima is stated as: bounds one family if and only if it bounds the other, without forming a real supremum. The hypothesis is the page's; for the right-hand family is unbounded.
import Mathlib import Definitions.Def_NestedLogitVariants_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
namespace NestedLogitVariants.PartialCompetitive
/-- Proof of Lemma 9, p. 23. For `x ≥ 0` and dissimilarity parameters at most one, the two maxima
`max_{S ⊂ N} V_i(S)^{γ_i} (R_i(S) − x)` and `max_{ε ≥ 0} (v_{i0} + ε)^{γ_i} [K_i(ε)/(v_{i0} + ε) − x]`
coincide; stated as: a number `y` bounds the first family iff it bounds the second. -/
theorem nest_max_eq_knapsack_max {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (i : ι) (x : ℝ) (hx : 0 ≤ x) (y : ℝ) :
(∀ S : Finset (Fin n), nestWeight I i S * (R I i S - x) ≤ y) ↔
(∀ ε : ℝ, 0 ≤ ε → (I.vnp i + ε) ^ I.γ i * (Kval I i ε / (I.vnp i + ε) - x) ≤ y) := by sorry
end NestedLogitVariants.PartialCompetitive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.