Regularized Online Allocation Problems: Fairness and Beyond
Manufacturing & Service Operations Management · 2025-05 · 27 (3) · 720-735
DOI: 10.1287/msom.2022.0212 ↗Kurz gefasst
Fachartikel in der Zeitschrift Manufacturing & Service Operations Management, 2025-05. Verfasst von Santiago R. Balseiro und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 27 Literaturangaben.
Abstract (Originalsprache)
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 .
Zitieren
APA
Balseiro, S. R., Lu, H., & Mirrokni, V. (2025). Regularized Online Allocation Problems: Fairness and Beyond. Manufacturing & Service Operations Management, 27(3), 720-735. https://doi.org/10.1287/msom.2022.0212
Vancouver
Balseiro SR, Lu H, Mirrokni V. Regularized Online Allocation Problems: Fairness and Beyond. Manufacturing & Service Operations Management. 2025;27(3):720-735. doi:10.1287/msom.2022.0212
BibTeX
@article{Balseiro2025,
author = {Balseiro, Santiago R. and Lu, Haihao and Mirrokni, Vahab},
title = {Regularized Online Allocation Problems: Fairness and Beyond},
journal = {Manufacturing & Service Operations Management},
year = {2025},
volume = {27},
number = {3},
pages = {720--735},
doi = {10.1287/msom.2022.0212}
}
EUVIMED