CS Paper Radar

Online Stochastic Allocation with Increasing Returns

Shuo Sun, Yunduan Lin

cs.DS math.OC ·submitted 2026-09-28 02:00 UTC · v2

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.

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

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

cs.LG math.OC ·2026-08-11 ·Zhen Xu
similarity 0.68
Abstract

We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of $O(\frac{(\ln T)^3}{T})$ where $T$ is the horizon length. Our bound significantly reduces the $O(\frac{1}{\sqrt{T}})$ bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.

0.34

Online Fair Division under an Oblivious Adversary

cs.GT ·2026-09-23 ·Saar Cohen, Nicholas Teh, Michael Wooldridge
benchmarkhighly cited similarity 0.68
Abstract

We study online fair division, where indivisible goods arrive one at a time and must be allocated immediately and irrevocably among $n\ge2$ agents. Against an oblivious adversary that fixes the input in advance, we ask what fairness guarantees randomized online algorithms can achieve. We present the Deficit Allocation (DA) algorithm, which improves the previously known high-probability approximation to PROP1 from inverse-logarithmic to inverse-doubly-logarithmic in $n/δ$, where $δ$ is the failure probability. DA does not require $δ$ as input. With probability at least $1-δ$, a refined variant achieves an arbitrarily close approximation to proportionality when no single item is too valuable relative to an agent's proportional share; without any restriction on item values, it obtains an arbitrarily close approximation to PROP$k$ for $k$ doubly logarithmic in $n/δ$. For $n2^{-2n}\leδ\le1/2$, our bounds on the approximation factor and $k$ are asymptotically tight for the stronger fractional benchmark that divides each item equally among the agents who value it positively. We also prove that algorithms that use only which agents value each item positively, but not by how much, cannot improve upon the logarithmic dependence of uniformly random allocation. However, other fairness notions admit weaker guarantees. For EF1, every randomized online algorithm has an input on which any positive approximation succeeds with probability at most $e^{-Ω(n)}$. For EFX, this probability is at most $1/n!$ with only $n+1$ items, tight within a factor of $(n+1)/2$; for MMS, it can be at most $5/6$. Finally, allocating each item uniformly among the agents who value it positively gives, with probability at least $1-δ$, an arbitrarily close approximation to EF$k$ for $k$ logarithmic in $n/δ$, and this dependence is necessary for this rule.

0.28

Online Resource Allocation with Replenishable Budgets

cs.GT ·2026-09-28 ·Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Alberto Marchesi
similarity 0.67
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.66
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

Online Fair Division: Pushing the Frontier of Approximate Proportionality

cs.GT ·2026-09-12 ·Yingjian Du, Ankang Sun
theoryhighly cited similarity 0.66
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

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

cs.GT ·2026-09-18 ·Haoxin Sang, Bo Sun, Xiaoqi Tan
published similarity 0.66
Abstract · Accepted at WINE 2026

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.

0.36

MMS Allocation for Chores with Online Agent Arrivals

cs.GT ·2026-09-10 ·Haolong Li, Zehan Lin, Huahua Miao, Xiaowei Wu
theory similarity 0.65
Abstract

We study the fair allocation of $m$ indivisible chores to $n$ agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed of her cost function and must irrevocably assign her a set of chores. We focus on the Maximin Share (MMS) fairness notion and aim to compute an allocation in which all items are assigned, and no agent incurs a cost more than $α$ times her MMS. Without any prior information about the instance (other than $n$ and $m$), we design an algorithm with a competitive ratio of $O(\min\{n, k\log^{1+ε}k, \log m\})$ for any constant $ε> 0$, where $k$ denotes the number of cost function types. Our bound matches the best known offline approximation guarantees for MMS under subadditive costs and is nearly optimal with respect to all three parameters: we show that even for binary additive cost functions, no online algorithm can achieve a competitive ratio of $o(\min\{n, k\log k, \log m\})$. We then consider the setting in which the $k$ cost function types are known in advance (though the realized types of arriving agents are not). For additive cost functions, we provide an algorithm with a competitive ratio of $O(\min\{\log k, \log(kn)/\log\log(kn)\})$, and show that constant-competitive algorithms do not exist for general $k$, even for the binary additive setting. For binary additive functions when $k \le n$, we propose a $3$-competitive algorithm and establish a lower bound of $2$.

0.39