  In this work, we study an upgrading scheme for online resource allocation
problems. We work in a sequential setting, where at each round a request for a
resource arrives and the decision-maker has to decide whether to accept it (and
thus, offer the resource) or reject it. The resources are ordered in terms of
their value. If the decision-maker decides to accept the request, they can
offer an upgrade-for-a-fee to the next more valuable resource. This fee is
dynamically decided based on the currently available resources. After the
upgrade-for-a-fee option is presented to the requester, they can either accept
it, get upgraded, and pay the additional fee, or reject it and maintain their
originally allocated resource.
  We take the perspective of the decision-maker and wish to design upgrading
mechanisms in a way that simultaneously maximizes revenue and minimizes
underutilization of resources. Both of these desiderata are encapsulated in a
notion of regret that we define, and according to which we measure our
algorithms' performance. We present a fast algorithm that achieves O(log T)
regret. Finally, we implemented our algorithm utilizing data akin to those
observed in the hospitality industry and estimated our upgrading mechanism
would increase the annual revenue by over 17%.
