论文标题
加深增量稳定匹配问题的（参数化）复杂性分析
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
论文作者
论文摘要
计算稳定的匹配时，通常假定匹配市场中代理的偏好是固定的。但是，在许多现实的情况下，偏好会随着时间而变化。因此，最初稳定的匹配可能会变得不稳定。然后，一个自然的目标是找到相对于修改的偏好稳定的匹配，并尽可能接近初始匹配。对于稳定的婚姻/室友，Bredereck等人正式将这个问题正式定义为稳定的婚姻/室友。 [AAAI '20]。正如他们表明的那样，稳定的室友和与领带的增量稳定婚姻是NP-HARD，我们专注于这些问题的参数化复杂性。我们回答了Bredereck等人的两个开放问题。 [AAAI '20]：我们表明，增量稳定的室友是通过偏好的变化数量来参数w [1] - hard参数，但接受了复杂的XP-Algorithm，我们表明，与纽带的增量稳定婚姻是W [1] -HARD通过TIE的参数化。此外，我们分析了代理人的偏好列表之间“相似性”程度的影响，确定了几个多项式时间可溶可解决的和固定参数的可聊天案例，但也证明了增量稳定的室友和增量稳定的稳定婚姻以及通过不同偏好列表的参数为w [1] -Hard的稳定稳定婚姻。
When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.
