arXiv:2506.21727cs.GTcs.AI2025-06被引 4

多维度公平分配新方法,解决资源评估中多个标准的公平难题。

Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

  • 提出弱/强同时免嫉妒(sEFc)概念,适应多属性偏好
  • 证明存在性边界与算法,无需依赖物品总数
  • 适用于云资源、任务分配等多维公平场景

本文研究多维度环境下不可分物品的公平分配问题,源于复杂环境中代理人需基于多个标准评估资源包的实际需求。例如云计算资源按CPU核数、内存和网络带宽等多个维度评估,传统单维度公平概念无法充分反映多属性公平性。为此,论文提出两种宽松版同时免嫉妒定义:弱同时免嫉妒至c个物品(weak sEFc)与强同时免嫉妒至c个物品(strong sEFc)。在弱情形下,对任意两位代理人及每个维度,通过移除被妒者分配中不同物品集可消除嫉妒;强情形要求仅用一个物品集的移除即可在所有维度上消除嫉妒。论文给出了保证弱或强sEFc分配存在的松弛参数c的上下界,且这些界与物品总数无关。此外,提出了判断弱或强sEFc分配是否存在性的算法,并证明了检查弱sEF1与强sEF1分配存在的复杂度为NP-hard。

原文摘要 · Abstract (English)

This paper explores the fair allocation of indivisible items in a multidimensional setting, motivated by the need to address fairness in complex environments where agents assess bundles according to multiple criteria. Such multidimensional settings are not merely of theoretical interest but are central to many real-world applications. For example, cloud computing resources are evaluated based on multiple criteria such as CPU cores, memory, and network bandwidth. In such cases, traditional one dimensional fairness notions fail to capture fairness across multiple attributes. To address these challenges, we study two relaxed variants of envy-freeness: weak simultaneously envy-free up to c goods (weak sEFc) and strong simultaneously envy-free up to c goods (strong sEFc), which accommodate the multidimensionality of agents' preferences. Under the weak notion, for every pair of agents and for each dimension, any perceived envy can be eliminated by removing, if necessary, a different set of goods from the envied agent's allocation. In contrast, the strong version requires selecting a single set of goods whose removal from the envied bundle simultaneously eliminates envy in every dimension. We provide upper and lower bounds on the relaxation parameter c that guarantee the existence of weak or strong sEFc allocations, where these bounds are independent of the total number of items. In addition, we present algorithms for checking whether a weak or strong sEFc allocation exists. Moreover, we establish NP-hardness results for checking the existence of weak sEF1 and strong sEF1 allocations.

公平分配多维度算法设计资源调度

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