CS Paper Radar

The Value of Experiments in Assortment Optimization

Mohammadreza Ahmadnejadsaein, Amine Bennouna, Omar El Housni

cs.DS math.OC ·submitted 2026-10-29 17:40 UTC · v1

Abstract

Retailers can learn customer preferences by experimenting with different assortments. However, the cost of each experiment and the operational burden of repeatedly changing product offerings can make extensive experimentation impractical. We study how much a retailer can improve its final assortment decision using customer observations from one (or a very small number of) fixed experimental assortments. We consider the multinomial logit model, where product revenues are known but customer preferences are unknown. In this setting, we jointly design the experimental assortment and the rule for selecting a final assortment from observed customer choices to minimize worst-case regret: the expected revenue loss of the final assortment relative to an optimal assortment under the true preferences, maximized over possible customer preferences. We first characterize exactly the minimax regret and an optimal assortment when no experimentation is possible. We then show, surprisingly, that offering a single experimental assortment to just one customer can already substantially reduce regret, depending on how the products' revenues compare. We derive the exact minimax regret and an optimal experimental policy in this setting. When a single fixed experimental assortment is offered to many customers, we give a geometric characterization of the limiting minimax regret and construct an asymptotically optimal policy. Depending on product revenues, this single experiment can yield no improvement over no experimentation or nearly complete regret reduction. Finally, we extend our analysis to multiple experimental assortments chosen in advance, characterizing the limiting minimax regret, constructing asymptotically optimal policies, and identifying which collections of assortments allow worst-case regret to vanish as the number of customer observations grows.

Closest papers

Nearest neighbours by meaning across the whole index.

A Unified Framework for Assortment Optimization and Matching under MNL Choice

cs.GT math.OC ·2026-10-26 ·Omar El Housni, Ulysse Hennebelle
benchmark similarity 0.73
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.

0.05

Cardinality-Constrained Randomized Assortments with Balanced Market Share

cs.GT ·2026-09-18 ·Xiaotie Deng, Hanyu Li, Chenghua Liu
similarity 0.73
Abstract

Assortment optimization asks a seller which of $n$ products to display to each customer. Under the multinomial-logit (MNL) model, a revenue-maximizing policy may concentrate most purchases on only a few products. Balanced market share (BMS) limits this disparity by requiring every product to receive either zero aggregate sales or at least an $α$-fraction of the largest product's sales. We study randomized BMS under a per-assortment cardinality constraint: every displayed assortment contains at most $K$ products, although the seller may rotate a larger catalog across customers. This couples per-realization feasibility with aggregate balance over an exponential policy space. We resolve the model on all three algorithmic fronts. First, reweighting assortments by their MNL denominators turns the cardinality restriction into a single uniform-matroid rank inequality, yielding an exact compact sales-space formulation in which every feasible sales vector can be implemented by a policy supported on $O(n)$ assortments. Second, deciding whether there exists a feasible policy attaining a given revenue target is NP-complete even for $α=1$ and $K=2$, whereas optimization is polynomial-time solvable once the set of products with positive sales is prescribed. Third, despite this hardness, BMS confines all positive sales to one multiplicative band, and a geometric scale search combined with a standard multiple-choice-knapsack dynamic program yields an FPTAS. For every $\varepsilon\in(0,1)$, it achieves at least a $(1-\varepsilon)$ fraction of the optimal expected revenue, preserves BMS and per-assortment cardinality exactly, and outputs a rational policy supported on $O(n)$ assortments.

0.19

Multi-Capacity Online Assortment Optimization with Consecutive Stays under Markov Chain Choice

cs.DM ·2026-10-20 ·Hongbin Zhang, Yanzhi Li, Woonghee Tim Huh
benchmark similarity 0.70
Abstract

