Online Allocation with Unknown Shared Supply

arXiv cs.AI Papers
online-allocation optimization resource-management learning-augmented-algorithms approximation-theory arxiv

Summary

This paper introduces the Online Shared Supply Allocation problem and proposes a deterministic threshold-proportional policy (GPA) that achieves a 4/3-approximation to the offline optimum. It also includes a learning-augmented extension to handle imperfect forecasts and demonstrates superior performance in synthetic and real-world experiments.

arXiv:2605.07080v1 Announce Type: new Abstract: 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.
Original Article
View Cached Full Text

Cached at: 05/11/26, 07:12 AM 

# Online Allocation with Unknown Shared Supply
Source: [https://arxiv.org/abs/2605.07080](https://arxiv.org/abs/2605.07080)
[View PDF](https://arxiv.org/pdf/2605.07080)

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

## Submission history

From: Davin Choo \[[view email](https://arxiv.org/show-email/9fc0bcfc/2605.07080)\] **\[v1\]**Fri, 8 May 2026 00:59:11 UTC \(5,184 KB\)

Similar Articles

Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

arXiv cs.LG

This paper presents a unified algorithmic framework for distributed online submodular maximization under partition matroid constraints, achieving sublinear (1-1/e)-regret guarantees for both full-information and bandit feedback. It also introduces a bounded stochastic pipage rounding scheme to ensure cumulative sampling violations remain sublinear.

Hölder Policy Optimisation

Hugging Face Daily Papers

HölderPO introduces a generalized policy optimization framework that uses the Hölder mean for token-level probability aggregation in GRPO, with a dynamic annealing schedule to balance gradient concentration and variance. The method achieves state-of-the-art results on mathematical benchmarks (54.9% average, 7.2% relative gain over GRPO) and a 93.8% success rate on ALFWorld.