CS Paper Radar

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

Danny Segev

cs.GT cs.DS ·submitted 2026-10-09 21:12 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

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.70
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.67
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

Diffusion-Based Data-Driven Assortment Optimization

cs.LG ·2026-08-11 ·Junyi Liao, Xiaohui Jiang, Zhengwei Tong, Ethan X. Fang, Vahid Tarokh
similarity 0.67
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

The Value of Experiments in Assortment Optimization

cs.DS math.OC ·2026-10-29 ·Mohammadreza Ahmadnejadsaein, Amine Bennouna, Omar El Housni
similarity 0.65
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.

0.17

A Constant-Factor Approximation to Multidimensional Consumer Utility

cs.GT ·2026-10-07 ·Kira Goldner, Taylor Lundy, Thodoris Tsilivis
theory similarity 0.64
Abstract · 40 pages, including appendices

Motivated by social services where consumers pay with non-transferable ordeals, we study mechanisms that maximize consumer utility for multiple unit-demand buyers and heterogeneous items whose values are drawn independently from known prior distributions. Prior work in utility maximization approximates social welfare and shows that the gap between optimal utility and social welfare is logarithmic. We resolve the question of whether simple mechanisms can guarantee a constant-factor approximation to optimal utility itself. Our mechanisms achieve a $(5.67+\varepsilon)$-approximation for general independent values, improving to $2e/(e-1)<3.164$ when values are i.i.d. Each buyer chooses their favorite option from posted item prices or free item lotteries, and contention resolution determines which buyers' requests are served; this is BIC, ex-post individually rational, and computable in polynomial time. Our main technical contribution is a general upper bound on the optimal ex-ante-constrained utility that separates the contributions captured by posted prices and free lotteries. These results establish a utility counterpart to the theory of simple, approximately revenue-optimal mechanisms.

0.49

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.63
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

Do You Have My Size In Stock? Assortment and Inventory Optimization Under the Consider-Fit-Then-Choose Choice Model

cs.DS math.OC ·2026-08-15 ·Yi-Chun Akchen, Kaan Cakiroglu, Felipe Caro, Jacob Feldman
theory similarity 0.60
Abstract

In apparel retail and other applications, when a customer's preferred size is unavailable, demand may shift to nearby sizes. This substitution creates new assortment and inventory optimization challenges by coupling product availability and demand across sizes. We introduce the consider-fit-then-choose (CFTC) model to capture such size-dependent choice behavior. Products may be offered in multiple sizes, which affect customer preferences and consideration sets through fit, measured by distance from the customer's ideal size. We study assortment optimization and show-all inventory selection, in which the retailer chooses initial inventory and subsequently offers every in-stock product. We show that assortment optimization under the CFTC model is NP-hard and develop a PTAS when customers deviate by at most $O(1)$ sizes from their ideal size. Combined with the recent black-box framework of Fu et al. (2026), this yields a nearly $0.272$-approximation for show-all inventory selection. We next exploit the specific choice dynamics of the CFTC model. By stocking only every other size, we decouple demand across stocked sizes and reduce CFTC to a special class of mixed multinomial logit models that we prove satisfies the convex chain decomposition (CCD) property of Goyal et al. (2023). For the fluid problem, we develop a polynomial-time $(1/2-ε)$-approximation under adjacent-size substitution and a mild condition on preference weights. For the stochastic problem, we establish an asymptotic $1/2$-approximation using a new coupling argument connecting the stochastic inventory process to its fluid counterpart. Numerical experiments calibrated using footwear data show small optimality gaps across a broad range of substitution patterns and problem settings.

0.04