Online Allocation with Unknown Shared Supply

Authors: Tzeh Yuan Neoh, Davin Choo, Mengchu Yue et al.

arXiv · PDF

Summary

This paper studies how to allocate a limited, unknown supply across multiple locations before you know what the demand will be — think distributing vaccines or humanitarian supplies when you can't restock and shortages mean people go unserved. The authors propose a policy called GPA that achieves a 4/3-approximation to the best possible allocation (with an unavoidable additive error term), and they prove this ratio is tight. They also show how to incorporate imperfect forecasts (from experts or ML models) in a way that helps when the forecasts are good but doesn't hurt much when they're bad.

Main takeaways:

• Studies online allocation where you must pre-position finite supply before demand arrives, with no backlogging or restocking (irreversible stockouts)
• GPA policy achieves 4/3-approximation to optimal, which is the best possible even for randomized algorithms that know the total supply in advance
• The additive error term is also unavoidable — it's impossible to eliminate even with perfect knowledge of total supply
• Learning-augmented extension incorporates forecasts in a principled way: exploits good advice while remaining robust to bad advice
• Synthetic and real-world experiments show GPA outperforms baselines when global supply is scarce

Relevance

No connection to my persona installation or conditional behavior work — this is operations research for humanitarian logistics. Included for completeness but not relevant to language model behavior research.

Abstract

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.