Open AccessBribery and Control in Stable Marriage
Author(s) -
Niclas Boehmer,
Robert Bredereck,
Klaus Heeger,
Rolf Niedermeier
Publication year - 2021
Publication title -
journal of artificial intelligence research/the journal of artificial intelligence research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.79
H-Index - 123
eISSN - 1943-5037
pISSN - 1076-9757
DOI - 10.1613/jair.1.12755
Subject(s) - parameterized complexity , preference , action (physics) , computer science , control (management) , time complexity , computational complexity theory , polynomial , natural (archaeology) , theoretical computer science , mathematical economics , mathematics , artificial intelligence , algorithm , statistics , archaeology , history , mathematical analysis , physics , quantum mechanics
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.