# Fair Online Resource Allocation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 17 Jun 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Individual Fairness in Hindsight](https://mlsanity.com/paper/1812.04069/) (2018)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Fairness and Utilization in Allocating Resources with Uncertain Demand](https://mlsanity.com/paper/1906.09050/) (2019)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Group fairness in dynamic refugee assignment](https://mlsanity.com/paper/2301.10642/) (2023)
- [Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement](https://mlsanity.com/paper/2410.22992/) (2024)

## Abstract (arXiv)

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an Omega(1/γ) fraction of the optimal unfair allocation, where γ is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.