Regularized Online Allocation Problems: Fairness and Beyond

Problem definition: Online allocation problems with resource constraints have a rich history in operations management. In this paper, we introduce the regularized online allocation problem, a variant that includes a nonlinear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time, and for each request, a decision-maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints. Methodology/results: We design an algorithm that is simple and fast and attains good performance with stochastic and adversarial inputs. In particular, our algorithm is asymptotically optimal under stochastic i.i.d. input models, attains a fixed competitive ratio that depends on the regularizer when the input is adversarial, and can handle a sublinear amount of non-stationarity. Furthermore, the algorithm and analysis do not require convexity or concavity of the reward function and the consumption function, which allows more model flexibility. Numerical experiments confirm the effectiveness of the proposed algorithm and of regularization in an Internet advertising application. Managerial implications: Introducing a regularizer allows decision-makers to trade off separable objectives such as the economic efficiency of an allocation with ancillary, non-separable objectives such as fairness or equity of an allocation. Our results have implications for online allocation problems across many sectors, such as Internet advertising, cloud computing, and humanitarian logistics, in which fairness and equity are key considerations for managers. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0212 .