CS Paper Radar

Dynamic Run-Out Pricing for Perishable Goods

Farbod Ekbatani

cs.GT cs.DM ·submitted 2026-10-12 21:30 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory

cs.LG ·2026-09-26 ·Mengxiao Zhang, Yingfei Wang, Haipeng Luo
benchmarktheory similarity 0.70
Abstract

We study online dynamic pricing with censored demand, where an arbitrary inventory level is revealed before pricing and may adapt to past observations, while demand follows an unknown, price-dependent distribution that is stationary over time. For a horizon of $T$ rounds, Xu et al. [2026] achieved $\widetilde{\mathcal{O}}(\sqrt{T})$ regret under restrictive structural assumptions including linear demand, price-independent additive noise, and conditions relating inventory levels to the noise support. Our first contribution is to extend this framework to a substantially more general and statistically harder nonparametric setting, requiring only the natural assumption that expected sales are nonincreasing in price and allowing nonlinear demand curves and price-dependent noise. For this model, we first propose a simple baseline, Double-Grid-UCB, which discretizes both price and inventory and achieves $\widetilde{\mathcal{O}}(T^{3/4})$ expected regret using separate revenue estimates for each price-inventory grid pair. Then, we develop Threshold-UCB, which improves the expected regret to $\widetilde{\mathcal{O}}(T^{2/3})$. Unlike Double-Grid-UCB, Threshold-UCB reuses sales observations across inventory levels through shared estimates of demand-tail probabilities, allowing the same data to support revenue upper bounds for multiple inventories rather than a single inventory bin. We also complement this upper bound with an $Ω(T^{2/3})$ lower bound via a reduction from stochastic posted pricing, establishing its minimax optimality. Finally, extensive experiments across inventory processes, demand functions, and noise models demonstrate consistently superior performance of Threshold-UCB over benchmark algorithms.

0.23

An $O(n\log n)$ Algorithm for Uncapacitated Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Arbitrary Prices

cs.CE ·2026-11-17 ·Kleitos Papadopoulos
similarity 0.67
Abstract

We study the finite-horizon, uncapacitated single-item lot-sizing problem with no fixed setup cost, a stationary threshold $Q > 0$ for an all-units quantity discount, arbitrary time-varying regular and discounted unit prices, and nonnegative linear holding costs. Order quantities and inventories may be either continuous or integral, and neither backlogging nor free disposal is allowed. Because unit prices may rise and fall arbitrarily over time, an optimal physical schedule may engage in speculative forward buying: positive orders can occur when incoming stock already exceeds current demand, and physical inventory carried across periods can grow proportionally to total horizon demand rather than remaining bounded by a multiple of $Q$. We give an exact $O(n\log n)$-time algorithm that computes the minimum total cost with free terminal inventory, together with the optimal cost for every horizon prefix constrained to end with zero inventory, using $O(n)$ working space under unit-cost exact arithmetic. Value computation operates online in a single forward pass without lookahead. With persistent frontier snapshots and a linear-time retroactive order-aggregation pass, an optimal physical ordering schedule is recovered in $O(n\log n)$ time and $O(n\log n)$ space.

0.28

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

Unit-Demand Pricing for Min-Buying Customers

cs.GT econ.TH ·2026-10-12 ·Titing Cui, Michael Hamilton, Jourdain Lamperski, Kasra Tari
similarity 0.64
Abstract

We study the unit-demand pricing problem under \textit{min-buying} behavior, where customers purchase the lowest-priced item that yields non-negative utility. In contrast to the quasi-linear model, we show that uniform pricing becomes substantially more effective under min-buying. First, we study symmetric environments. We show that for min-buying customers with independent and identically distributed valuations, a uniform price across items is optimal. We then extend this optimality result to all valuations drawn from exchangeable and affiliated distributions. However, uniform pricing is not optimal in all symmetric environments: for min-buying customers we construct an exchangeable and non-affiliated valuation distribution for which the gap between uniform pricing and optimal item pricing is logarithmic in the number of items. This gap is tight and matches the worst-case gap in the quasi-linear setting. Next, we consider asymmetric environments in which valuations are independent but not identically distributed. When these valuations are regular and customers are min-buying, we show that a uniform price guarantees approximately 69.86\% of the optimal item-pricing revenue and this is tight. Overall, our results highlight that the value of non-uniform pricing substantially diminishes, and often disappears entirely, under more conservative demand models in which customers engage in satisficing behaviors such as min-buying.

0.16

Personalised versus Posted Pricing from Samples

cs.DS math.OC ·2026-09-23 ·Pieter Kleer, Johan van Leeuwaarden, Daan Noordenbos
published similarity 0.64
Abstract · Accepted at the 22nd Conference on Web and Internet Economics (WINE 2026)

