REU Project

Assortment optimization studies the problem of selecting a subset of products to offer to customers in order to maximize expected revenue under uncertain customer preferences. This problem is commonly modeled using probabilistic choice models, including Mallows-based ranking models that capture substitution behavior through distributions over customer rankings. However, full rankings may be unrealistic in settings where customers primarily distinguish between their most preferred alternatives, motivating the study of the Top-k Mallows Model, introduced by Chierichetti et al. in 2018. We investigate assortment optimization under the Top-k Mallows Model, where only a customer's top-k alternatives are ranked and all remaining alternatives are treated as indistinguishable. We first establish structural properties of choice probabilities arising from symmetries in the underlying Kendall-Tau distance. We show that unranked alternatives exhibit uniform choice behavior and that the contribution of unranked products to the optimal assortment depends on their cardinality. Using these properties, we develop an exact algorithm for assortment optimization with runtime \(\Theta(2^k n)\), improving upon exhaustive enumeration over all possible assortments. Finally, we develop a framework for approximation algorithms by conditioning on the position of the no-purchase option and derive probability bounds that support further approximation results.