§3, Eq. (1), p. 13 — the dynamic-programming recursion: stock min(S) or not
ProvedConsiderChoose.StateSpace.recursion_1In the setting of the consider-then-choose assortment problem with a unique ranking (products numbered in preference order, prices , types with consideration sets and weights ), let be a subproblem with whose graph is connected, and let be its most preferred product. Write , let be the connected components of and those of . Then
The first term is the value of stocking product : every type in buys it, and those types leave the problem. The second is the value of not stocking it. This is the recursion the dynamic program solves on its state space.
Formalization Note. The component sums run over all components, trivial ones included (they contribute ). No condition on or is assumed.
import Mathlib import Definitions.Def_ConsiderChoose_StateSpace_Model
namespace ConsiderChoose.StateSpace
theorem recursion_1 {N K : ℕ} (I : Instance N K) (S : Finset (Fin N)) (T : Finset (Fin K))
(h : S.Nonempty) (hc : GConnected I.C S T) :
J I S T =
max (I.P (S.min' h) * ∑ j ∈ typesOf I.C T (S.min' h), I.lam j +
∑ p ∈ comps I.C (S.erase (S.min' h)) (T \ typesOf I.C T (S.min' h)), J I p.1 p.2)
(∑ p ∈ comps I.C (S.erase (S.min' h)) T, J I p.1 p.2) := by sorry
end ConsiderChoose.StateSpace
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.