Dividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
Argyris Deligkas and Eduard Eiben and Tiger-Lily Goldsmith and Dušan Knop and Šimon Schierreich
在标准的公平划分模型中,我们假设所有的代理人都是自私的。 然而,在很多情况下,资源划分会直接影响到整个群体甚至社会。 因此,我们研究对不可分割的项目的公平分配,同时最大限度地发挥社会影响。 在这个模型中,每个代理与两个附加函数相关联,这两个函数定义了它们对每个项目的价值和社会影响。 目标是分配项目,使社会影响最大化,同时保持一些公平标准。 我们揭示问题的复杂性在很大程度上取决于代理人是否具有社会意识,即他们考虑到社会影响功能。 对于社会不知情的代理人,我们证明这个问题对于各种公平概念来说是NP-硬,并且它只能用于非常有限的情况,例如,如果对每个代理人来说,估值等于社会影响并且它是二元的。 另一方面,社会意识允许公平的分配,最大限度地发挥社会影响,这种分配可以在多项式时间计算。 有趣的是,一旦社会意识的定义放松,问题就再次变得棘手。
In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining som...
