pp. 16–17 — the optimal solutions of (9) depend only on the ordering and signs of the utilities
ProvedConstrNestedLogit.Card.knapsack_optimal_order_signassortment-optimizationknapsackp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a nest , a cardinality limit , and write for the utility of product in problem (9). Let be two values at which the utilities have
- the same ordering: for all products , if and only if ;
- the same signs: for every product , and are both positive, both zero, or both negative (the same position relative to the line ).
Then for every assortment ,
Applied to two values in one of the intervals between consecutive intersection points of the lines , this says that the optimal solution of (9) does not change inside such an interval.
Formalization Note The ordering is compared as a weak order, so ties are allowed, and the conclusion is about the whole set of optimal solutions, not about one selected solution. The signs are compared with Mathlib's SignType.sign.
Preamble
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model import Definitions.Def_ConstrNestedLogit_Card_Knapsack open NestedLogitVariants.LP
Formal statement
namespace ConstrNestedLogit.Card
/-- The optimal solutions of the knapsack problem (9) depend only on the ordering and signs of
the utilities (pp. 16–17): if at `u` and `u'` the utilities `{f_ij : j ∈ N}` are ordered the
same way (as a weak order, ties included) and have the same signs (comparison with
`f_i0 = 0`), then `S` is optimal for (9) at `u` if and only if it is optimal at `u'`. -/
theorem knapsack_optimal_order_sign {ι : Type*} {n : ℕ} (I : Instance ι n) (c : ι → ℕ) (i : ι)
(u u' : ℝ)
(horder : ∀ j k : Fin n, utility I i j u ≤ utility I i k u ↔ utility I i j u' ≤ utility I i k u')
(hsign : ∀ j : Fin n, SignType.sign (utility I i j u) = SignType.sign (utility I i j u'))
(S : Finset (Fin n)) :
IsKnapsackOptimal I c i u S ↔ IsKnapsackOptimal I c i u' S := by sorry
end ConstrNestedLogit.Card
Source
Gallego & Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science (2014), DOI 10.1287/mnsc.2014.1931; authors' manuscript of Sept. 11, 2013, pp. 16–17, discussion of problem (9) and Figure 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.