When Should you Offer an Upgrade: Online Upgrading Mechanisms for Resource Allocation

In this work, we study an upgrading scheme for online resource allocation problems. We consider a setting with sequentially arriving resource requests, which the decision-maker has to accept or reject. The resources are ordered according to their values. If the decision-maker accepts the request, they offer an upgrade-fora-fee to the next more valuable resource. The fee is dynamically adjusted based on the currently available resources. After the upgrade-for-a-fee option is presented to the requester, they can either accept it and get the upgrade by paying the additional fee, or reject it and maintain their originally allocated resource. We take the decision-maker’s perspective to design upgrading mechanisms simultaneously maximizing revenue and minimizing underutilization of resources. Both objectives are encapsulated in a concept termed regret, which is used to measure the algorithm performance. We present a fast algorithm that achieves O(log T) regret. Furthermore, our computational experiments with data similar to those observed in the hospitality industry showed that the proposed upgrading mechanism could increase the annual revenue by over 17%.