WWW.DISSERTATION.XLIBX.INFO FREE ELECTRONIC LIBRARY - Dissertations, online materials

<< HOME
CONTACTS

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

# «ASSORTMENT OPTIMISATION UNDER A GENERAL DISCRETE CHOICE MODEL: A TIGHT ANALYSIS OF REVENUE-ORDERED ASSORTMENTS ¨ GERARDO BERBEGLIA AND GWENAEL JORET ...»

-- [ Page 1 ] --

¨

## 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. [2014]. 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 [2004] 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 3

three 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. [2014], 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 [2004]. We observe that two monotonicity results regarding revenue-ordered assortments that were established by Rusmevichientong et al. [2014] 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. [2014], 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 [2004]. 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. [2010] 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 [2012] 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. [2014], and computational methods to obtain good upper e ıaz bounds on the optimal revenue were given in Feldman and Topaloglu [2015]. Rusmevichientong et al. [2014] 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.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

Similar works:

«SCIENCE IN CHINA (Series C) Vol. 45 Supp. October 2002 Land use effects on terrestrial carbon sources and sinks Josep G. Canadell Global Carbon Project, GCTE, CSIRO Land and Water, PO Box 1666, Australia (email: pep.canadell@csiro.au) Received September 7, 2002 Abstract Current and past land use practices are critical in determining the distribution and size of global terrestrial carbon (C) sources and sinks. Although fossil fuel emissions dominate the anthropogenic perturbation of the global C...»

«UNITED STATES DEPARTMENT OF EDUCATION OFFICE OF SPECIAL EDUCATION AND REHABILITATIVE SERVICES REHABILITATION SERVICES ADMINISTRATION WASHINGTON, DC 20202 INFORMATION MEMORANDUM RSA-IM-03-12 DATE: June 19, 2003 ADDRESSEES: STATE VOCATIONAL REHABILITATION AGENCIES (GENERAL) STATE VOCATIONAL REHABILITATION AGENCIES (BLIND) STATE REHABILITATION COUNCILS REGIONAL REHABILITATION CONTINUING EDUCATION PROGRAMS CONSUMER ADVOCACY ORGANIZATIONS CLIENT ASSISTANCE PROGRAMS PROTECTION & ADVOCACY OF...»

«Nolo’s Guide to Living Trusts Table of Contents Living Trusts 101 how a living trust Works how a living trust helps your Family What living trusts Don’t Do Do you Also need a Will? Is a Living Trust Right for You? When to Use a trust one trust or two? Nolo’s Online Living Trust it Won’t take long you get More Than Just a living trust What you’ll need to get Started changing or revoking your living trust When you need a lawyer 2 | copyright © 2015 nolo S o you’re thinking about...»

«3 Proven Strategies to Avoid Boring E-Learning Paciﬁc Blue Solutions 55 Newhall Street BIRMINGHAM B3 3RB www.paciﬁcblue.co.uk www.paciﬁcblue.co.uk What’s in this guide? 3 Proven Strategies to Avoid Boring E-Learning provides a frank analysis of the shortcomings of many e-learning courses. It explains why the typical efforts of e-learning designers to achieve success and alleviate learner boredom are well-meaning, but misdirected. The guide acknowledges that when learners are bored or...»

«Division of Financial Operations STANDARD OPERATING PROCEDURES: OTPS PURCHASES Last Updated: September 15, 2016 1|Page TABLE OF CONTENTS CHAPTER 1 4 1.1 RATIONALE 4 1.2 OVERVIEW 4 1.3 USING THE FAMIS PORTAL 8 1.4 TOP AUDIT ITEMS 9 CHAPTER 2 11 2.1 AUTHORIZATION 11 2.2 REGULATIONS GOVERNING THE PURCHASING PROCESS 11 2.3 REGARDING PURCHASES FROM A CONTRACTED VENDOR 12 2.4 REGULATIONS RELATED TO COST 12 2.5 OTPS SPENDING – SERVING THE NEEDS OF EDUCATION 12 2.6 EXPENSES INCURRED BY A NON-NYC...»

