在线多类别选择中保障群体公平性，实现高效资源分配。
Online Multi-Class Selection with Group Fairness Guarantee
- 提出无损取整方案，保证整数解性能与分数解一致。
- 设计随机算法，通过预留机制实现跨类公平且不降低效率。
- 融合不可靠预测，提升实际场景中公平与效率的平衡。
我们研究具有群体公平性保障的在线多类别选择问题，需在资源有限条件下为依次到达的代理分配资源。现有研究存在两大局限：一是引入新型无损取整方案，使整数算法的期望性能与任意分数解相同；二是显式处理属于多个类别的代理带来的挑战。为此，我们基于松弛-取整框架设计了一种随机算法：首先利用资源预留机制（即设留机制）计算分数解以确保跨类公平；随后的取整步骤在不损害性能的前提下保持公平性。此外，我们还提出一种学习增强型变体，引入不可靠的机器学习预测，以在实际场景中更好平衡公平性与效率。
原文摘要 · Abstract (English)
We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach -- referred to as the set-aside mechanism -- to enforce fairness across classes. The subsequent rounding step preserves these fairness guarantees without degrading performance. Additionally, we propose a learning-augmented variant that incorporates untrusted machine-learned predictions to better balance fairness and efficiency in practical settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。