CS Paper Radar

StoBasket: Joint Upsell and Cross-Sell Optimization for Contribution Margin

Xin Heng

cs.AI ·submitted 2026-10-16 00:19 UTC · v1
unusual

Abstract

Retail recommenders rank relevance, but retailers earn contribution margin: an upsell earns the margin difference over the item it replaces, whereas a cross-sell earns its full margin. We introduce joint stochastic basket editing, a formulation in which one policy selects replacement and addition offers for an existing basket, values them by expected incremental contribution margin, and couples them through displayed-offer, accepted-offer, and joint-acceptance response channels. To our knowledge, it is the first formulation in which upsell and cross-sell responses are coupled; prior separable treatments are its zero-coupling special case. In real-data-calibrated simulations on five public basket datasets, StoBasket captures essentially all attainable offer margin: within 0.5% in every default-price setting and within 0.7% when the true response lies outside its model family. Correct economic accounting is the broadest gain: margin-weighted popularity leaves up to 11% of attainable margin unrealized, and a published next-basket recommender leaves 11-52%. Joint selection adds 10.2% of attainable margin on Instacart, where premium tiers and add-ons are strongly linked. When offers pay only together, the best heuristics lose 64% while exact search stays within 0.5%. For a structured subclass, we characterize when staged policies fail and give an exact optimizer that solves every tested real basket in 0.13 ms median and at most 111 ms. Profit saturates long before prediction accuracy: a correctly structured predictor trained on 5,000 randomized sessions comes within 0.06% of perfect prediction, while a signal-free one loses 38%. The same estimates yield a decision-aware market-basket analysis whose cost does not grow with association order.

Closest papers

Nearest neighbours by meaning across the whole index.

One Basket, Many Experts: Decorrelated Re-ranking for Financial Asset Recommendation

cs.IR cs.CE ·2026-11-04 ·Ryuki Unno, Keigo Sakurai, Koshi Watanabe, Keisuke Maeda, Takahiro Ogawa +1 more
publishedhot direction similarity 0.59
Abstract · Accepted to the 7th ACM International Conference on AI in Finance (ICAIF2026)

Financial asset recommendation for retail investors is typically optimized for relevance, that is, how well a recommendation matches what each user will buy. From the service provider's point of view, the value of a recommendation also depends on portfolio performance: the risk-adjusted return the recommended assets (the basket) deliver, which drives user engagement and fee revenue. The two goals are rarely achieved jointly, because the recommendations that best match user behavior concentrate on a few popular assets whose returns are highly correlated, which caps the risk-adjusted return a provider can offer. We propose Decorrelated-Satellite Expert Re-ranking (\textbf{DSER}), which retains the most relevant recommendations from an expert-following list and replaces the rest with return-decorrelated alternatives. The number of replaced slots is a single integer~$m$ (a knob) that the provider sets, so the relevance--performance trade-off becomes an explicit, auditable choice rather than a property hidden inside a learned model. In experiments on the public FAR-Trans retail-brokerage dataset, under the primary protocol, replacing a few slots improves risk-adjusted return at a small relevance cost, and the gain survives realistic trading costs at typical retail portfolio sizes. Minimizing correlation would lower basket volatility, but in our data the least-correlated assets are more volatile and higher-return, so their volatility offsets that reduction while their return drives the gain, not lower volatility. The resulting trade-off is asymmetric, with the relevance cost consistent across market phases while the gain is phase-dependent. The provider sets $m$ to read off exactly how much relevance each operating point costs.

0.44

A Constant-Factor Approximation to Multidimensional Consumer Utility

cs.GT ·2026-10-07 ·Kira Goldner, Taylor Lundy, Thodoris Tsilivis
theory similarity 0.55
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

Demand Transfer Estimation at Scale via Restricted Logit Modeling

cs.LG cs.AI ·2026-08-13 ·Lakshya Garg, Deep Narayan Mishra, Swapnil Yadav, Haoan Wang, Sujal Alugubelli +2 more
published similarity 0.55
Abstract · 8 pages. Accepted in the Main Conference of IEEE ICMLA 2026

Item demand forecasting is an integral component of store assortment optimization. Existing literature focuses on learning a suitable customer choice model and using this model to determine the value of an objective function (i.e. expected demand) with respect to an assortment proposal. However, for large item universe with many categories, this approach can prove inefficient, needing a separate demand forecast for every possible item assortment. An alternate approach exists whereby we combine the efficiency of forecasting item demand independently, while at the same time applying adjustments to the independent forecasts that account for the relations between item demand and the availability of other similar items on the shelf. Central to this approach is the estimation of Demand Transfer (DT) coefficients. These DT coefficients represent the percent of a particular target item's (item that the customer walked in the store to buy) demand that is redirected to each other item in the universe should the target item be removed from the shelf. We introduce an approach that allows us to compute these DT coefficients on large item universes (assortments having 1 million+ items). Experiments on data as well as historical transaction data for multiple locations within categories demonstrate that when certain reasonable assumptions about substitution behavior are satisfied, our procedure is able to accurately estimate underlying DT coefficients and lead to improvements in demand forecasting.

