Online Resource Allocation with Unknown Demand: Bounded Regret and Fair Algorithm

We study the online resource allocation problem where the decision-maker aims to maximize the total reward subject to budget constraints on multiple types of resources over a finite horizon. At each time, the reward and resource consumption of the arriving order is revealed, and the decision-maker needs to accept or reject the order. We consider a stochastic setting where the reward and resource consumption of arriving orders follow an i.i.d. distribution with finite support. Without the knowledge of distribution parameters, we propose an adaptive LP(Linear Program)-based algorithm and show that the regret, defined as the performance gap between the reward of the online algorithm and the optimal reward in the offline problem, is bounded and not dependent on the length of time horizon. The algorithm also features a fair allocation rule in two aspects: (i) fairness across time and (ii) individual fairness. In (i), we require that the treatment of the same type of order is fair relative to the past and future; In (ii), we require that similar orders should be treated similarly. To achieve these criteria, we identify the offline fair solution that is fair across order types, and define cumulative unfairness as the cumulative distance from the online allocation rule to the offline fair solution. We ensure fairness by showing that the cumulative unfairness has a logarithmic upper bound with respect to time horizon.

Share this Event