Distribution-specific approximation guarantees for the random-parameters logit assortment problem

We consider the mixed logit assortment problem under continuously distributed random parameters (random-parameters logit). This problem is known to be NP-complete and approximation guarantees based on the revenue-ordered assortment exist. The revenue-ordered assortment solely contains products with the highest revenue. Using concentration inequalities, we propose upper bounds for the approximation guarantee. These bounds depend on the distribution of the customers’ utility function (random parameters). We present several product choice models from practice applications that empirically underpin our theoretical results. In our numerical studies, we provide the first evidence that the actual approximation performance quality depends on the specification of the customers’ utility, i.e., the underlying covariance pattern. In contrast to the current state of the literature, our results show that the approximation performance based on the revenue-ordered assortment can be arbitrarily bad. If the covariance between the mean utilities of the products is non-zero, the revenue-ordered assortment is non-optimal in 23 % of all instances (some problem sets obtain 100 % non-optimal instances). We report optimality gaps of about 8 % (with gaps increasing in the number of products). Hence, only in consumer markets where customers tend to primarily substitute between high-revenue products and the opt-out option, the revenue-ordered assortment performs well.