Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments

Autor: Gerardo Berbeglia, Gwenaël Joret
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Class (set theory)
Computer Science::Computer Science and Game Theory
Mathematical optimization
General Computer Science
Computer science
0211 other engineering and technologies
Informatique appliquée logiciel
Context (language use)
0102 computer and information sciences
02 engineering and technology
Minimum spanning tree
01 natural sciences
Set (abstract data type)
Order (exchange)
Envy-free pricing
0502 economics and business
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Assortment problem
0202 electrical engineering
electronic engineering
information engineering
Stackelberg competition
Revenue
Data Structures and Algorithms (cs.DS)
Special case
Mathematics - Optimization and Control
Multinomial logistic regression
Mathematics
Choice set
Discrete choice
021103 operations research
Revenue management
Informatique générale
Heuristic
Applied Mathematics
05 social sciences
Function (mathematics)
Stackelberg games
Computer Science Applications
Mathématiques
Optimization and Control (math.OC)
010201 computation theory & mathematics
Theory of computation
020201 artificial intelligence & image processing
Mathematical economics
050203 business & management
Sciences exactes et naturelles
Zdroj: EC
Proceedings-ACM conference on Economics and Computation, ACM EC '17
Algorithmica, 82 (4
ISSN: 1432-0541
0178-4617
Popis: The assortment problem in revenue management is the problem of deciding which subset of products to offer 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 fixing 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 specific product from the set being offered cannot increase if the set is enlarged. This rationality assumption, known as regularity, is satisfied 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. (Prod Oper Manag 23(11):2023–2039, 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.
SCOPUS: ar.j
info:eu-repo/semantics/published
Databáze: OpenAIRE
Externí odkaz: