Online Allocation with Unknown Shared Supply

2026-05-11 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, quick

Summary

This paper introduces the Online Shared Supply Allocation (OSSA) problem, a stateful online model for resource allocation in scenarios like humanitarian logistics and vaccine distribution, where a central hub distributes an unknown, finite supply to multiple sites facing sequential demand, incurring fixed-charge transportation costs and lost-sales penalties without backlogging. The authors propose GPA, a deterministic threshold-proportional policy, proving it achieves a 4/3-approximation to the offline optimum, with matching lower bounds confirming this ratio's tightness and the unavoidable additive-error dependence. Furthermore, a learning-augmented extension of GPA is developed to leverage imperfect forecasts from human experts or ML models, demonstrating superior performance over natural baselines in synthetic and real-world experiments, especially when global supply is scarce.

Key takeaway

This paper introduces the Online Shared Supply Allocation (OSSA) problem for pre-positioning unknown, finite supply across multiple sites facing sequential demand, critical for humanitarian logistics and vaccine distribution. The proposed GPA policy achieves a tight 4/3-approximation to the offline optimum and includes a learning-augmented extension that robustly integrates imperfect forecasts. GPA significantly outperforms baseline methods in scenarios with scarce global supply, offering a practical solution for critical resource allocation challenges.

Topics

• Online Shared Supply Allocation
• Resource Allocation
• Approximation Algorithms
• Learning-Augmented Algorithms
• Humanitarian Logistics

Best for: AI Scientist, Research Scientist, AI Engineer

Related on AIssential

• Batched Single-Index Global Multi-Armed Bandits with Covariates — BIDS is a novel batched multi-armed bandit algorithm that uses single-index regression to efficiently manage covariates and related arm rewards.
• Adaptive mine planning under geological uncertainty: A POMDP framework for sequential decision-making — Sequential belief updating transforms geological uncertainty into an active component of value creation in mine planning.
• Generative Frontier Planning for Adaptive Peer-Referral Recruitment under Covariate-Dependent Arrivals — GFP optimizes peer-referral recruitment by modeling referrer-dependent covariates and capacity, enabling efficient, adaptive resource allocation.
• In-Context Learning for Data-Driven Censored Inventory Control — ICGPS uses generative models and in-context learning to improve inventory control under censored demand.
• The Limits of AI-Driven Allocation: Optimal Screening under Aleatoric Uncertainty — Optimal resource allocation combines algorithmic targeting with strategic screening to mitigate irreducible aleatoric uncertainty.
• On-Policy Approximate Control Methods — Function approximation extends Sarsa and n-step Sarsa to large-scale reinforcement learning control problems.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.