Online booking policy improves multi-copy product sales efficiency
Multi-Capacity Online Assortment Optimization with Consecutive Stays under Markov Chain Choice
Discrete Mathematics
Summary
This paper looks at how to best sell products when customers arrive randomly and want to book consecutive timeslots on one physical copy of a product. The researchers developed a new method that guesses product availability independently for each copy and updates bookings while keeping everything possible in real life. Their method performs well compared to the best possible strategy and works even when customers choose products based on complex preferences modeled by Markov chains. For simpler choice models, like the common multinomial logit, their approach guarantees better sales outcomes than some previous methods.
What this means in practice
- •For reservation system designers: create booking policies that efficiently assign multi-slot product reservations to physical copies under customer choice uncertainty.
- •For ecommerce platform operators: implement assortment offers that optimize expected revenue over repeated purchase requests with multi-copy product inventories.
Authors
Hongbin Zhang, Yanzhi Li, Woonghee Tim Huh
Abstract
We study online assortment optimization under Markov chain choice and independent Bernoulli arrivals, with each period's request type known in advance. Each product may have multiple interchangeable physical copies, and each booking reserves consecutive service slots on a single copy. Customers choose among products, while the platform assigns purchases to feasible copies. We develop a sales-based relaxation that upper-bounds the optimal online revenue and use it to design a policy with two components: independent sampling and purchase--update coupling. We generate independent copy proposals and make a product eligible whenever at least one of its copies proposes. A general revenue-extraction bound for random candidate sets with independent product inclusions shows that optimizing over eligible products recovers at least half of each period's relaxation revenue benchmark in expectation. A purchase--update coupling reproduces the interval flows through independent virtual copy updates while preserving physical feasibility. Under general Markov chain choice, the policy uses a random gate to make the coupling feasible: it offers the selected assortment with probability \(1-1/e\) and the empty assortment otherwise. No gate is needed under multinomial logit (MNL) choice. The resulting policies achieve approximation ratios of \((1-1/e)/2\) and \(1/2\), respectively, relative to the optimal nonanticipative online policy, independently of product capacities. In the single-copy MNL setting, our policy improves the guarantee of \citet{huwu2026} from \(0.271\) to \(1/2\) under the same arrival convention. The \(1/2\) static extraction factor and the \(1-1/e\) uniform scalar-gate factor are separately sharp, and the \(1/2\) MNL guarantee is tight for the proposed policy.