Online resource allocation under partially predictable demand

DOI10.1287/OPRE.2020.2017MaRDI QIDQ5003724zbMATH OpenOpenAlexFDO

Authors Dawsen Hwang, Patrick Jaillet, Vahideh H. Manshadi

Publication date 29 July 2021

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.00447

zbMATH Keywords

analysis of algorithmscompetitive analysisonline resource allocation

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: For online resource allocation problems, we propose a new demand arrival model where the sequence of arrivals contains both an adversarial component and a stochastic one. Our model requires no demand forecasting; however, due to the presence of the stochastic component, we can partially predict future demand as the sequence of arrivals unfolds. Under the proposed model, we study the problem of the online allocation of a single resource to two types of customers, and design online algorithms that outperform existing ones. Our algorithms are adjustable to the relative size of the stochastic component, and our analysis reveals that as the portion of the stochastic component grows, the loss due to making online decisions decreases. This highlights the value of (even partial) predictability in online resource allocation. We impose no conditions on how the resource capacity scales with the maximum number of customers. However, we show that using an adaptive algorithm---which makes online decisions based on observed data---is particularly beneficial when capacity scales linearly with the number of customers. Our work serves as a first step in bridging the long-standing gap between the two well-studied approaches to the design and analysis of online algorithms based on (1) adversarial models and (2) stochastic ones. Using novel algorithm design, we demonstrate that even if the arrival sequence contains an adversarial component, we can take advantage of the limited information that the data reveals to improve allocation decisions. We also study the classical secretary problem under our proposed arrival model, and we show that randomizing over multiple stopping rules may increase the probability of success.

Recommendations

• Model predictive control for dynamic resource allocation
• A stochastic algorithm for online bipartite resource allocation problems
• Near optimal online algorithms and fast approximation algorithms for resource allocation problems
• Stochastic knapsack revisited: the service level perspective
• Online resource allocation with personalized learning

Cites work

• A dynamic near-optimal algorithm for online linear programming
• A multiple-choice secretary algorithm with applications to online auctions
• AdWords and generalized online matching
• Airline Seat Allocation with Multiple Nested Fare Classes
• An analysis of bid-price controls for network revenue management
• Asymptotic Behavior of an Allocation Policy for Revenue Management
• Dynamic pricing for nonperishable products with demand learning
• Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms
• Dynamic Programming and Decision Theory
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• Model predictive control for dynamic resource allocation
• Performance of an LP-based control for revenue management with unknown demand parameters
• Primal beats dual on online packing LPs in the random-order model
• Revenue management with limited demand information
• Robust linear optimization under general norms.
• Robust optimization-methodology and applications
• Secretary Problems with Non-Uniform Arrival Order
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• The Secretary Problem and Its Extensions: A Review
• The underlying Markov decision process in the single-leg airline yield-management problem
• Toward Robust Revenue Management: Competitive Analysis of Online Booking
• Who solved the secretary problem

Cited in

(7)

• Allocation of flexible and indivisible resources with decision postponement and demand learning
• Model predictive control for dynamic resource allocation
• Online resource allocation with personalized learning
• Pricing for Online Resource Allocation: Intervals and Paths
• USING STOCHASTIC INFORMATION TO PREDICT APPLICATION BEHAVIOR ON CONTENDED RESOURCES
• A deep reinforcement learning framework for solving two-stage stochastic programs
• Online stochastic reservation systems

This page was built for publication: Online resource allocation under partially predictable demand

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5003724)