Fair Online Resource Allocation

A new study tackles fair online resource allocation, a problem with direct applications in refugee resettlement and airline scheduling, by introducing a model that balances overall welfare with a formal fairness requirement [1]. The research, posted to arXiv on June 17, 2026, addresses scenarios where agents arrive sequentially and must be assigned to facilities with limited capacities [1]. The model enforces a Lipschitz fairness constraint, which ensures that similar agents arriving in the same batch receive similar expected outcomes [1]. The authors first analyze the offline version of the problem and prove that the optimal fair allocation achieves at least an Ω(1/γ) fraction of the optimal unfair allocation, where γ is the fairness coefficient, thereby bounding what they term the price of fairness [1]. For the online setting, the team proposes an algorithm built on dual mirror descent [1]. The approach adapts the standard dual descent framework by enforcing Lipschitz fairness constraints within the primal allocation step for each batch [5]. By estimating optimal dual variables, or shadow prices, over time, the algorithm achieves sublinear regret relative to the optimal offline fluid benchmark [1]. The method is validated using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and the trade-offs between welfare maximization and fairness enforcement [1]. Resource allocation under uncertainty is a central challenge in operations research, where efficiency-focused methods often underserve marginalized populations [3]. A related line of work studies the Fair Online Resource Allocation with Indivisible Units problem, which adopts a fairness criterion based on the expected filling ratio to balance each group's expected allocation against its expected demand and priority weight [3]. That research finds that partial fulfillment is a necessary condition for attaining optimal fairness in online indivisible resource allocation [3]. Another recent contribution shows that a simple randomized bidding strategy in repeated first-price auctions with artificial currencies can guarantee each agent a 2 − √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids [4]. Broader frameworks for fair division continue to emerge. The Boltzmann Fair Division model, inspired by the Boltzmann distribution in statistical mechanics, allocates resources probabilistically based on a distribution potential that integrates human factors such as contribution, need, and preference [10]. The new arXiv study contributes to this growing body of work by providing an algorithm with provable guarantees for settings where fairness must be enforced within each batch of arriving agents [1].