We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the $n$ agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to $\Theta(\sqrt{n})$ goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to $o(\sqrt{n})$ goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
翻译:我们研究的是利用众所周知的公平概念,如嫉妒自由性和相称性,在各类代理人之间分配不可分割货物的问题。虽然这些概念并不总是能够满足,但我们提供了可以保证的最佳放松的几条界限。例如,我们的界限意味着,当集团数量不变,而美元代理人被任意划分为集团时,就存在着一种无嫉妒性的分配,最高可达$(sqrt{n})美元的货物,而且这种约束也十分严格。此外,我们表明,虽然这种分配可以有效地找到,但很难计算出一个无嫉妒性最高达$(sqrt{n})的商品分配,即使完全没有嫉妒性的分配存在。我们的证据广泛利用差异理论的工具。