研究树状结构中多层级资源公平分配，提出新公平准则并验证算法有效性。
Multilevel Fair Allocation under Additive Preferences
- 基于树形层级结构设计多级公平分配机制
- 在相同偏好下，三种公平准则等价且MWRR可保证
- 实验显示即使不严格满足，算法仍表现良好
我们研究具有树状层级关系的多层级公平资源分配问题。每一层可视为将父节点的资源包分配给其子节点，整体分配是该过程自顶向下迭代至叶节点的结果。假设内部节点的效用为其子节点效用之和（功利主义福利），叶节点具有对物品的经典可加效用。我们首先提出通常基于嫉妒的公平概念（如WEF1）的多层级扩展。给出三种扩展形式，并证明其选择并非中立。在偏好一致条件下，三种扩展准则等价，且多层级加权轮询法（MWRR）可保证它们。在一般偏好下，MWRR可能仅保证部分准则而不满足其他。实验表明，即使未被形式化保证，MWRR在多数情形下仍具良好性能。
原文摘要 · Abstract (English)
We study multilevel fair resource allocation with tree-structured hierarchical relations among agents. At each level, the problem can be viewed locally as allocating an agent's bundle to its children, the overall allocation being a trace of this process iterated down to the leaves. Assuming that internal nodes' utilities are the utilitarian welfare of their children, and the leaves have classical additive utilities over items, we first propose multilevel adaptations of usual envy-based fairness notions (e.g., WEF1). We present three adaptations and show that the choice among them is not neutral. We prove that, under identical preferences, the three adapted envy-based notions coincide, and that the Multilevel extension of Weighted Round Robin (Chakraborty et al., 2021) (MWRR) guarantees them. We then show that under general preferences, MWRR may guarantee some notions while failing others. Finally, through experiments, we show that MWRR may still perform well even for adaptations it does not formally guarantee.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。