Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets
Niclas Boehmer, Klaus Heeger, Rolf Niedermeier
[AAAI-22] Main Track
Abstract:
Following up on purely theoretical work of Bredereck et al. [AAAI 2020], we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we perform extensive empirical studies hinting at numerous practically useful properties. Our theoretical extensions include the study of new problems (that is, incremental variants of Almost Stable Marriage and Hospital Residents), focusing on their (parameterized) computational complexity and the equivalence of various change types (thus simplifying algorithmic and complexity-theoretic studies for various natural change scenarios). Our experimental findings reveal, for instance, that allowing the new matching to be blocked by a few pairs significantly decreases the difference between the old and the new matching.
Introduction Video
Sessions where this paper appears
-
Poster Session 6
Sat, February 26 8:45 AM - 10:30 AM (+00:00)Blue 6 -
Poster Session 10
Sun, February 27 4:45 PM - 6:30 PM (+00:00)Blue 6