TL;DR
This paper introduces a new model for how customers choose products, called the Sequential Multinomial Logit (SML) model, which can explain complex behaviors like the attraction and compromise effects that standard models can't. The authors then develop an efficient algorithm to find the optimal product assortment for this SML model, proving that it's solvable in polynomial time.
What Problem Does This Paper Address?
In revenue management, businesses need to decide which products to offer to maximize their profits. This is known as the assortment optimization problem. Traditional approaches often rely on simple choice models like the Multinomial Logit (MNL), which assume customers decide on a product beforehand and don't consider substitutions. While these models are computationally tractable, they fail to capture realistic consumer behavior, such as how adding a new product might unexpectedly increase the popularity of an existing one (attraction effect) or how consumers might favor "middle-ground" options (compromise effect). These phenomena, often referred to as violations of regularity, are crucial for accurate demand prediction and optimal assortment decisions. This paper addresses this gap by proposing a more sophisticated choice model, the SML, and developing an efficient method to solve the assortment problem under this new model.
Methods
The core of this paper lies in two main contributions:
- The Sequential Multinomial Logit (SML) Model: This model extends the standard MNL by partitioning products into two levels based on attractiveness or perception priority. Customers first consider products in the higher priority level. If they don't find a suitable product there, they then consider products in the lower priority level. This sequential consideration allows the SML model to capture behavioral phenomena like attraction and compromise effects, which are not possible with standard random utility models. The SML is presented as a special case of the broader Perception-Adjusted Luce Model (PALM).
- Revenue-Ordered by Level Assortments: For the standard MNL model, it's known that optimal assortments can be found using a "revenue-ordered" strategy. The authors generalize this concept to "revenue-ordered by level" assortments for the SML model. They prove that any optimal assortment under the SML must be revenue-ordered by level. This structural property is key to developing a polynomial-time algorithm for assortment optimization. The algorithm essentially involves searching through a structured set of candidate assortments, rather than all possible subsets of products.
Datasets
Not discussed in the paper. The paper focuses on theoretical development and uses numerical experiments to validate its findings, rather than relying on specific real-world datasets.
Key Insights and Ideas
- Beyond Regularity: The paper highlights that standard choice models based on random utility violate the "regularity" condition, which states that adding an option to a choice set cannot increase the probability of choosing an existing option. The SML model, by contrast, allows for these violations, making it more realistic for capturing complex consumer behavior.
- Two-Level Structure is Powerful: The simple addition of a two-level sequential decision process to the MNL model is shown to be sufficient to explain phenomena like attraction and compromise effects, which have puzzled researchers for decades.
- Generalizing Revenue Ordering: The concept of revenue-ordered assortments, a cornerstone for solving the MNL assortment problem efficiently, is successfully generalized to the SML model. This generalization is crucial for developing an efficient algorithm.
- Polynomial-Time Solvability: The most significant outcome is the proof that assortment optimization under the SML model is solvable in polynomial time. This is a major theoretical advancement, as many complex choice models lead to NP-hard optimization problems.
Key Results
- SML Model: The paper formally defines the Sequential Multinomial Logit (SML) model and demonstrates its ability to capture attraction and choice overload effects through illustrative examples.
- Revenue-Ordered by Level Property: The paper proves that all optimal assortments under the SML model are "revenue-ordered by level." This means optimal assortments can be constructed by selecting products from each level in descending order of revenue, up to a certain threshold for each level.
- Polynomial-Time Algorithm: As a direct consequence of the revenue-ordered by level property, the assortment optimization problem under the SML is shown to be solvable in polynomial time.
- Numerical Experiments: Experiments show that the proposed revenue-ordered by level strategy (ROL) is optimal, while the traditional revenue-ordered strategy (RO) can have significant optimality gaps (up to 26.319% in their tests). The ROL strategy is computationally efficient, taking only a small amount of additional time compared to RO.
Limitations and Future Work
- Generalizing to More Levels: The current work focuses on a two-level SML model. The authors conjecture that their revenue-ordered by level approach can be extended to the general Perception-Adjusted Luce Model (PALM) with an arbitrary number of levels, but acknowledge that their proof techniques do not directly apply to this more general case. This remains an open research question.
- Dynamic Level Ordering: The SML model assumes a fixed ordering of product levels. Future work could explore models where decision-makers can dynamically change the order in which levels are presented to consumers.
- Cardinality/Space Constraints: The current model does not account for constraints on the number of products that can be offered or the physical space available. Studying assortment optimization under the SML with such constraints is a promising direction.
- Parameter Estimation: Developing efficient methods to estimate the parameters of the SML model from historical data is highlighted as an important area for future research.
Summary updated