# Online Allocation with Unknown Shared Supply

arXiv: https://arxiv.org/abs/2605.07080 · HTML: https://mlsanity.com/paper/2605.07080/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 14 of 14)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Online Computation with Untrusted Advice](https://mlsanity.com/paper/1905.05655/) (2019)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [Better Approximation Bounds for the Joint Replenishment Problem](https://mlsanity.com/paper/1307.2531/) (2013)
- [Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs](https://mlsanity.com/paper/2410.18535/) (2024)
- [Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs](https://mlsanity.com/paper/2507.16096/) (2025)
- [Product distribution learning with imperfect advice](https://mlsanity.com/paper/2511.10366/) (2025)

## Abstract (arXiv)

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.