Introduction
Modern e-commerce platforms often engage customers in multi-stage interactions. A customer might browse a sequence of product assortments—for instance, clicking through multiple pages of search results—until they either find a suitable item or abandon the session due to a lack of patience. While previous research has modeled these sequential interactions for individual customers, it often overlooks the critical supply-side constraint: inventory is finite and shared across a diverse stream of customers over time.
This paper addresses the multi-stage, multi-customer assortment optimization problem with inventory constraints. The goal is to develop algorithms that maximize expected revenue over a finite horizon, balancing the immediate desire to satisfy a current customer with the long-term need to preserve inventory for future, potentially higher-value arrivals.
Methodology
Solving this problem exactly is computationally prohibitive due to the curse of dimensionality inherent in dynamic programming. To overcome this, the authors propose polynomial-time approximation algorithms based on a Multi-stage Choice-based Deterministic Linear Program (MCDLP) benchmark. This LP provides a theoretical upper bound on the maximum achievable revenue.
The algorithmic framework involves three main components:
- Offline Black-Box Rounding: The fractional solutions from the MCDLP are converted into discrete assortment decisions using a randomized rounding scheme. By prioritizing items with lower sales probabilities, the authors improve upon existing rounding techniques to enhance worst-case performance.
- Attenuation Framework: To prevent high-performing items from depleting inventory too quickly, the algorithm employs an "attenuation" strategy. This artificially throttles the offering probability of over-performing items, ensuring that inventory remains available for items that are harder to sell but necessary for achieving theoretical guarantees.
- Efficient Computation: For the popular Multinomial Logit (MNL) choice model, the authors utilize column generation to solve the LP efficiently, resulting in a Fully Polynomial-Time Approximation Scheme (FPTAS).
Key Insights: Repeated vs. Non-repeated Offerings
A significant finding of this research is how the complexity of the problem changes based on whether items can be offered repeatedly to the same customer.
- Repeated Offerings: If the platform can show the same item across different stages, the problem is more tractable. The authors achieve a tight 0.51 approximation ratio in this setting.
- Non-repeated Offerings: If a customer's rejection of an item is permanent, the problem becomes significantly more complex. Despite this, the authors establish the first constant-factor guarantees for this scenario.
Furthermore, the research identifies a "Goldilocks" zone for inventory management. While simple greedy or conservative heuristics may suffice when inventory is extremely abundant or scarce, the proposed LP-based algorithms demonstrate superior performance in realistic, moderate-inventory scenarios.
Key Results
The theoretical contributions of this work include closing the gap for single-item sequential offerings and providing the first constant-factor guarantees for general multi-stage assortments.
As shown in the table above, the authors achieved a tight 0.51 approximation ratio for online stochastic matching with timeouts and multi-stage assortments with repeated offerings. For the more challenging case without repeated offerings, they established a 0.09 guarantee, which improves to 0.15 when items are priced homogeneously across customer types.
Empirical evaluations using a real-world hotel booking dataset from Bodea et al. (2009) further validate these results. In simulations with synthetic "patience levels," the proposed algorithms consistently outperformed standard baselines in scenarios with moderate loading factors.
Conclusion and Future Directions
This work provides a robust theoretical and practical framework for managing inventory in interactive e-commerce environments. However, several avenues for future research remain. The current model assumes a known, stationary arrival process for customers, whereas real-world traffic often exhibits non-stationary trends. Additionally, while the model assumes sequential sessions, extending the framework to handle overlapping customer sessions—where multiple users browse simultaneously—could further enhance its applicability to high-traffic platforms. Finally, accurately estimating customer patience levels in practice remains a key challenge for implementation.
Summary updated