arXiv:2607.23310cs.GTcs.AI2026-07

在线分配中引入预算约束,实现更公平的资源分配。

Online Fair Division with Budget Constraints

  • 设计在线算法,在物品陆续到来时分配给符合条件的接收者或慈善机构。
  • 在预算可行集下,实现接近最优的公平性保证,尤其在小物品时可达理论最优。
  • 通过学习预测联合价值与大小类型,提升算法鲁棒性与公平性表现。

我们研究了在广义分配预算约束下的在线离散公平分配问题。物品逐个到达,必须不可撤销地分配给可行的接收者或慈善机构(持有所有未分配物品),而公平性仅针对每位接收者包中预算可行的子集进行评估。我们首先证明,在无额外结构条件下,任何确定性在线算法都无法保证对可行嫉妒消除的固定近似比,即使在高度对称实例中亦然。随后,我们识别出有界密度分布作为结构性条件,恢复有意义的保证,提出了适用于任意物品大小的近似算法,并表明在常见估值和足够小的物品下,这些保证可强化至最优确定性边界。此外,我们研究了资源增强情形,即在线算法被允许使用略大于公平基准的预算,刻画由此带来的保证提升。最后,我们提出基于预测联合价值-大小类型的增益学习框架,证明在完美预测下具有一致性,在预测误差下具有鲁棒性,且单独预测价值与大小边际不足以恢复强公平保证。

原文摘要 · Abstract (English)

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

在线分配公平性预算约束学习增强

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。