Regularized Online Allocation Problems: Fairness and Beyond
Online allocation problems with resource constraints have a rich history in operations research. In this paper, we introduce the \emph{regularized online allocation problem}, a variant that includes a non-linear 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. Our primary motivation is allowing decision makers to trade off separable objectives such as the economic efficiency of an allocation with ancillary, non-separable objectives such as the fairness or equity of an allocation. We design an algorithm that is simple, fast, and attains good performance with both stochastic i.i.d.~and adversarial inputs. In particular, our algorithm is asymptotically optimal under stochastic i.i.d. input models and attains a fixed competitive ratio that depends on the regularizer when the input is adversarial. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
DECAF: Learning to be Fair in Multi-agent Resource Allocation
A wide variety of resource allocation problems operate under resource constraints that are managed by a central arbitrator, with agents who evaluate and communicate preferences over these resources. We formulate this bro…
FairnessQ-LearningFairness-Regularized Online Optimization with Switching Costs
Fairness and action smoothness are two crucial considerations in many online optimization problems, but they have yet to be addressed simultaneously. In this paper, we study a new and challenging setting of fairness-regu…
Trading-off price for data quality to achieve fair online allocation
We consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes -- which is often unre…
FairnessFairness-Aware Secure Integrated Sensing and Communications with Fractional Programming
We propose a novel secure integrated sensing and communications (ISAC) system designed to serve multiple communication users (CUs) and targets. To that end, we formulate an optimization problem that maximizes the secrecy…
FairnessISACFractional Top Trading Cycle on the Full Preference Domain
Efficiency and fairness are two desiderata in market design. Fairness requires randomization in many environments. Observing the inadequacy of Top Trading Cycle (TTC) to incorporate randomization, Yu and Zhang (2020) pro…
Fairness