Online Allocation with Unknown Shared Supply

Computer Science > Artificial Intelligence [Submitted on 8 May 2026] Online Allocation with Unknown Shared Supply Tzeh Yuan Neoh, Davin Choo, Mengchu Yue, Milind Tambe 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. Subjects: Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2605.07080 [cs.AI]   (or arXiv:2605.07080v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.07080 Focus to learn more Submission history From: Davin Choo [view email] [v1] Fri, 8 May 2026 00:59:11 UTC (5,184 KB) Access Paper: view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs cs.DS References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)