在线分配不可分物品时，利用未来信息可显著提升公平性保障。
Online Fair Division with Additional Information
- 通过引入未来物品价值的统计信息，设计新算法提升公平性。
- 在已知总价值或频率预测下，达到接近离线最优的公平保证。
- 对噪声数据具有鲁棒性，误差增大时公平性缓慢下降。
我们研究在在线场景下公平分配不可分物品的问题：物品按序到达且必须立即分配。聚焦于最流行的公平性概念——无嫉妒、比例公平和最大最小份额公平（及其近似变体），探究获取未来信息如何改变可实现的公平保证。在无任何信息的情况下，即使近似公平也存在强不可能性结果。当有归一化信息（即各代理的总价值）时，我们提出一种算法，其公平性优于已有结果，并证明更强公平性不可达。当有频率预测（价值多重集但无顺序）时，设计了一种元算法，将广泛的离线“基于份额”的保证迁移至在线场景，匹配目前已知的最佳离线界。最后，我们提供了两种模型的可学习增强版本：在总价值或频率预测存在噪声时，我们的保证依然稳健，且随误差参数平滑退化。
原文摘要 · Abstract (English)
We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we investigate how access to future information changes what guarantees are achievable. Without any information, we prove strong impossibility results even for approximate fairness. With normalization information (agents' total values), we provide an algorithm that achieves stronger fairness guarantees than previously known results, and show matching impossibilities for stronger notions. With frequency predictions (value multisets without order), we design a meta-algorithm that lifts a broad class of offline ''share-based'' guarantees to the online setting, matching the best-known offline bounds. Finally, we provide learning-augmented variants of both models: under noisy totals or noisy frequency predictions, our guarantees are robust and degrade gracefully with the error parameters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。