论文标题
3D享乐游戏中的嫉妒
Envy-freeness in 3D Hedonic Games
论文作者
论文摘要
我们研究了基于代理商可分离的偏好将一组代理分配到联盟中的问题，这也可以将其视为享乐游戏。我们采用三个依次弱的解决方案概念，即嫉妒，弱的嫉妒和有道理的嫉妒。 在联盟可能具有任何规模的模型中，对于这些概念而存在琐碎的解决方案，这为放大联盟规模的限制提供了强大的动力。在本文中，我们要求可行的联盟具有三个尺寸。我们研究了分区的存在，这些分区是无嫉妒的，弱的嫉妒且无理的嫉妒，以及如果存在这些分区的计算复杂性。 我们就对代理人偏好的限制表示了全面的复杂性分类。由此，我们确定了一个普遍的趋势，即对于三种依次较弱的解决方案概念，存在和多项式时间溶解度在较弱的限制下具有。
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.
