论文标题
稳定的室友问题具有多样性偏好
Stable Roommate Problem with Diversity Preferences
论文作者
论文摘要
在多维稳定的室友问题中，必须将代理分配给房间，并且对一组潜在的室友有偏好。在假设代理具有多样性偏好的假设下，我们研究了代理商对房间的良好分配的复杂性[Bredereck等，2019]：每个代理都属于两种类型之一（例如，大三学生和老年人，老年人，艺术家和工程师），以及代理商在房间中的偏好完全取决于他们自身的房间的本质。我们考虑了针对此设置的各种解决方案概念，例如核心和交换稳定性，帕累托最优性和嫉妒性。负面的一面，我们证明，嫉妒，核心稳定或（强烈）交换稳定的结果可能不存在，并且相关的决策问题是NP的完整问题。从积极的一面来看，我们表明这些问题在房间大小方面是FPT，这对于一般稳定的室友问题并非如此。此外，对于具有二大尺寸的经典设置，我们提出了一种线性时间算法，该算法计算出核心和交换稳定以及帕累托最佳的结果。我们对稳定室友问题的许多结果扩展到了稳定的婚姻问题。
In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents' preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.