We study online assortment optimization under Markov chain choice and independent Bernoulli arrivals, with each period's request type known in advance. Each product may have multiple interchangeable physical copies, and each booking reserves consecutive service slots on a single copy. Customers choose among products, while the platform assigns purchases to feasible copies. We develop a sales-based relaxation that upper-bounds the optimal online revenue and use it to design a policy with two components: independent sampling and purchase--update coupling. We generate independent copy proposals and make a product eligible whenever at least one of its copies proposes. A general revenue-extraction bound for random candidate sets with independent product inclusions shows that optimizing over eligible products recovers at least half of each period's relaxation revenue benchmark in expectation. A purchase--update coupling reproduces the interval flows through independent virtual copy updates while preserving physical feasibility. Under general Markov chain choice, the policy uses a random gate to make the coupling feasible: it offers the selected assortment with probability \(1-1/e\) and the empty assortment otherwise. No gate is needed under multinomial logit (MNL) choice. The resulting policies achieve approximation ratios of \((1-1/e)/2\) and \(1/2\), respectively, relative to the optimal nonanticipative online policy, independently of product capacities. In the single-copy MNL setting, our policy improves the guarantee of \citet{huwu2026} from \(0.271\) to \(1/2\) under the same arrival convention. The \(1/2\) static extraction factor and the \(1-1/e\) uniform scalar-gate factor are separately sharp, and the \(1/2\) MNL guarantee is tight for the proposed policy.

0.06

Assortment optimization under the perception-adjusted Luce model

cs.GT math.OC ·2026-10-22 ·Gerardo Berbeglia, Mashbat Suzuki, Matthew Tam
theory similarity 0.70
Abstract · 17 pages, 1 figure

The Perception-Adjusted Luce Model (PALM) introduced by by Echenique et al. (2018) is a sequential choice model that can accommodate violations of regularity and choice overload, behaviors not captured by the utility-maximization framework. Flores et al. (2019) studied the assortment problem under the PALM and proved that, for the case of two levels, there is always an optimal solution that is revenue-ordered by level. They also conjectured that revenue-ordered by levels remain optimal for the general PALM with any number of levels. We resolve this question in the affirmative by showing that every PALM instance admits an optimal assortment that includes, within each level, all products at or above a level-specific revenue threshold. The proof involves first showing how the conjecture which deals with a discrete optimization problem, can be reduced to proving certain property of a related continuous optimization problem. Specifically, we study a continuous refinement of the assortment decision under the same PALM choice rule. Although the refinement permits partial utility selections, we prove it always has an optimum that selects complete revenue tiers. This allows us to show that the assortment problem is polynomial-time solvable when the number of levels is fixed.

0.10

Diffusion-Based Data-Driven Assortment Optimization

cs.LG ·2026-08-11 ·Junyi Liao, Xiaohui Jiang, Zhengwei Tong, Ethan X. Fang, Vahid Tarokh
similarity 0.69
Abstract

Assortment optimization is a fundamental problem in revenue management, typically addressed using parametric choice models such as the multinomial logit (MNL) and its variants. While these models enable tractable formulations, their performance is sensitive to model misspecification and often struggles to capture complex customer behavior. In this paper, we propose a model-agnostic framework for assortment optimization based on guided discrete diffusion. We represent assortments as binary vectors and perform stochastic search via a learned reverse diffusion process, avoiding explicit combinatorial enumeration. To incorporate decision objectives, we introduce a reward-guided mechanism that biases local transitions using estimates of expected revenue. This allows the method to effectively balance exploration and exploitation during generation. Empirically, we show that the proposed approach consistently identifies high-quality assortments and remains robust under model misspecification, often recovering near-optimal solutions in high-dimensional settings. Moreover, the generative nature of diffusion enables the production of diverse high-performing assortments, offering flexibility beyond a single deterministic solution. These results highlight the potential of generative modeling as a scalable and robust paradigm for combinatorial optimization in data-driven decision-making.

0.04

AI-Mediation in Retail Markets: Revenue Effects and Assortment Optimization

cs.AI econ.GNmath.OC ·2026-10-09 ·Omar El Housni, Marouane Ibn Brahim
dataset similarity 0.67
Abstract

