我们研究了公正在线资源分配的问题，主要应用于难民安置和航空公司调度等场景。在这些场景中，代理人依次到达并必须分配到有限容量的设施。我们提出了一种模型，旨在最大化总体福利，同时遵循资源约束和Lipschitz公平性要求，确保在同一批次到达的相似代理人获得相似的预期结果。
首先，我们分析了离线问题，证明了最优公正分配的价值至少是最优不公正分配的 $\Omega(1/\gamma)$ 倍，其中 $\gamma$ 是公平系数，从而界定了公平的代价。
在在线设置中，我们提出了一种基于对偶镜像下降的算法，该算法在批次内强制执行公平性约束，同时估计最优对偶变量。我们证明该算法相对于最优离线流体基准达到了次线性遗憾。
最后，我们使用来自难民经济计划的真实数据验证了理论结果，展示了算法的性能，并考察了福利最大化与公平性执行之间的权衡。
博主点评： 本文通过结合理论与实际数据，探讨了资源分配中的公平性，提供了一种新颖的算法来平衡福利与公平性，具有重要的应用前景，尤其在社会科学与运筹学交叉领域。算法的有效性和理论基础为进一步研究提供了坚实的基础。