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