论文标题
室友多样性问题的知名度
Popularity on the Roommate Diversity Problem
论文作者
论文摘要
多维稳定室友问题的最近引入的限制性变体是室友多样性问题：每个代理属于两种类型之一（例如，红色和蓝色）之一，代理商对联盟的偏好仅取决于他们自己室友中自己类型的代理人的比例。 有各种稳定概念定义了对代理的最佳分区。最近，人们的概念最近引起了很多关注。如果不存在另一种分区，那么对代理的分区将很受欢迎，在这种分区中，代理比更糟的情况更好。在稳定的室友游戏中计算流行的分区可以在多项式时间内完成。当我们允许纽带时，稳定的室友问题将变成NP完整。确定多维稳定室友问题中流行解决方案的存在，也是NP-HARD。 我们表明，在室友的多样性问题中，固定在两个的房间大小，问题变得可行。特别是，可以保证存在对代理的流行分区，并且可以在多项式时间内计算。此外，在任何室友多样性游戏中，始终可以对代理商进行混合的流行分区。相比之下，当室友多样性游戏的联盟规模没有限制时，流行的分区可能不存在，并且问题变得棘手。我们的结果可治性结果总结如下： *即使代理人的偏好是三角形的，确定流行分区的存在也是co-np-hard。 *即使代理人的偏好是二分法的，确定严格流行的分区的存在也是共同的。 *即使P = np，即使代理的偏好是二分法，在多项式时间内计算混合的流行分区是不可能的。
A recently introduced restricted variant of the multidimensional stable roommate problem is the roommate diversity problem: each agent belongs to one of two types (e.g., red and blue), and the agents' preferences over the coalitions solely depend on the fraction of agents of their own type among their roommates. There are various notions of stability that defines an optimal partitioning of agents. The notion of popularity has received a lot of attention recently. A partitioning of agents is popular if there does not exist another partitioning in which more agents are better off than worse off. Computing a popular partition in a stable roommate game can be done in polynomial time. When we allow ties the stable roommate problem becomes NP-complete. Determining the existence of a popular solution in the multidimensional stable roommate problem also NP-hard. We show that in the roommate diversity problem with the room size fixed to two, the problem becomes tractable. Particularly, a popular partitioning of agents is guaranteed to exist and can be computed in polynomial time. Additionally a mixed popular partitioning of agents is always guaranteed to exist in any roommate diversity game. By contrast, when there are no restrictions on the coalition size of a roommate diversity game, a popular partitioning may fail to exist and the problem becomes intractable. Our results intractability results are summarized as follows: * Determining the existence of a popular partitioning is co-NP-hard, even if the agents' preferences are trichotomous. * Determining the existence of a strictly popular partitioning is co-NP-hard, even if the agents' preferences are dichotomous. * Computing a mixed popular partitioning of agents in polynomial time is impossible unless P=NP, even if the agents' preferences are dichotomous.
