Simple method improves product assortment and matching decisions
A Unified Framework for Assortment Optimization and Matching under MNL Choice
Computer Science and Game Theory
Summary
Choosing the best set of products or matches for customers is tricky, especially when some options may not be available. The authors create a simple, unified approach that works well even when you don’t know in advance which products will be offered. Their method guarantees that you get at least half as much value as a perfect strategy that sees everything in advance. This approach helps improve many tasks like ride-hailing recommendations or matching buyers and sellers while handling realistic limits on product availability.
What this means in practice
- •For ecommerce platform operators: Improve the selection of product offers shown to customers with availability uncertainty while ensuring strong performance guarantees.
- •For ride-hailing service teams: Optimize notification strategies to riders and drivers using a unified model that accounts for uncertain availabilities and matching constraints.
Authors
Omar El Housni, Ulysse Hennebelle
Abstract
We develop a unified framework for assortment optimization and matching under multinomial logit (MNL) choice, yielding simple algorithms and analyses across a broad class of problems. The framework centers on a single-customer assortment problem in which the firm commits to eligible products before their independent availabilities are revealed. A simple threshold policy achieves a tight $1/2$ guarantee against a benchmark that selects its assortment after observing availability and may control dependence subject to the same marginal probability bounds. This guarantee accommodates cardinality constraints and adversarial removal of excess available products. Combined with problem-specific linear programming relaxations, the framework yields $1/2$ guarantees for standard two-sided assortment optimization, customization under mixtures of MNL models, ride-hailing notifications, multi-round broadcast matching, and MNL prophet inequalities, and a $1/4$ guarantee for fully static two-sided assortment optimization. Across these applications, we improve approximation factors, extend guarantees to more general revenues and cardinality constraints, and retain existing factors against stronger benchmarks.