CS Paper Radar

Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs

Haoxin Sang, Bo Sun, Xiaoqi Tan

cs.GT ·submitted 2026-09-18 23:54 UTC · v2
published

Abstract

We study online allocation with convex costs (\OACC), a generalization of limited-supply models in which additional resources can be produced dynamically at convex cost. Prior work largely focuses on constructing a single algorithm that achieves strong competitive guarantees. In contrast, our main contribution is a structural characterization of the optimal design space of reserve functions (i.e., normalized pricing rules) for \OACC, yielding a family of optimal online algorithms. Using a principled dynamical-systems approach, we show that optimal online algorithms arise as solutions of a nonlinear eigenvalue problem: the optimal competitive ratio corresponds to the dominant eigenvalue, and the associated eigenfunction determines the optimal reserve function. This perspective establishes the existence of infinitely many optimal designs attaining the best possible competitive ratio, thereby unifying and generalizing a broad class of prior algorithms. Beyond unification, our characterization uncovers new structural phenomena, including the ability to flexibly mix dynamic and static pricing without loss of optimality and the construction of universally competitive algorithms under unknown or stochastic costs. We further extend the analysis to more structured settings such as supply-oblivious arrivals and hard supply constraints, obtaining sharper guarantees that improve upon previous bounds.

Comment
Accepted at WINE 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

cs.LG ·2026-10-07 ·Zhaohua Chen
benchmark similarity 0.68
Abstract

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.

0.19

Online Stochastic Allocation with Increasing Returns

cs.DS math.OC ·2026-09-28 ·Shuo Sun, Yunduan Lin
similarity 0.66
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

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

Online Resource Allocation with Replenishable Budgets

cs.GT ·2026-09-28 ·Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Alberto Marchesi
similarity 0.62
Abstract

Online Resource Allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints. Classical ORA models typically assume that resources are monotonic, meaning that selecting actions can only decrease the available budget. In this work, we study a more general setting with replenishable budgets, in which actions may either consume or replenish resources over time. This extension is necessary to capture scenarios such as inventory systems or energy markets in which capacity can be actively recovered. We develop a dual-based algorithm that recovers best-of-both-worlds guarantees for standard ORA when the replenishment factor $β= 0$, and improves them when $β> 0$. In particular, our algorithm attains $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic setting and $\widetilde{\mathcal O}(\sqrt{T})$ $α$-regret in the adversarial setting, where $α$ depends on the per-round budget and on the replenishment factor of the void action. Moreover, the algorithm ensures strict satisfaction of the budget constraints.

0.12

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

cs.LG math.OC ·2026-09-23 ·Jiameng Lyu
theory similarity 0.62
Abstract

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

0.07

Minimization Prophet Inequality with Bounded Costs

cs.DS ·2026-09-06 ·Haolong Li, Xiaowei Wu
similarity 0.61
Abstract

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $Θ(\sqrt{b})$.

0.27

Online Fair Division: Pushing the Frontier of Approximate Proportionality

cs.GT ·2026-09-12 ·Yingjian Du, Ankang Sun
theoryhighly cited similarity 0.61
Abstract · In this updated version, we add a discussion of an independent work that studies related results. We also add a new section that presents a …

Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study deterministic online allocation among $n$ agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous allocation decisions. We focus on proportionality up to one good (PROP1) and examine how advance information affects the achievable guarantees. Without additional future information, we give a deterministic algorithm that guarantees $Ω(\frac{1}{\log(nm)})$-PROP1 after every round, where $m$ is the number of goods at termination. We complement this result by showing that, for every $n$ and sufficiently large $m$, every deterministic algorithm has an adaptive instance with $m$ goods on which its allocation has PROP1 approximation guarantee $O(\frac{\log \log m}{\log m})$. Thus, when the number of agents is fixed, our upper and lower bounds on the competitive ratio differ by at most an $O(\log\log m)$ factor. These results answer an open question proposed by Choo et al. on whether a nontrivial deterministic approximation for PROP1 can be obtained. We also study the setting where the algorithm knows the predictions of the maximum item value for every agent. When the predictions are accurate, we give a deterministic $\frac{1}{2}$-PROP1 algorithm, improving the $\frac{1}{n}$ guarantee of Choo et al. to a constant. We further establish an explicit upper bound below one on the competitive ratio, even for two agents with accurate predictions. Finally, we give a single deterministic algorithm that guarantees $\frac{1}{2}$-PROP1 when predictions are accurate and $Ω(\frac{1}{\log (nm)})$-PROP1 for arbitrary predictions.

0.40

A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

cs.LG ·2026-09-05 ·Menglong Li, Jiawei Zhang
similarity 0.61
Abstract

We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with one request type, for a fluid relaxation in which resource overuse incurs a quadratic penalty. The policy achieves $O(1)$ expected additive regret relative to the hindsight optimum, with a bound independent of the horizon $T$, under a general arrival model. This model includes independent and identically distributed arrivals with unknown probabilities, independent nonstationary arrivals with known probabilities, independent nonstationary arrivals with unknown probabilities and one historical sample path, and Markov-modulated arrivals with an unknown Markov chain. The policy does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.

0.20