平衡资源分配公平与效率，适用于难民安置等场景。
Fair Online Resource Allocation
- 基于对偶镜面下降法，在批次内强制公平约束。
- 公平性代价为福利损失的Ω(1/γ)倍，γ为公平系数。
- 实证验证了福利与公平的权衡，适合政策制定者参考。
我们研究公平在线资源分配问题，源于难民安置和航空公司调度等应用，其中代理按顺序到达，需分配至容量有限的设施。提出一种模型，在满足资源约束和Lipschitz公平性要求下最大化整体福利，确保同一批次中相似代理获得相似期望结果。首先分析离线问题，证明最优公平分配的价值至少为最优非公平分配的Ω(1/γ)，其中γ为公平系数，从而界定了公平性代价。针对在线设置，提出基于对偶镜面下降的算法，在批次内实施公平约束并估计最优对偶变量。证明该算法相对于最优离线流基准实现次线性遗憾。最后，利用难民经济计划的真实数据验证理论结果，展示算法性能并分析福利最大化与公平性之间的权衡。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。