Abstract
We study how to share a single conserved capacity budget across many locations and two service classes when demand is uneven, time-varying, and can exceed supply. The shape recurs: an origin's request-rate cap split across its edge locations, a licensed throughput cap across premium and standard tenants, or an egress budget between latency-critical and batch workloads. We present a two-level algorithm. The first level redistributes capacity within a class across locations by proportional deficit and excess redistribution; the second lends capacity elastically between classes when one has surplus and the other deficit. We prove it conserves the budget exactly, preserves non-negativity, and reaches a stable allocation in one iteration under stationary demand because it carries no per-cycle state, at O(KN) cost per cycle for K classes and N locations. We evaluate it defending a CDN's per-domain budget under volumetric attack, where the classes are confirmed-legitimate and not-yet-cleared traffic; across 8 contention scenarios on a 22-location topology it serves 66-93% of high-priority demand, competitive with a single-class linear-programming optimum, while never leaving capacity idle or over-committing whenever aggregate demand meets or exceeds the budget (the contention regime these scenarios evaluate). Two findings carry beyond the application. First, a throughput-maximizing objective is wrong under contention: a two-class LP maximizing total served load serves less high-priority load than our demand-proportional, reservation-respecting allocator in most scenarios, because it cannot tell that some load it serves is the contention. Second, inter-class borrowing earns its complexity under bursty load, improving high-priority service by 1.5 points (isolated by ablation), and is neutral under stationary demand. A 5-location prototype with real HTTP traffic validates the pipeline.
Explore similar work
May 8, 2026cs.AI
Many real-world resource allocation systems, such as humanitarian logistics and vaccine distribution, must preposition limited supply across multiple locations before demand is realized while stockouts incur irreversible service losses. To study this, we introduce the Online Shared Supply Allocation (OSSA) problem, a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand under fixed-charge transportation costs and lost-sales penalties. Unlike classical make-to-stock or make-to-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand. To tackle OSSA, we propose a deterministic threshold-proportional policy GPA and prove that it achieves a
4/3-approximation to the offline optimum up to an additive term independent of the total supply. We complement this with matching lower bounds showing that the
4/3 ratio is tight and that the additive-error dependence is unavoidable, even for randomized algorithms that know the total supply upfront. Finally, we develop a learning-augmented extension to GPA that principally incorporates imperfect forecasts (e.g., from human experts or ML models) commonly available in practice, enabling us to exploit high-quality advice while being robust against arbitrary bad ones. Synthetic and real-world experiments show that GPA outperforms natural baselines with global supply is scarce.
Tzeh Yuan Neoh, Davin Choo, Mengchu Yue +1
May 12, 2026cs.AI
We study a sequential resource allocation problem motivated by adaptive network recruitment, in which a limited budget of identical resources must be allocated over multiple rounds to individuals with stochastic referral capacity. Successful referrals endogenously generate future decision opportunities while allocating additional resources to an individual exhibits diminishing returns. We first show that the single-round allocation problem admits an exact greedy solution based on marginal survival probabilities. In the multi-round setting, the resulting Bellman recursion is intractable due to the stochastic, high-dimensional evolution of the frontier. To address this, we introduce a population-level surrogate value function that depends only on the remaining budget and frontier size. This surrogate enables an exact dynamic program via truncated probability generating functions, yielding a planning algorithm with polynomial complexity in the total budget. We further analyze robustness under model misspecification, proving a multi-round error bound that decomposes into a tight single-round frontier error and a population-level transition error. Finally, we evaluate our method on real-world inspired recruitment scenarios.
Yuqi Pan, Davin Choo, Haichuan Wang +3
Jun 17, 2026cs.DS
We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an
Ω(1/γ) fraction of the optimal unfair allocation, where
γ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.
Christopher En, Yuri Faenza, Andrea Lodi +1