0.23

Better Capturing Interactions Between Products in~Retail: Revisited Negative Sampling for~Basket Choice Modeling

cs.LG cs.AI ·2026-10-13 ·Jules Désir, Vincent Auriau, Martin Možina, Emmanuel Malherbe
published similarity 0.55
Abstract

Brick-and-mortar retailers face many different challenges that involve understanding thoroughly its products catalog and customer preferences. In particular, assortment optimization - proposing the ideal mix of products - and promotion planning hold a pivotal role in their strategy. By leveraging sales data, retailers can make informed decisions on which products to sell and how to manage inventory, based on customer preferences as well as regional and seasonal trends. It is especially crucial to capture interactions between products, in order to minimize the number of items that cannibalize each other's sales and to ensure that complementary products, which are often purchased together, are conjointly available and sold across all stores. In this paper, we propose a model of shopping basket that learns embeddings to represent interactions between products, prices and stores. Our model is built to uncover sales patterns from very large transaction datasets. In particular, the optimization loss is computed with random negative samples in order to overcome the computational bottlenecks that arise with large number of items. Our experiments on synthetic data show the efficiency of drawing such negative samples based on the actual assortment of available products, with better results than approaches from the literature. We also validate our approach by training and evaluating our model on a dataset composed of millions of transactions from Fortenova Group, one of the leading retail company in Southeast Europe. Our model showcases promising applications in the sector of retail, with enriched interfaces to efficiently support category managers.

0.32

ComboShoppingBench: Evaluating LLM Agents for Budget-Constrained Basket Shopping with Coupons

cs.AI cs.CL ·2026-08-10 ·Adrian Li, Kelong Mao, Yudong Guo, Heming Xia, Xinwei Yang +5 more
benchmark similarity 0.54
Abstract

Real-world shopping often requires constructing a basket of complementary items rather than retrieving a single product. Such combo-shopping tasks arise in device setup, meal preparation, event planning, and group takeout ordering, requiring joint reasoning about item compatibility, availability, store-level requirements, delivery fees, coupons, and budgets. Evaluation is challenging because multiple baskets may satisfy the same request, making exact-match metrics unsuitable, whereas semantic evaluation alone cannot detect infeasible orders, invalid coupon combinations, or incorrect payments. We introduce ComboShoppingBench, an agentic shopping benchmark for open-ended yet verifiable basket construction in a simulated commerce and takeout environment. During task synthesis, an exploration agent constructs a feasible and semantically coherent basket of purchasable products; this witness guides the generation of coupons, budget constraints, user queries, and aligned evaluation rubrics. During evaluation, LLM judges assess semantic satisfaction, response quality, and claim faithfulness, while deterministic validation checks product-ID validity, budget compliance, and coupon optimality. Experiments with diverse LLM agents demonstrate that even strong agents struggle on ComboShoppingBench, highlighting substantial room for improvement in reliable, constraint-aware combo shopping.

0.38

Efficient Conformal Calibration for Paired Recommendation Decisions

cs.LG ·2026-10-31 ·Xinyu Qiao, Yichen Lin, Zhewen Chen, Xue Wang, Tao Yao
similarity 0.54
Abstract

Risk control can suppress useful changes to a frozen recommendation rule. We study how to recover valid activation from the same observed fractional losses. Two specified internal calibrators can lose efficiency by compressing losses into their sum or clipping auxiliary inverse counts before averaging. We propose Averaged Conformal Risk Calibration, or ACRC, which averages before clipping. A product identity proves expected-risk validity, while pointwise bounds characterize the additional activation. For fixed populations sampled without replacement, we connect activation to signed utility under heterogeneous users and switching constraints. Near the budgets, positive population mean gain and the stated nondegeneracy conditions give positive leading-order utility increments despite sampling dependence. Across six datasets, changing only calibration improves discounted net utility by $0.010226$ over raw and $0.008337$ over RB. A separately frozen Jester confirmation gives $0.011025 \pm 0.001082$ over raw with the rule and filter fixed, using a five-seed approximate 95 percent paired interval. Against information-matched SCoRE selecting risk or reward scores, the mean utility difference is $+0.015934 \pm 0.001440$. These gains use more mean realized risk within the declared budgets. Upstream failures delimit the benefit: efficient calibration releases useful modifications when the proposals themselves have value.

0.33

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

Diffusion-Based Data-Driven Assortment Optimization

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