CS Paper Radar

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

Hongbin Zhang, Yanzhi Li, Woonghee Tim Huh

cs.DM ·submitted 2026-10-20 05:23 UTC · v2
benchmark

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.

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

The Value of Experiments in Assortment Optimization

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

Assortment optimization under the perception-adjusted Luce model

cs.GT math.OC ·2026-10-22 ·Gerardo Berbeglia, Mashbat Suzuki, Matthew Tam
theory similarity 0.69
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

Inter-Temporal Price Constraints in Dynamic Pricing: Performance Guarantees Under Price Monotonicity and Promotion Fatigue

cs.DM math.OC ·2026-09-23 ·Weiyuan Li, Paat Rusmevichientong, Huseyin Topaloglu
similarity 0.67
Abstract · 31 pages in main text, 14 pages in appendix, 1 figure

We study dynamic pricing problems under inter-temporal price constraints. We have resources with limited capacities. At each time period, we decide which products to make available and what prices to charge for the available products. The sale probability for a product depends on its price. If we make a sale for a product, then we collect a revenue reflecting the price and consume the capacities of a combination of resources. We work with two types of inter-temporal constraints. In price monotonicity, the prices charged for a product at different time periods have to be monotone. In promotion fatigue, we can discount a product at most once over each time interval of a fixed length. Computing the optimal policy is intractable. We use fluid approximations to construct policies. Traditionally, policies from fluid approximations make randomized decisions at each time period by following an optimal solution to the fluid approximation, but such randomized decisions easily violate price monotonicity or promotion fatigue constraints. We develop policies that sample price paths according to an optimal solution to the fluid approximation, while satisfying the inter-temporal constraints. Letting $c_{\min}$ be the smallest initial capacity of a resource and $L$ be the maximum number of resources used by a product, our policies have a performance guarantee of $\max\Big\{ \frac{1}{8L}, \, \frac{1}{2} - \sqrt{\frac{\log c_{\min}}{2 \,c_{\min}}} - \frac{L}{c_{\min}}\Big\}$. Thus, under large resource capacities, our policies are guaranteed to obtain at least half of the optimal total expected revenue. The latter performance guarantee is tight in the sense that no policy can, in general, obtain more than half of the optimal objective value of the fluid approximation even under large resource capacities. We unify our approach to open the path for extensions to other inter-temporal price constraints.

0.31

Diffusion-Based Data-Driven Assortment Optimization

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

Assortment and Procurement Design in Dual-Mode Content Platforms

cs.DS ·2026-09-03 ·Garud Iyengar, Yuanzhe Ma, Jay Sethuraman
similarity 0.66
Abstract

We study assortment and procurement design for a digital content platform offering both ad-supported and subscription access. Users are heterogeneous in content preferences and ad tolerance and self-select between the two modes or an outside option. For a fixed common subscription price and ad load, the platform chooses assortment distributions specific to each user type and access mode, together with content-family-level buy-versus-rent decisions to maximize profit. Rental costs scale with realized consumption, whereas buying provides a reusable pool of titles whose cost depends on the largest induced requirement across user types and modes. We show that the resulting problem is NP-hard. We then develop a scalable approximation framework based on a candidate buy set, a relaxation of the procurement coupling, and a decomposition into linear programs with a single equality constraint. These subproblems are solved by dual bisection with cardinality-constrained assortment optimization, followed by restricted-master postprocessing to recover primal feasibility. The method yields computable optimality-gap bounds, an interpretable threshold-based procurement heuristic, and asymptotic optimality under proportional market scaling as market size and grid resolution increase. Numerical experiments show strong performance at moderate market scales and grid sizes.

0.18

Online Stochastic Allocation with Increasing Returns

cs.DS math.OC ·2026-09-28 ·Shuo Sun, Yunduan Lin
similarity 0.65
Abstract

We study online allocation with increasing returns, where an uncertain number of customers arrive sequentially and can be irrevocably assigned to any product with remaining capacity. Each assignment earns a base reward plus a bonus that is nondecreasing in the number of previous assignments to the same product. Prior work has focused primarily on fixed or diminishing returns. Under increasing returns, the central challenge is that concentrating assignments can unlock large future rewards, while a different product may be preferable if arrivals stop early. We show that classical approaches, including greedy and natural LP-based rounding algorithms, can perform arbitrarily poorly, even with homogeneous bonuses. We evaluate performance through competitive ratios relative to the hindsight offline optimum. For homogeneous bonuses, we establish a tight competitive ratio of $1/2$. For arbitrary heterogeneous bonuses, however, no online algorithm can guarantee a competitive ratio greater than $1/m$, where $m$ is the number of products. By imposing discrete concavity on the bonus functions, we limit the concentration of rewards in later assignments and restore constant guarantees. Under this structure, we develop a re-solving framework that repeatedly selects a planning horizon, constructs a feasible allocation plan from the current state, and executes its assignments in a specific order. For arbitrary arrival distributions, we design distribution-oblivious deterministic and randomized algorithms with competitive ratios of $0.2537$ and $0.3864$, respectively. For known increasing-failure-rate (IFR) arrival distributions, we exploit distributional information to obtain a deterministic $1/2$-competitive algorithm.

0.14