Regularized Online Allocation Problems: Fairness and Beyond

Santiago R. Balseiro (), Haihao Lu () and Vahab Mirrokni ()
Additional contact information
Santiago R. Balseiro: Columbia Business School and Google Research, Columbia University, New York, New York 10027
Haihao Lu: MIT Sloan School of Management, MIT, Cambridge, Massachusetts 02139
Vahab Mirrokni: Google Research, New York, New York 10011

Manufacturing & Service Operations Management, 2025, vol. 27, issue 3, 720-735

Abstract: 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.

Keywords: online allocation; fairness; regret analysis; regularization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/msom.2022.0212 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormsom:v:27:y:2025:i:3:p:720-735

Access Statistics for this article

More articles in Manufacturing & Service Operations Management from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().