Regularized Online Allocation Problems: Fairness and Beyond

• 成果类型: Article
• 署名作者: Balseiro, Santiago R.; Lu, Haihao; Mirrokni, Vahab
• 署名单位: Columbia University; Alphabet Inc.; Google Incorporated; Columbia University; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
• 刊物名称: M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1523-4614
• DOI: 10.1287/msom.2022.0212
• 发表日期: 2025
• 关键词: online allocation; fairness; Regret Analysis; regularization

摘要

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 nonseparable 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.