A Unified Framework to Impose Market Share Constraints for Selected Product Classes: Randomized and Deterministic Assortments Under the Multinomial Logit Model

Problem definition: We study assortment optimization problems with market share constraints. The products are partitioned into product classes, each with a market share threshold. If a product class is represented in the offered assortment, then the total purchase probability of the products offered in the class should be above the market share threshold of the product class. Customers choose among offered products according to the multinomial logit model. The goal is to maximize the expected revenue while satisfying the market share constraints. Our work is motivated by the fact that focusing only on maximizing the expected revenue often results in offering many products with small demand quantities, causing operational burden. Retailers are interested in ensuring that the products represented in their assortments command reasonably large demand quantities. Methodology/results: Imposing the market share constraints only for product classes represented in the offered assortment brings unique unexplored dynamics. In the randomized variant, we randomize the offered assortments. In the deterministic variant, we offer a single assortment. The randomized variant is NP-hard, whereas the deterministic variant is NP-hard to approximate within a factor of $\frac{1}{2}$. Our main contributions are a fully polynomial-time approximation scheme for the randomized variant, an approximation scheme for the deterministic variant that yields a $(1-ϵ)$-approximate solution while violating market share constraints with a $(1-ϵ)$-factor in running time that is polynomial in $\frac{1}{ϵ}$, and a $\frac{1}{2}$-approximation algorithm for the deterministic variant that yields a solution satisfying market share constraints exactly in running time that is pseudopolynomial in the input size. We develop a unified approximation framework that applies to both variants and leverage this approximation framework. Managerial implications: We are motivated by a practical need for assortments where the offered products command reasonably large demand quantities. Imposing market share constraints for the selected product classes is a natural way to satisfy this need.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1396.