Theorem 1, p. 14 — the state space of the unique-ranking assortment DP has at most min(2^N, N·2^K) subproblems
ProvedConsiderChoose.StateSpace.theorem_1Consider the assortment problem under a consider-then-choose model with a single preference ranking: products numbered in preference order, and customer types with consideration sets . The dynamic program of §3 decomposes the problem along the connected components of the bipartite product–type graph, examines the products in preference order, and at each subproblem decides whether to stock ; each decision leaves a residual graph that splits into connected components, which become new subproblems. Let be the set of distinct nontrivial subproblems so generated. Then
Moreover, for every , if then .
The paper's algorithm spends operations per state, so this bound is what makes it quadratic in for a constant number of customer types and polynomial when , instead of examining all pairs .
Formalization Note. The bound holds for every instance: the state space depends only on the consideration sets, so no hypothesis on prices or type probabilities is involved. The second sentence of the paper's Theorem 1 concerns running time, which is not formalized here (there is no operation-count model); only its state-space content is stated, as the second conjunct with the floor logarithm Nat.log 2. States are nontrivial components (at least one product and one type); products are Fin N with the paper's product as 0.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_ConsiderChoose_StateSpace_Model
namespace ConsiderChoose.StateSpace
theorem theorem_1 {N K : ℕ} (C : Fin K → Finset (Fin N)) :
(stateSpace C).ncard ≤ min (2 ^ N) (N * 2 ^ K) ∧
∀ c : ℕ, K ≤ c * Nat.log 2 N → (stateSpace C).ncard ≤ N ^ (c + 1) := by sorry
end ConsiderChoose.StateSpace
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.