  In many on-demand online platforms such as ride-sharing, grocery delivery, or
shipping, some arriving agents are patient and willing to wait a short amount
of time for the resource or service as long as there is an upfront guarantee
that service will be ultimately provided within a certain delay. Motivated by
this, we present a setting with patient and impatient agents who seek a
resource or service that replenishes periodically. Impatient agents demand the
resource immediately upon arrival while patient agents are willing to wait a
short period conditioned on an upfront commitment to receive the resource. We
study this setting under adversarial arrival models using a relaxed notion of
competitive ratio. We present a class of POLYtope-based Resource Allocation
(POLYRA) algorithms that achieve optimal or near-optimal competitive ratios.
Such POLYRA algorithms work by consulting a particular polytope and only making
decisions that guarantee the algorithm's state remains feasible in this
polytope. When the number of agent types is either two or three, POLYRA
algorithms can obtain the optimal competitive ratio. To design these polytopes,
we construct an upper bound on the competitive ratio of any algorithm, which is
characterized via a linear program (LP) that considers a collection of
overlapping worst-case input sequences. Our designed POLYRA algorithms then
mimic the optimal solution of this upper bound LP via its polytope's
definition, obtaining the optimal competitive ratio. When there are more than
three types, our overlapping worst-case input sequences do not necessarily
result in an attainable competitive ratio, and so we present a class of simple
and interpretable POLYRA algorithm which achieves at least 80% of the optimal
competitive ratio. We complement our theoretical studies with numerical
analysis which shows the efficiency of our algorithms beyond adversarial
arrivals
