Bribery and Control in Stable Marriage
| Autor: | Rolf Niedermeier, Klaus Heeger, Robert Bredereck, Niclas Boehmer |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Discrete Mathematics (cs.DM) Computational complexity theory Computer science Parameterized complexity Stable marriage problem Preference Action (philosophy) Computer Science - Computer Science and Game Theory Artificial Intelligence Natural (music) Control (linguistics) Computer Science and Game Theory (cs.GT) Computer Science - Discrete Mathematics |
| Zdroj: | Journal of Artificial Intelligence Research. 71:993-1048 |
| ISSN: | 1076-9757 |
| DOI: | 10.1613/jair.1.12755 |
| Popis: | 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. Accepted for publication at the Journal of Artificial Intelligence Research (JAIR) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|