Theorem 4.2 — revenue-ordered and nested optimal assortments
ProvedXuMultistage.Structure.theorem_4_2Consider two finite catalogs and with arbitrary real deterministic utilities and exogenous real prices weakly decreasing within each stage. Price ties are allowed. Option is always available at each stage and has price and deterministic utility zero. The seller commits to an initial assortment and a continuation assortment for each . Empty assortments are permitted, and is freely chosen. The customer uses the two-stage probabilities (1), and the seller maximizes the undiscounted revenue (2).
When , there exists one optimal policy among all such deterministic policies satisfying all three properties:
- Revenue-ordered in the first stage: for some .
- Revenue-ordered in the second stage: for every , for some .
- Nested in the second stage:
In particular, the three clauses hold simultaneously, with no comparison required between and the other continuations. This is an exact existence result for a globally optimal policy.
Formalization Note A policy stores ordinary-product assortments and inserts the two outside options when forming its path matrix. Values of continuations after unavailable first-stage products are ignored. Nesting is expressed as for offered positive indices , equivalent to the displayed chain because is a prefix.
Differences from the source:
- encoding: a deterministic policy with continuations on active histories and a chain of nested assortments → finite sets with irrelevant continuations on inactive rows and pairwise inclusions for offered positive indices; reason: every source policy has such an extension, the objective ignores its inactive entries, and on a prefix the pairwise inclusions are exactly the printed chain
- encoding: the expected revenue objectives in (2), (5), and (9) → the finite sum of exact first-stage probabilities times conditional total revenues; reason: this equals the path-probability objective on every feasible matrix; at gamma one it is exactly (5), and for positive gamma it is (9)
import Definitions.Def_XuMultistage_Structure_Revenue import Definitions.Def_XuMultistage_Structure_RevenueOrdered
namespace XuMultistage.Structure
theorem theorem_4_2 {n₁ n₂ : ℕ} (M : Model n₁ n₂) (horder : M.Ordered) :
∃ π : Policy n₁ n₂, IsOptimalPolicy M 1 π ∧
RevenueOrdered π.first ∧
(∀ i : Fin (n₁ + 1), (i = 0 ∨ i ∈ π.first) → RevenueOrdered (π.next i)) ∧
(∀ i ∈ π.first, ∀ k ∈ π.first, k ≤ i → π.next i ⊆ π.next k) := by sorry
end XuMultistage.Structure
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.