Upfront Commitment in Online Resource Allocation with Patient Customers

In many online platforms like ride-sharing or grocery delivery, some demand agents can wait for a short period of time for a service if they are assured of its eventual provision within an acceptable delay. We study these “partially patient” agents in the context of an online resource allocation problem, contrasting them with impatient agents who require immediate service. We utilize a relaxed notion of competitive ratio, known as the resource/feature augmented competitive ratio, allowing online algorithms to benefit from additional features not available to the optimal offline algorithm. We introduce a class of polytope-based resource allocation (POLYRA) algorithms that achieve optimal or near-optimal competitive ratios by consulting specific polytopes and maintaining feasible algorithm states within these polytopes. For two or three types of agents, these algorithms can achieve the optimal competitive ratio. For more than three types, we present a near-optimal nested POLYRA algorithm that secures at least 80% of the optimal ratio. Our theoretical findings are supported by numerical analysis, highlighting the efficiency of our algorithms beyond adversarial arrivals and the modified competitive ratio framework.

This paper was accepted by Chung Piaw Teo, optimization and decision analytics.

Supplemental Material: The online appendices and data files are available at https://doi.org/10.1287/mnsc.2022.03335.