«ASSORTMENT OPTIMISATION UNDER A GENERAL DISCRETE CHOICE MODEL: A TIGHT ANALYSIS OF REVENUE-ORDERED ASSORTMENTS ¨ GERARDO BERBEGLIA AND GWENAEL JORET ...»
ASSORTMENT OPTIMISATION UNDER A GENERAL DISCRETE
CHOICE MODEL: A TIGHT ANALYSIS OF REVENUE-ORDERED
GERARDO BERBEGLIA AND GWENAEL JORET
Abstract. The assortment problem in revenue management is the problem of deciding which
subset of products to oﬀer to consumers in order to maximise revenue. A simple and natural strategy is to select the best assortment out of all those that are constructed by ﬁxing a threshold revenue π and then choosing all products with revenue at least π. This is known as the revenue-ordered assortments strategy. In this paper we study the approximation guarantees provided by revenue-ordered assortments when customers are rational in the following sense: the probability of selecting a speciﬁc product from the set being oﬀered cannot increase if the set is enlarged. This rationality assumption, known as regularity, is satisﬁed by almost all discrete choice models considered in the revenue management and choice theory literature, and in particular by random utility models. The bounds we obtain are tight and improve on recent results in that direction, such as for the Mixed Multinomial Logit model by Rusmevichientong et al. . An appealing feature of our analysis is its simplicity, as it relies only on the regularity condition.
We also draw a connection between assortment optimisation and two pricing problems called unit demand envy-free pricing and Stackelberg minimum spanning tree: These problems can be restated as assortment problems under discrete choice models satisfying the regularity condition, and moreover revenue-ordered assortments correspond then to the well-studied uniform pricing heuristic. When specialised to that setting, the general bounds we establish for revenue-ordered assortments match and unify the best known results on uniform pricing.
1. Introduction Revenue management consists of a set of methodologies permitting ﬁrms to decide on the availability and the price of their products and services. The development of this ﬁeld began in the late 1970’s in the airline industry, and has since been expanding constantly its practices into a large variety of markets such as grocery stores, retailing, railways, car rentals, accommodation, cruises, and more recently, electronic goods [Talluri and Van Ryzin, 2006].
At the core of revenue management lies the assortment problem, that of choosing an optimal subset of products/services to oﬀer to consumers in order to maximise the ﬁrm’s proﬁts. As an illustration, consider the case of a grocery store that has limited space for its coﬀee products.
Say it has space for at most 15 diﬀerent coﬀee products on the shelves but can choose between 300 products from its distributors (due to the combinations of coﬀee brands, coﬀee types, package sizes, etc). Given products’ costs and consumer demand, what is the best subset to oﬀer?
Date: July 6, 2016.
G. Joret was supported by a DECRA Fellowship from the Australian Research Council during part of the project.
2 G. BERBEGLIA AND G. JORET In order to solve the assortment problem, it is necessary to know (or at least be able to approximate) the consumer demand for each product, as a function of the assortment of products that are oﬀered. This issue has been widely studied in discrete choice theory, a ﬁeld which essentially tries to predict the choices of individuals when they select a product from a ﬁnite set of mutually exclusive alternatives, typically known as the choice set. Classical economic theory postulates that individuals select an alternative by assigning a real number known as utility to each option and then choosing the alternative from the choice set that has the maximum utility. Individuals are thus said to be utility maximisers. Diﬀerent assumptions about the distribution of the product utilities give rise to diﬀerent discrete choice models.
Prominent examples are the multinomial logit model (MNL model) [Luce, 1965] and the more general Mixed MNL model [Rusmevichientong et al., 2014].
There is a large literature on studies and methodologies for solving the assortment problem under diﬀerent discrete choice models such as the independent demand model, the MNL model [Talluri and Van Ryzin, 2004], and Mixed MNL model [Rusmevichientong et al., 2014].
A well-known heuristic is the revenue-ordered assortments strategy. It consists in selecting the best assortment out of all those that are constructed by ﬁxing a threshold π and then selecting all products whose revenue is at least π. This strategy is appealing for two reasons.
First, it only needs to evaluate as many assortments as there are diﬀerent revenues among products, independently of the number of products the ﬁrm oﬀers. Second, even if one has no knowledge about consumer choice behaviour, revenue-ordered assortments can still be used, one only needs to be able to evaluate the revenue of these revenue-ordered assortments. This second point is crucial in practice since most of the time not only the parameters of the assumed discrete choice model are not known but also it is not known what type of discrete choice model the consumers are following (e.g. MNL model, Nested MNL model, etc.). This motivates the study of the performance of revenue-ordered assortments under diﬀerent discrete choice models. Talluri and Van Ryzin  showed for instance that, when consumers follow the MNL model, the revenue-ordered assortments strategy is in fact optimal. In general however, this strategy does not always produce an optimal solution to the assortment problem.
1.1. Contributions. Our ﬁrst contribution is an analysis of the performance of the revenueordered assortments strategy making only minimal assumptions about the underlying discrete choice model: We assume that consumers behave rationally, in the sense that the probability of choosing a speciﬁc product x ∈ S when given a choice set S cannot increase if S is enlarged.
This rationality assumption, known as regularity, is satisﬁed by almost all models studied in the revenue management and choice theory literature. This includes in particular all random utility models, as well as other models introduced recently such as the additive perturbed utility model, the hitting fuzzy attention model, and models obtained using a non-additive random utility function (see Section 4 for a discussion of these models). We provide three types of revenue guarantees for revenue-ordered assortments: If there are k distinct revenues r1, r2,..., rk associated with the products (listed in increasing order), then revenue-ordered assortments approximate the optimum revenue to within a factor of (A) 1/k;
(B) 1/(1 + ln(rk /r1 )), and (C) 1/(1 + ln ν), where ν is deﬁned with respect to an optimal assortment S ∗ as the ratio between the probability of just buying a product and that of buying a product with highest revenue in S ∗. These
ASSORTMENT OPTIMISATION UNDER A GENERAL DISCRETE CHOICE MODEL 3three guarantees are in general incomparable, that is, (A), (B), or (C) can be the largest depending on the instance.
When applied to the special case of Mixed MNL models, bound (B) improves the recent analysis of revenue-ordered assortments by Rusmevichientong et al. , who showed a bound of 1/(e(1 + ln(rk /r1 ))). After ﬁnishing a preliminary version of this paper, we learned of independent results by Aouad et al. [2015b] on the approximation guarantees of revenueordered assortments. In the important case of random utility models, they showed a bound of Ω(1/ln(rk /r1 )), which is thus within a constant factor of our bound (B). (In fact, one can ˜ deduce a bound of 2/(5 ln(rk /r1 ) ) from their proof.) They also proved a bound of Ω(1/ln λ), ˜ is the probability of buying a product when oﬀered the set consisting of only the where λ products with highest revenue. This is closely related to bound (C) above, as it can be shown ˜ that ν λ.
Complementing our analysis, we show that the three bounds (A), (B), and (C) are exactly tight, in the sense that none of the bounds remains true if multiplied by a factor (1 + ) for any
0. Let us remark that bounds (A) and (B) also provide a quick and easy way to obtain some upper bound on the optimum revenue that can be achieved on a given instance, by simply checking the revenue provided by revenue-ordered assortments. While the resulting upper bounds can of course be far from the optimum, they have the merit of being straightforward to compute, independently of how complex the underlying discrete choice model is, as long as it satisﬁes the regularity condition. Bound (C) on the other hand is typically hard to compute exactly as it involves knowing an optimal solution; nevertheless, some non-trivial bounds that are easy to compute can be deduced from (C) by bounding ν from above (using the bound ˜ ν λ mentioned above for instance).
Our second contribution is to draw a connection between assortment optimisation and some pricing problems studied in the theoretical computer science literature by showing that these pricing problems can be restated as an assortment problem under a discrete choice model satisfying the above-mentioned rationality assumption. This includes unit demand envy-free pricing problems and the Stackelberg minimum spanning tree problem (see Section 4 for deﬁnitions). Building on that connection, we then observe that a well-studied heuristic in that area called uniform pricing corresponds in fact to the revenue-ordered assortment strategy for the speciﬁcally constructed discrete choice models. As a consequence, our revenue guarantees for revenue-ordered assortments apply. Interestingly, the resulting bounds match and unify known results on uniform pricing that were proved separately in the literature for the envy-free pricing problems and the Stackelberg minimum spanning tree problem.
We conclude the paper with a brief analysis of the single-leg multi-period setting with limited capacity as studied by Talluri and Van Ryzin . We observe that two monotonicity results regarding revenue-ordered assortments that were established by Rusmevichientong et al.  in the context of Mixed MNL models hold more generally for the discrete choice models considered in this paper. As mentioned by Rusmevichientong et al. , these results could potentially be used in the implementation of standard revenue management systems.
1.2. Related literature. The assortment problem is an active research topic in revenue management, and providing an exhaustive literature review is beyond the scope of this paper.
In this section, we focus mostly on previous works that are directly related to our contributions.
4 G. BERBEGLIA AND G. JORET One of the ﬁrst studies of the assortment problem for a general discrete choice model was carried out by Talluri and Van Ryzin . In that paper, the authors considered a singleleg seat allocation problem in which a ﬁrm sells aircraft seats to consumers arriving one at a time. Each consumer selects at most one fare among the ones that are oﬀered, and the ﬁrm has to decide the subset of fares to oﬀer at each time period, depending on the number of available seats and time periods remaining. The authors have shown that this problem reduces to solving a static (or single shot) assortment problem in which one wishes to maximise the expected proﬁt on a single consumer without caring about capacity. For the special case in which the consumer choice model is the Multinomial Logit (MNL) model, they proved that the optimal choice sets are revenue-ordered assortments. Thus, solving the assortment problem when consumers follow a MNL model can be done eﬃciently in polynomial time.
Again under the MNL model, Rusmevichientong et al.  studied the assortment problem subject to the constraint that there is maximum number of products that can be shown in the assortment. Although the assortment sometimes fails to be a revenue-ordered assortment, the authors proved than an optimal assortment can still be found in polynomial-time. Another extension of the assortment problem over MNL model was considered by Rusmevichientong and Topaloglu  where the authors formulated the problem as a robust optimization problem in which the true parameters are unknown.
Another series of papers studied the assortment problem in which diﬀerent shares of customers follow diﬀerent MNL models, a model known as the Mixed MNL model. The assortment problem under a Mixed MNL model is NP-hard [Bront et al., 2009]. A branch-and-cut algorithm was presented by M´ndez-D´ et al. , and computational methods to obtain good upper e ıaz bounds on the optimal revenue were given in Feldman and Topaloglu . Rusmevichientong et al.  proved that the problem remains NP-hard even when the model is composed of only two customer types. The authors also studied the performance of revenue-ordered assortments in this setting, and proved in particular an approximation ratio of 1/(e(1 + ln(rk /r1 ))), as mentioned earlier.