Certified Block-Interaction Dynamic Programming for Sparse-Change Multiproduct Markdown Pricing

Source abstract

Finite-horizon multiproduct markdown pricing with interacting demands, finite inventories, and a hard limit on product-level price changes leads to a high-dimensional stochastic dynamic program. We develop a block-interaction capacity-compressed suffix dynamic program (BI-CCSDP) that combines bounded interaction blocks, compressed local recursions, and offline budget allocation to construct a feasible inventory-adaptive pricing policy. For fixed block size, the dynamic programming core is polynomial after surrogate construction, although unrestricted joint-kernel preprocessing can remain exponential. A computable regret certificate separates surrogate optimization error from discrepancies between the true and surrogate demand models. Under controlled stationarity and exact block-marginal correctness, we establish an O(T) upper bound on absolute regret, where T is the selling horizon. Synthetic experiments show modest revenue improvements over independent-product dynamic programming and small certified regret bounds relative to the inventory revenue scale under correct demand specification. Larger planning-parameter errors increase average revenue losses relative to a known-model reference and yield increasingly conservative certificates. A controlled block-size comparison further illustrates the trade-off between capturing demand interactions and computational cost. These findings clarify both the benefits of modeling interactions and the limitations of certification under demand misspecification.