Research map / Bandits and online learning / Online convex optimization and games
Online Allocation with Unknown Shared Supply
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the Online Shared Supply Allocation (OSSA) problem and a deterministic threshold-proportional policy GPA achieving a 4/3-approximation plus an additive term, with matching lower bounds and a learning-augmented extension LA-GPA.
Problem
Preposition a finite, unknown shared supply across multiple sites facing sequential online demand with lost-sales penalties and fixed-charge transportation costs, where the global supply is revealed only upon exhaustion.
Approach
A deterministic threshold-proportional replenishment policy (GPA) that maintains per-site safety stock and caps cumulative resupply at a site-specific fraction of observed demand, with full-truck shipments; a prediction-guided variant sets thresholds from forecasts of supply and demand with a distrust parameter lambda.
Key results
- GPA achieves a 4/3-approximation to the offline optimum up to an additive term independent of total supply s.
- Matching lower bounds: 4/3 ratio is tight and improving the additive term beyond Omega(sp epsilon) is impossible for ratio 4/3 - epsilon.
- LA-GPA(lambda) gives robustness 1 + (1-lambda)^2/(4 lambda) and consistency 1 + lambda plus 3 eta p additive.
Surprising findings
- Knowing total supply upfront does not help: an adversary can prepend unknown demand, reducing to the unknown-supply setting.
Limitations
- Single hub and single commodity; multi-echelon or multi-commodity settings left open.
- Additive error term depends on sitewise constants and is not vanishing for small instances.
- Fixed distrust hyperparameter lambda rather than adaptive advice validation.
Experimental setup
Datasets: real-world taxi dataset
Benchmarks: synthetic OSSA instances taxi-demand OSSA instances
Metrics: cost ratio to offline optimum
Baselines: natural inventory heuristics
Builds on: one-warehouse multi-retailer joint replenishment problem Adwords learning-augmented algorithms with predictions
Closest papers by meaning
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.86)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · similarity 0.84)
- Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets (NeurIPS 2026 · similarity 0.84)
- Online Resource Allocation with Non-Stationary Customers (ICML 2024 · similarity 0.83)
- Promoting External and Internal Equities Under Ex-Ante/Ex-Post Metrics in Online Resource Allocation (ICML 2024 · similarity 0.83)
- Adaptive Market Making with Inventory Constraints via Online Learning (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.