Lemma 1, p. 12 — J(S,T) is the sum of J over the connected components of G[S,T]
ProvedConsiderChoose.StateSpace.lemma_1Consider a consider-then-choose instance with a unique ranking: products numbered in preference order, prices , customer types with consideration sets and weights . For and let , and let be the connected components of the bipartite graph (an edge joins product and type when ). Then
The lemma says that the subproblem splits into independent subproblems, one per connected component. It is the base case of the dynamic program and is applied again after every stocking decision.
Formalization Note. The sum runs over all components of , including isolated products and isolated types , as in the paper's partition; each of these contributes . No sign or normalisation condition on or is assumed: the identity holds for every instance, so the standing assumption that is a probability vector is not needed and not carried.
import Mathlib import Definitions.Def_ConsiderChoose_StateSpace_Model
namespace ConsiderChoose.StateSpace
theorem lemma_1 {N K : ℕ} (I : Instance N K) (S : Finset (Fin N)) (T : Finset (Fin K)) :
J I S T = ∑ p ∈ comps I.C S 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.