AI shopping assistants increasingly influence which products consumers consider. We study retail assortment planning under AI mediation, where a retailer chooses a catalog, an AI intermediary forms a customer-facing shortlist, and the customer chooses from that shortlist according to a multinomial logit model. We consider both deterministic mediation, in which the AI follows a fixed segment-specific ranking, and stochastic mediation based on the Plackett-Luce model. Empirically, we construct a dataset of product rankings from leading AI models, estimate Plackett-Luce ranking models, and evaluate their predictive performance on held-out assortments. Combining these estimates with synthetic customer preferences, we find that accounting for AI mediation can materially change optimal assortments and revenue. Across the tested capacity configurations, ignoring mediation yields mean revenue losses between 2.52% and 11.37% relative to the PL optimum. A much simpler deterministic plug-in, based only on the ordering of fitted AI utilities, performs substantially better, with mean losses of at most 0.53%. Motivated by this performance, we study assortment optimization under deterministic mediation. We characterize its computational complexity and show that, for any fixed number of customer segments, the problem admits a fully polynomial-time approximation scheme.

0.32

Assortment Optimization under the Mallows Model: Independent-Utility Choice Equivalence and Its Algorithmic Implications

cs.GT cs.DS ·2026-10-09 ·Danny Segev
similarity 0.65
Abstract

The Mallows model is a well-established construct in preference modeling, describing random rankings through their Kendall-Tau distance from a reference permutation. Its compact parameterization and interpretable treatment of preference uncertainty have made it influential across statistics, machine learning, probability, and revenue management. In the latter domain, recent literature has studied the embedding of Mallows-driven choice into assortment optimization. Early approximation schemes in this context require stylized structural simplifications or restrictive parametric assumptions. In the absence of these levers, a highly involved quasi-polynomial-time approximation scheme has subsequently been proposed, leaving wide open the question of whether near-optimal assortments can be computed in true polynomial time. The main contribution of this focused technical paper resides in closing these gaps by uncovering a striking independent-utility structure within Mallows choices, and turning this representation into a polynomial-time approximation scheme. Our central structural characterization explicitly constructs a single collection of mutually independent utilities, reproducing Mallows choice probabilities simultaneously for all offered sets. This exact choice equivalence connects pending Mallows-related challenges to the recent approximation framework of Bowers et al. (FOCS 2025) for assortment optimization under independent random utilities. We make this connection algorithmically feasible through a finite-support reduction that produces distributions of polynomial size while controlling revenue loss uniformly over all assortments. Fused together, these ingredients lead to an $O(n^{\tilde{O}(1/ε^2)})$-time approximation scheme for assortment optimization under the Mallows model, while allowing arbitrary product prices, concentration parameters, and modal rankings.

0.28

The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-Wise

cs.GT cs.LG ·2026-11-07 ·Yan Dai, Tao Lin, Aleksandrs Slivkins
position similarity 0.64
Abstract

We study the dynamic pricing problem, where a firm sells a product to $T$ myopic customers and their values are independent samples from an unknown value distribution $F$. With posted prices, the firm only sees whether each customer buys, and the minimax regret is $\widetilde Θ(T^{2/3})$ [KL03]. A menu instead offers several options, each selling the product with some probability at some expected payment. Infinitely many menu options allow the seller to fully reveal customer values, reducing the regret to $Θ(\sqrt T)$. How many options are needed? Perhaps surprisingly, a second menu option suffices, achieving the same regret as infinite menus (up to $\log$ factors). This holds broadly: without knowing any property of $F$, our algorithm with two menu options attains $\tilde O(\sqrt T)$ regret in general, $\tilde O(T^{1/3})$ regret for monotone-hazard-rate distributions, and $\tilde O(T^{d/(d+1)})$ instance-dependent regret when $d\in(0,1)$ is a suitable notion of "dimension". All are optimal even with infinite menus. Moreover, we argue, via a novel lower-bound construction, that our algorithm is near-optimal for each problem instance. Along the way, we study the query complexity of revenue maximization, where an algorithm issues a query to each customer to learn the property of interest (either the best price or the CDF) up to some precision. We show that interval queries suffice to achieve the same query complexity as value queries (up to $\log$ factors) for both properties and across several classes of value distributions. We provide a new interval-query algorithm for each property. The best-price-estimation algorithm is the key ingredient in our main dynamic pricing algorithm, and the CDF-estimation algorithm underpins a simpler algorithm attaining $\tilde O(\sqrt T)$ regret with three menu options.

0.26