Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets

No. 5: AAAI-22 Technical Tracks 5

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Game Theory and Economic Paradigms

Following up on purely theoretical work, 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.

10.1609/aaai.v36i5.20413