Assortment Planning for Recommendations at Checkout under Inventory Constraints

In this paper, we consider a personalized assortment planning problem under inventory constraints, where the type of each arriving customer is defined by a primary item of interest. As long as that item is in stock, the customer adds it to her shopping cart, at which point the retailer can recommend to the customer an assortment of add-ons to go along with her primary item. This problem is motivated by the new "recommendation at checkout'' systems that have been deployed at many online retailers, and also serves as a framework which unifies many existing problems in online algorithms (personalized assortment planning, single-leg booking, online matching with stochastic rewards). In our problem, add-on recommendation opportunities are eluded when primary items go out of stock, which poses additional challenges for the development of an online policy. We overcome these challenges by introducing the notion of an inventory protection level in expectation, and derive an algorithm with a 1/4 competitive ratio guarantee under adversarial arrivals