Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints

Elaheh Fata, Will Ma, David Simchi-Levi

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:

  1. 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.
  2. 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.
  3. 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.

Summary of approximation guarantees and arrival models for various problem settings.

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

Abstract

We consider an assortment optimization problem where a customer chooses a single item from a sequence of sets shown to her, while limited inventories constrain the items offered to customers over time. In the special case where all of the assortments have size one, our problem captures the online stochastic matching with timeouts problem. For this problem, we derive a polynomial-time approximation algorithm which earns at least 1-ln(2-1/e), or 0.51, of the optimum. This improves upon the previous-best approximation ratio of 0.46, and furthermore, we show that it is tight. For the general assortment problem, we establish the first constant-factor approximation ratio of 0.09 for the case that different types of customers value items differently, and an approximation ratio of 0.15 for the case that different customers value each item the same. Our algorithms are based on rounding an LP relaxation for multi-stage assortment optimization, and improve upon previous randomized rounding schemes to derive the tight ratio of 1-ln(2-1/e).
BibTeX
@misc{fata2019multi,
  author = {Elaheh Fata and Will Ma and David Simchi-Levi},
  title = {{Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints}},
  year = {2019},
  eprint = {1908.09808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.09808},
}
Figure