Proof of Theorem 4, p. 15 — adding a missing higher-revenue product k < j to S_i* keeps the assortment optimal
ProvedNestedLogitVariants.Competitive.insert_higher_revenue_optimalAssume and for every nest , and . Let be an optimal solution to the assortment problem (2), and suppose that in some nest the assortment contains product but not product , where (so ). Let . Then
is also an optimal solution to problem (2).
This exchange step is the core of the proof of Theorem 4: repeating it fills every gap in every nest until each nest offers a set of the form .
Formalization Note The standing assumptions of §3 (p. 13), and for every nest, are hypotheses, together with those of §1 and the disclosed pins of the model definition (, , , revenues ordered within each nest). The positivity is the section's own "without loss of generality" assumption (p. 14), stated as a hypothesis here because the argument uses it. Products are indexed ; compares indices, which by the ordering of revenues means .
import Mathlib import Definitions.Def_NestedLogitVariants_Competitive_Model
namespace NestedLogitVariants.Competitive
/-- Proof of Theorem 4, p. 15 (exchange step): if `(S*_1, …, S*_m)` is optimal and `S*_i`
contains product `j` but not product `k` with `k < j`, then adding `k` to `S*_i` gives an
assortment that is also optimal. -/
theorem insert_higher_revenue_optimal {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n) (hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (hfc : ∀ i, I.vnp i = 0) (hv0 : 0 < I.v0)
(Sstar : ι → Finset (Fin n)) (hopt : IsOptimal I Sstar)
(i : ι) (j k : Fin n) (hj : j ∈ Sstar i) (hk : k ∉ Sstar i) (hkj : k < j) :
IsOptimal I (Function.update Sstar i (insert k (Sstar i))) := by sorry
end NestedLogitVariants.Competitive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.