# No-regret Algorithms for Fair Resource Allocation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 55 references that are in the map.
- First posted on arXiv 11 Mar 2023.

## Builds on (most cited first, 25 of 25)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Online Nash Social Welfare Maximization with Predictions](https://mlsanity.com/paper/2008.03564/) (2020)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Enabling Long-term Fairness in Dynamic Resource Allocation](https://mlsanity.com/paper/2208.05898/) (2022)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Group fairness in dynamic refugee assignment](https://mlsanity.com/paper/2301.10642/) (2023)
- [Online Dating Recommendations: Matching Markets and Learning Preferences](https://mlsanity.com/paper/1401.8042/) (2014)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Individual Fairness in Prophet Inequalities](https://mlsanity.com/paper/2205.10302/) (2022)
- [Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches](https://mlsanity.com/paper/2011.02752/) (2020)
- [Universal Caching](https://mlsanity.com/paper/2205.04860/) (2022)

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

- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [α-Fair Contextual Bandits](https://mlsanity.com/paper/2310.14164/) (2023)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)
- [Online Multi-Class Selection with Group Fairness Guarantee](https://mlsanity.com/paper/2510.21055/) (2025)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)
- [Combinatorial Allocation Bandits with Nonlinear Arm Utility](https://mlsanity.com/paper/2603.07005/) (2026)
- [Price of Fairness in Short-Term and Long-Term Algorithmic Selections](https://mlsanity.com/paper/2605.06227/) (2026)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

We consider a fair resource allocation problem in the no-regret setting against an unrestricted adversary. The objective is to allocate resources equitably among several agents in an online fashion so that the difference of the aggregate α-fair utilities of the agents between an optimal static clairvoyant allocation and that of the online policy grows sub-linearly with time. The problem is challenging due to the non-additive nature of the α-fairness function. Previously, it was shown that no online policy can exist for this problem with a sublinear standard regret. In this paper, we propose an efficient online resource allocation policy, called Online Proportional Fair (OPF), that achieves cα-approximate sublinear regret with the approximation factor cα=(1-α)-(1-α)≤ 1.445, for 0≤ α < 1. The upper bound to the cα-regret for this problem exhibits a surprising phase transition phenomenon. The regret bound changes from a power-law to a constant at the critical exponent α=frac12. As a corollary, our result also resolves an open problem raised by Even-Dar et al. [2009] on designing an efficient no-regret policy for the online job scheduling problem in certain parameter regimes. The proof of our results introduces new algorithmic and analytical techniques, including greedy estimation of the future gradients for non-additive global reward functions and bootstrapping adaptive regret bounds, which may be of independent interest.