«CHAC AND MAXIMON: PERSPECTIVES ON RELIGIOUS SYNCRETISM Religious syncretism is defined in many ways, but most definitions include the interpenetration of differing religions, a mingling of beliefs which changes the internal logic of a belief system. Such changes cause tension for orthodox religious leaders, but not necessarily for the people who practice syncretism (Mulder 204-205). Usually the term religious syncretism carries a pejorative connotation, especially when ones own beliefs are...»

«Case: 13-12613 Date Filed: 10/27/2014 Page: 1 of 25 [DO NOT PUBLISH] IN THE UNITED STATES COURT OF APPEALS FOR THE ELEVENTH CIRCUIT No. 13-12613 D.C. Docket No. 2:12-cr-14054-KMM-1 UNITED STATES OF AMERICA, Plaintiff-Appellee, versus CAMERON DEAN BATES, Defendant-Appellant. Appeal from the United States District Court for the Southern District of Florida (October 27, 2014) Before MARTIN, Circuit Judge, and EATON, * Judge, and HINKLE, ** District Judge. * Honorable Richard K. Eaton, United...»

«Exercise therapy and the treatment of mild or moderate depression in primary care Contents | Up and running? Contents i) Foreword............................................................................ 2 ii) Acknowledgements................................................................. 3 iii) Executive summary.......................»

«th Proceedings of ENCIT 2012 14 Brazilian Congress of Thermal Sciences and Engineering Copyright © 2012 by ABCM November 18-22, 2012, Rio de Janeiro, RJ, Brazil COMPARISON STUDY: ETHANOL PRODUCTION INCREASE THROUGH THE INTRODUCTION OF BAGASSE ENZYMATIC HYDROLYSIS & SURPLUS ELECTRICITY INCREASE, IN ETHANOL DISTILLERIES Reynaldo Palacios-Bereche, reynaldo.palacios@ufabc.edu.br Marcelo Modesto, marcelo.modesto@ufabc.edu.br Adriano Ensinas, adriano.ensinas@ufabc.edu.br Center of Engineering,...»

«CONFERENCE ABSTRACTS International Conference on Archaeology and Cultural Heritage in Pakistan and Adjacent Regions Islamabad, Jan 5-8, 2012 Sponsored by the American Institute of Pakistan Studies with support from the US Embassy, Islamabad In collaboration with the Department of Archaeology and Museums Ministry of National Heritage and Integration Government of Pakistan Radio Pakistan: Official Media Partner Archaeology  and  Cultural  Heritage  Conference:    Abstracts      ...»

«Part 3: Cubics, Trigonometric Methods, and Angle Trisection 1 Trigonometric Solution of the Casus Irreducibilis 1.1 Introduction The following argument is in essence due to Fran¸ois Vi`te (1540–1603). c e The result was published in 1615.1 Albert Girard (1595–1632) was the ﬁrst explicitly to use a version of identity (1) to solve cubic equations. In his L’Algebra (1572) Bombelli gives an ingenious geometric solution of the irreducible case. He is aware that his method is connected to...»

«Improving Tropical Cyclone Intensity Forecasting With Theoretically-Based Statistical Models PI: Wayne H. Schubert Department of Atmospheric Science Colorado State University Fort Collins, CO 80523-1371 Phone: (970) 491-8521 FAX: (970) 491-8449 e-mail: waynes@atmos.colostate.edu CO-PI: Mark DeMaria NOAA/NESDIS/StAR CIRA/CSU 1375 Campus Delivery Fort Collins, CO 80523-1375 Phone: (970) 491-8405 FAX: (970) 491-8241 E-mail: Mark.DeMaria@noaa.gov CO-PI: Charles R. Sampson Naval Research Laboratory...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.