论文标题
稳定婚姻中的贿赂和控制
Bribery and Control in Stable Marriage
论文作者
论文摘要
我们通过考虑多种操纵行动以及几个操纵目标来启动稳定婚姻中外部操作的研究。例如，一个目标是确保给定的代理在稳定的解决方案中匹配，这可以通过重新排序某些代理的首选项列表的操纵性动作来实现。我们对以这种方式产生的所有问题的计算复杂性进行了全面研究。我们发现了几个多项式时间可溶可溶剂和NP-HARD病例。对于NP硬性案例，专注于自然参数预算（即允许执行操作的动作数量），我们还进行了参数化的复杂性分析，并遇到大多数参数化硬度结果。
We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter budget (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.
