# Regularized Online Allocation Problems: Fairness and Beyond

arXiv: https://arxiv.org/abs/2007.00514 · HTML: https://mlsanity.com/paper/2007.00514/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

## Built on by (most cited first, 22 of 22)

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [Utility Fairness in Contextual Dynamic Pricing with Demand Learning](https://mlsanity.com/paper/2311.16528/) (2023)
- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Learning Potentials for Dynamic Matching and Application to Heart Transplantation](https://mlsanity.com/paper/2602.08878/) (2026)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Trading-off price for data quality to achieve fair online allocation](https://mlsanity.com/paper/2306.13440/) (2023)
- [Robust Allocations with Diversity Constraints](https://mlsanity.com/paper/2109.15015/) (2021)
- [Online Allocation and Learning in the Presence of Strategic Agents](https://mlsanity.com/paper/2209.12112/) (2022)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Seller-side Outcome Fairness in Online Marketplaces](https://mlsanity.com/paper/2312.03253/) (2023)
- [Online Fair Allocation of Perishable Resources](https://mlsanity.com/paper/2406.02402/) (2024)
- [Binary-Integer-Programming Based Algorithm for Expert Load Balancing in Mixture-of-Experts Models](https://mlsanity.com/paper/2502.15451/) (2025)
- [A Theoretical Framework for Auxiliary-Loss-Free Load Balancing of Sparse Mixture-of-Experts in Large-Scale AI Models](https://mlsanity.com/paper/2512.03915/) (2025)
- [Online Allocation Problem with Two-sided Resource Constraints](https://mlsanity.com/paper/2112.13964/) (2021)
- [Optimal Efficiency-Envy Trade-Off via Optimal Transport](https://mlsanity.com/paper/2209.15416/) (2022)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [Fair Online Resource Allocation](https://mlsanity.com/paper/2606.18679/) (2026)
- [FARE: Deep Reinforcement Learning For Fair Exposure Constrained Uncertainty Aware Financial Content Personalization](https://mlsanity.com/paper/2609.31890/) (2026)

## Abstract (arXiv)

Online allocation problems with resource constraints have a rich history in operations research. In this paper, we introduce the 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.