Real-time optimization of personalized assortments

ABSTRACT

Motivated by the availability of real-time data on customer characteristics, we consider the problem of personalizing the assortment of products to each arriving customer. For an arriving customer of type z, the company must decide, in real-time, on the assortment of products to offer. Given the offered assortment, the customers make choices on which products to buy, if any, according to a general choice model that is specific to each customer type. Our goal is to develop a revenue-maximizing policy that determines the assortment to offer to each arriving customer, taking into account the customer type and the current inventories.

We propose a family of simple and effective algorithms, called Inventory-Balancing, for real-time personalized assortment optimization. Each Inventory-Balancing algorithm is characterized by the penalty function that discounts the marginal revenue of each product, as the inventory level reduces. By adjusting the revenue of each product according to its remaining inventory, the algorithms hedges against the uncertainty in the types of future customers, by reducing the rate at which products with low inventory are offered. Thus, Inventory-Balancing serves as a simple mechanism that coordinates the front-end customer-facing decision with the back-end supply chain constraints.

In particular, we prove that Inventory-Balancing algorithms with a strictly concave penalty function always obtain more than 50% of the optimal revenue. We also provide an Inventory-Balancing algorithm that obtains at least 1-1/e ≈ 63% of the benchmark revenue. The 63% ratio is optimal in the sense that no other deterministic or stochastic policies can achieve a higher value. In our numerical experiments, our algorithms perform even better than what is predicted by the worst-case bound, and they obtain revenues that are within 94% of the optimal. Through actual sales data from an online retailer, we also demonstrate that personalization based on each customer's location can lead to over 10% improvements in revenue, compared to a policy that treats all customers the same.

Index Terms

• Theory of computation

  • Design and analysis of algorithms