Abstract
Traditional choice models in revenue management, such as the Multinomial Logit (MNL) model, often fail to capture complex consumer behaviors like product dominance and regularity violations. This paper investigates the Two-Stage Luce Model (2SLM), a framework where consumers first eliminate dominated products before making a selection. We establish the computational complexity of assortment optimization under this model, proving that while the unconstrained problem is solvable in polynomial time, the capacitated version is NP-hard. Furthermore, we introduce a "three-price" strategy for joint assortment and pricing optimization under a threshold-based dominance structure.
Introduction
In Revenue Management (RM), the dual challenges of assortment selection and pricing are central to maximizing profitability. For decades, the Multinomial Logit (MNL) model has been the industry standard due to its mathematical tractability. However, MNL relies on two restrictive assumptions: the Independence of Irrelevant Alternatives (IIA) and Regularity. IIA assumes that the relative preference between two items remains constant regardless of other options, while regularity dictates that adding a new product cannot increase the probability of selecting an existing one.
Empirical evidence suggests that consumers often utilize a "consider-then-choose" heuristic. In these scenarios, a high-quality product might "dominate" a lower-quality one, removing it from the consumer's consideration set entirely. Paradoxically, the introduction of a new product can sometimes increase the sales of an existing item by eliminating a third, cannibalizing option. The Two-Stage Luce Model (2SLM) formally captures these dynamics, offering a more realistic representation of consumer choice at the cost of increased computational complexity.
The Two-Stage Luce Model (2SLM)
The 2SLM operates in two distinct phases:
- Elimination: Given an assortment, the consumer identifies and removes all products that are "dominated" by at least one other item in the set.
- Selection: The consumer applies a standard MNL choice process to the remaining "non-dominated" products.
This structure allows for the modeling of "decoy effects" and other behaviors that violate the regularity condition. The primary challenge addressed in this research is how to optimize revenue when the underlying choice process involves these non-linear dominance relationships.
Computational Complexity and Algorithms
The authors categorize the optimization problem into three primary domains:
1. Unconstrained Assortment Optimization
In the absence of shelf-capacity limits, the problem is to select a subset of products that maximizes expected revenue. The authors demonstrate that this can be mapped to finding a Maximum Weighted Independent Set within a comparability graph. By employing Megiddo’s Algorithm (1979) for rational objective functions, they prove that the unconstrained 2SLM assortment problem is solvable in polynomial time.
2. Capacitated Assortment Optimization
When a constraint is placed on the number of products offered (e.g., limited physical space), the problem becomes significantly more difficult. The paper provides a formal proof that the capacitated assortment problem under 2SLM is NP-hard. To provide practical solutions, the authors develop polynomial-time algorithms for specific dominance structures, such as "forests" (hierarchical tree structures) or cases where dominance is perfectly correlated with product attractiveness.
3. Joint Pricing and Assortment
The research extends to the Threshold Luce Model (TLM), a variant where dominance is determined by whether a product's attractiveness ratio exceeds a specific threshold. To solve the joint pricing problem, the authors utilize the Lambert W function to handle the transcendental equations arising from the revenue objective. This leads to the discovery of a "three-price" strategy, where the optimal solution typically involves a uniform price for most items, with specific adjustments made only for the most and least attractive products to strategically manage dominance links.
Experimental Results
Using 48 classes of synthetic instances and over 12,000 simulated scenarios, the authors compared their 2SLM-OPT algorithm against the standard Revenue-Ordered (RO) heuristic commonly used in MNL contexts.
Key findings include:
- The Optimality Gap: Ignoring dominance relations can lead to a revenue loss of up to 95%. This occurs because the RO heuristic may include products that dominate high-margin items, inadvertently lowering total revenue.
- Efficiency: The proposed
TLM-Optpricing algorithm proved highly efficient, consistently reaching optimal solutions in less than 0.5 seconds for the tested instances. - Scalability: As the number of products and the strength of the "outside option" (the probability of a customer buying nothing) increased, the performance gap between the 2SLM-optimized strategy and traditional heuristics widened, highlighting the importance of accounting for dominance in competitive markets.
Conclusion and Future Work
This research provides a rigorous mathematical foundation for assortment optimization under models that violate the regularity condition. By establishing the boundaries of polynomial-time solvability and providing efficient algorithms for pricing, the paper bridges the gap between complex behavioral theory and practical revenue management.
Future research directions include generalizing the pricing model to account for differentiated price sensitivities across products and integrating "attention models" to create a three-stage framework that accounts for both limited visibility and product dominance.
Summary updated