[Back]

R. Bredereck, J. Chen, D. Knop, J. Luo, R. Niedermeier:
"Adapting Stable Matchings to Evolving Preferences";
Talk: AAAI 2020, New York, USA; 2020-02-07 - 2020-02-12; in: "Proceedings of AAAI2020", (2020), ISBN: 978-1-57735-835-0; 1830 - 1837.

Adaptivity to changing environments and constraints is key tosuccess in modern society. We address this by proposing "in-crementalized versions" of STABLEMARRIAGEand STABLEROOMMATES. That is, we try to answer the following question:for both problems, what is the computational cost of adaptingan existing stable matching after some of the preferences ofthe agents have changed. While doing so, we also model theconstraint that the new stable matching shall be not too dif-ferent from the old one. After formalizing these incrementalversions, we provide a fairly comprehensive picture of thecomputational complexity landscape of INCREMENTALSTA-BLEMARRIAGEand INCREMENTALSTABLEROOMMATES.To this end, we exploit the parameters "degree of change" bothin the input (difference between old and new preference pro-file) and in the output (difference between old and new stablematching). We obtain both hardness and tractability results, inparticular showing a fixed-parameter tractability result withrespect to the parameter "distance between old and new stablematching".

https://publik.tuwien.ac.at/files/publik_293450.pdf