Assortment Optimization under the General Luce Model

Álvaro Flores, Gerardo Berbeglia, Pascal Van Hentenryck

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:

  1. Elimination: Given an assortment, the consumer identifies and removes all products that are "dominated" by at least one other item in the set.
  2. 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-Opt pricing 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

Abstract

This paper studies the assortment optimization problem under the General Luce Model (GLM), a discrete choice introduced by Echenique and Saito (2015) that generalizes the standard multinomial logit model (MNL). The GLM does not satisfy the Independence of Irrelevant Alternatives (IIA) property but it ensures that each product has an intrinsic utility and uses a dominance relation between products. Given a proposed assortment $S$, consumers first discard all dominated products in $S$ before using a MNL model on the remaining products. The General Luce Model may violate the traditional regularity condition, which states that the probability of choosing a product cannot increase if the offer set is enlarged. As a result, the model can model behaviour that cannot be captured by any discrete choice model based on random utilities. The paper proves that the assortment problem under the GLM is polynomially-solvable. Moreover, it proves that the capacitated assortment optimization problem under the General Luce Model (GLM) is NP-hard and presents polynomial-time algorithms for the cases where (1) the dominance relation is utility-correlated and (2) its transitive reduction is a forest. The proofs exploit a strong connection between assortments under the GLM and independent sets in comparability graphs.
BibTeX
@misc{flores2017assortment,
  author = {Álvaro Flores and Gerardo Berbeglia and Pascal Van Hentenryck},
  title = {{Assortment Optimization under the General Luce Model}},
  year = {2017},
  url = {https://openreview.net/forum?id=-dOmWLBoHW6},
}
Figure