Multi-Purchase Assortment Optimization Under a General Random Utility Model

The static assortment optimization problem is a classical and well-studied problem where customers choose a single item according to some customer choice model like the ubiquitous random utility model. However, the variant where customers purchase multiple items has received less attention, primarily due to the added complexity of modeling utility-maximizing behavior over sets of items, even when considering natural extensions of the standard MNL choice model. In this paper, we propose a general multi-purchase choice model that can be viewed as a natural extension of the single-purchase choice models. We also study the respective assortment optimization problem without making specific distributional assumptions on the random utilities. We propose a computationally efficient algorithmic framework that is motivated by an asymptotic regime, which we dub the large-offering regime, where the number of items available to the retailer grows large. Through this asymptotic lens, we develop an efficient approximation algorithm with corresponding asymptotic optimality guarantees under general utility distributions. Our numerical results demonstrate that our algorithm is very competitive even when we are far away from our limiting regime. For example, when the number of items available to the retailer is modest, or when customers choose only a single item.