论文标题
与多层批准偏好稳定匹配：批准可能比严格的偏好更难
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
论文作者
论文摘要
我们研究了代理具有多层偏好的稳定匹配问题：每个代理都有$ \ ell $层，每个层由一个偏好关系组成。最近，Chen等。 [EC '18]研究了严格偏好的此类问题，建立了四个经典稳定概念的多层适应。我们通过分析具有多层批准偏好的稳定匹配问题的计算复杂性来跟进他们的工作。我们考虑了从三个公认的稳定概念得出的11个稳定概念，该概念与Chen等人提出的稳定匹配和四种适应性。对于每个稳定性概念，我们表明找到稳定匹配的问题是多项式时间可溶可溶解或NP-硬化。此外，我们研究了层数和所需的“稳定性”对问题复杂性的影响。有些令人惊讶的是，我们发现假设批准偏好而不是严格的偏好并不能大大简化情况（有时甚至会使多项式时间可解决的问题np-hard）。
We study stable matching problems where agents have multilayer preferences: There are $\ell$ layers each consisting of one preference relation for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, establishing four multilayer adaptions of classical notions of stability. We follow up on their work by analyzing the computational complexity of stable matching problems with multilayer approval preferences. We consider eleven stability notions derived from three well-established stability notions for stable matchings with ties and the four adaptions proposed by Chen et al. For each stability notion, we show that the problem of finding a stable matching is either polynomial-time solvable or NP-hard. Furthermore, we examine the influence of the number of layers and the desired "degree of stability" on the problems' complexity. Somewhat surprisingly, we discover that assuming approval preferences instead of strict preferences does not considerably simplify the situation (and sometimes even makes polynomial-time solvable problems NP-hard).
