retail pricing teams

Abstract: I study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. I propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, I show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, I extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, I introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and I prove that it restores asymptotic optimality with a strict polynomial convergence rate.

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.

Abstract: 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.