Personalised pricing maximises expected revenue from a market but requires detailed information about individual customers. How much of this revenue can be recovered using a simple posted price based on a finite number of samples from the underlying value distribution? We answer this question by maximising the worst-case ratio between the expected revenues of posted and personalised pricing over the fundamental class of $λ$-regular value distributions. Our results reveal a structural transition as a function of $λ$. For the class of monotone hazard rate (MHR) distributions, corresponding to $λ= 0$, the sample mean is an optimal statistic: the entire sample can be compressed into its average without any loss of revenue. Beyond the MHR class, corresponding to $λ> 0$, this property disappears. We show that the sample mean is no longer optimal, revealing that optimal sample-based pricing rules become substantially more intricate. Nevertheless, we show that a remarkably simple order-statistic based pricing rule is asymptotically optimal as the number of samples $n$ grows, achieving the optimal approximation ratio up to a tight error of order $1/n$. Our analysis combines techniques from probability, approximation theory and optimization, including doubly infinite linear programming, hypergeometric functions, and combinatorial identities involving incomplete Beta functions.

0.45

Balanced Posted Prices in Stationary Two-Sided Markets

cs.GT ·2026-10-22 ·Ilan Reuven Cohen
benchmark similarity 0.63
Abstract · 30 pages

We study an intermediary that buys nonperishing items from arriving sellers and sells them to arriving buyers, subject to limited storage. Sellers and buyers arrive according to independent Poisson processes. The intermediary pays and charges the same fixed item prices, aiming to maximize long-run gains from trade: buyer value minus seller cost. Our benchmark may choose allocations directly, has unlimited storage, and must purchase each unit before allocating it. Its optimal long-run gain rate equals the value of a linear program of average purchase and allocation rates, with or without knowledge of future arrivals. For buyers whose bundle values are maxima of nonnegative additive valuations (XOS), we compute static common prices that guarantee half of this benchmark for arbitrary finite item capacities, even one storage slot per item, regardless of how ties are resolved without using future arrivals. The prices are computable in polynomial time using demand and supporting-value queries. The construction equalizes itemwise lower bounds on buyer and seller contributions to gains from trade, accounting for procurement costs. We call this contribution balance. As a single-item foundation, we also equalize the rates of purchases and sales selected by the price, before checking inventory availability. We call this rate balance. For capacity $C$, it yields the tight guarantee $C/(C+1)$. The two principles parallel proofs of the classical prophet inequality based on half the expected benchmark and on a median threshold, adapting these balancing ideas to recurring two-sided markets with limited inventory.

0.13

The Shadow Price of Intelligence: Quality Degradation in LLM Inference as a Supply Chain Problem

cs.AI math.OCcs.PF ·2026-08-25 ·Elioth Sanabria
similarity 0.63
Abstract · 28 pages, 12 figures. Numerical instances calibrated to public benchmark data for five LLM providers

Large language model providers are compute constrained, and a common response to congestion is to degrade service. A degraded answer fails with some probability, and a failed answer either returns as a retry or departs as churn, destroying LTV on an unaccounted ledger. We model inference allocation as a newsvendor whose stockout cost is churned lifetime value, a geometric retry multiplier in which the recycled product is dissatisfaction, and a two-regime transient fluid queue whose arrival rate is made endogenous by retries. Statically, there is a regime in which a cheaper model saves energy per initiated task while consuming strictly more capacity per initiated task, so the discount inverts when capacity binds. Dynamically, a reactive throttle fired during a surge can cross an ignition threshold beyond which it manufactures more traffic than it sheds, and a release rule set below the degraded equilibrium converts a transient surge into a permanent degraded regime. With heterogeneous customers, throttling is a transportation problem in retry-inflated load whose optimal policy rations intelligence by critical ratio, and whose dual, the shadow price of intelligence, prices a marginal query by class and by hour. Under congestion, throttling is not a cost lever but a demand lever.

0.26

Trading with the STARS: Algorithm Design & Spectrum of Fundamental Limits for Trading with Storage

cs.DS cs.GTmath.OCmath.PR ·2026-10-05 ·Jerry Anunrojwong, Akshit Kumar, Rachitesh Kumar
similarity 0.63
Abstract

We study an online trading problem where a trader, given a sequence of i.i.d. prices drawn from a known distribution $F$ on $[0,1]$, must make irrevocable buy, sell, or hold decisions subject to storage constraints. We investigate achievable algorithmic performance measured in terms of regret, the difference between the expected profit of the hindsight optimal policy that knows the entire price sequence and an online algorithm. We analyze finite atomic and continuous distributions characterized by their local behavior around the median which we capture using a parameter $β$. The parameter $β$ quantifies how the mass of prices accumulates around the distribution median. We identify a new driver of algorithmic performance, demonstrating that median gaps coupled with an initial inventory level of zero can force regret scaling of $Ω(T^{(β+ 1)/(2β+4)})$ --- establishing a novel spectrum of fundamental limits on algorithmic performance. We then study STARS, short for Storage Trading by Averaging Repeatedly across multiple Scenarios, which simulates possible future price scenarios to approximate the value-to-go function and make buy/sell/hold decisions. We show that STARS obtain near-optimal algorithmic performance (upto poly-logarithmic factors) across a broad range of distributions. In particular, it achieves $O(\log T)$ regret for finite atomic prices, $\widetilde{O}(T^{β/(2β+2)})$ for continuous distributions without a median gap and $\widetilde{O}(T^{(β+1)/(2β+4)})$ for continuous distributions with a median gap for $β\geq 0$.

0.26