Fair Online Resource Allocation

• URL: http://arxiv.org/abs/2606.18679v2
• Date: Thu, 18 Jun 2026 03:25:38 GMT
• Title: Fair Online Resource Allocation
• Abstract summary: We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling.<n>We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement.
• Score: 3.949078564650437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $Ω(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.

Related papers

• Online Generalized-mean Welfare Maximization: Achieving Near-Optimal Regret from Samples [29.8171362564092]
  We study online fair allocation of $T$ sequentially arriving items among $n$ agents with heterogeneous preferences.<n>We show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves $widetildeO (1/T)$ average regret.
  arXiv  Detail & Related papers  (2026-02-11T03:16:03Z)
• Fairness Aware Reward Optimization [78.85867531002346]
  We introduce Fairness Aware Reward Optimization (Faro), an in-processing framework that trains reward models under demographic parity, equalized odds, or counterfactual fairness constraints.<n>We provide the first theoretical analysis of reward-level fairness in LLM alignment.<n>Faro significantly reduces bias and harmful generations while maintaining or improving model quality.
  arXiv  Detail & Related papers  (2026-02-08T03:35:49Z)
• Cost Efficient Fairness Audit Under Partial Feedback [14.57835291220813]
  We study the problem of auditing the fairness of a given classifier under partial feedback.<n>We introduce a novel cost model for acquiring additional labeled data.<n>We show that our algorithms consistently outperform natural baselines by around 50% in terms of audit cost.
  arXiv  Detail & Related papers  (2025-10-04T08:38:03Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Bridging Jensen Gap for Max-Min Group Fairness Optimization in Recommendation [63.66719748453878]
  Group max-min fairness (MMF) is commonly used in fairness-aware recommender systems (RS) as an optimization objective.<n>We present an efficient and effective algorithm named FairDual, which utilizes a dual optimization technique to minimize the Jensen gap.<n>Our theoretical analysis demonstrates that FairDual can achieve a sub-linear convergence rate to the globally optimal solution.
  arXiv  Detail & Related papers  (2025-02-13T13:33:45Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences.<n>To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model.<n>Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Chasing Fairness Under Distribution Shift: A Model Weight Perturbation Approach [72.19525160912943]
  We first theoretically demonstrate the inherent connection between distribution shift, data perturbation, and model weight perturbation. We then analyze the sufficient conditions to guarantee fairness for the target dataset. Motivated by these sufficient conditions, we propose robust fairness regularization (RFR)
  arXiv  Detail & Related papers  (2023-03-06T17:19:23Z)
• Fair and Optimal Classification via Post-Processing [10.163721748735801]
  This paper provides a complete characterization of the inherent tradeoff of demographic parity on classification problems. We show that the minimum error rate achievable by randomized and attribute-aware fair classifiers is given by the optimal value of a Wasserstein-barycenter problem.
  arXiv  Detail & Related papers  (2022-11-03T00:04:04Z)
• Obtaining Dyadic Fairness by Optimal Transport [40.88844078769325]
  This paper considers obtaining fairness for link prediction tasks, which can be measured by dyadic fairness. We propose a pre-processing methodology to obtain dyadic fairness through data repairing and optimal transport. The optimal transport-based dyadic fairness algorithm is proposed for graph link prediction.
  arXiv  Detail & Related papers  (2022-02-09T15:33:59Z)
• Fairer LP-based Online Allocation [13.478067250930101]
  We consider a Linear Program (LP)-based online resource allocation problem where a decision maker accepts or rejects incoming customer requests irrevocably. We propose a fair algorithm that uses an interior-point LP solver and dynamically detects unfair resource spending. Our approach do not formulate the fairness requirement as a constrain in the optimization instance, and instead we address the problem from the perspective of algorithm design.
  arXiv  Detail & Related papers  (2021-10-27T17:45:20Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  We propose falSe COrrelation REduction (SCORE) for offline RL, a practically effective and theoretically provable algorithm. We empirically show that SCORE achieves the SoTA performance with 3.1x acceleration on various tasks in a standard benchmark (D4RL)
  arXiv  Detail & Related papers  (2021-10-24T15:34:03Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized 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.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.