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 overall welfare subject to resource constraints and a Lipschitz fairness requirement, ensuring that similar agents arriving in the same batch receive similar expected outcomes.
First, we analyze the offline problem, proving that the value of the optimal fair allocation is at least an $\Omega(1/\gamma)$ fraction of the optimal unfair allocation, where $\gamma$ is the fairness coefficient, thus 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.
Blogger's Review: This paper explores fairness in resource allocation by integrating theory and real data, offering a novel algorithm to balance welfare and fairness, with significant application prospects, especially in the intersection of social sciences and operations research. The effectiveness and theoretical foundation of the algorithm provide a solid basis for further research.