We study the problem of partitioning a set of agents into coalitions based on the agents' additively separable preferences, which can also be viewed as a hedonic game. We apply three successively weaker solution concepts, namely envy-freeness, weakly justified envy-freeness, and justified envy-freeness. In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist. We present a comprehensive complexity classification, in terms of the restrictions placed on the agents' preferences. From this, we identify a general trend that for the three successively weaker solution concepts, existence and polynomial-time solvability hold under successively weaker restrictions.
翻译：我们研究将一组代理商分割成联盟的问题,其基础是代理商的累加分解的偏好,这种偏好也可以被视为一种超常游戏。我们采用三个相继的较弱的解决方案概念,即无嫉妒、无嫉妒、无嫉妒、无嫉妒和无嫉妒。在一个联盟可能具有任何规模的模型中,存在对这些概念的微小解决方案,这为限制联盟规模提供了强烈的动机。在本文件中,我们要求可行的联盟体积为三。我们研究存在一些无嫉妒、无嫉妒和无嫉妒的不合理分解,以及如果存在的话,找到这种分割的计算复杂性。我们在对代理商偏好的限制方面提出了全面的复杂分类。我们从这一点出发,我们确定了一个总的趋势,即对于连续三个较弱的解决方案概念、存在和多民族时期的可溶性,在连续较弱的限制下存在。
相关内容
微信扫码咨询专知VIP会员