Adapting stable matchings to evolving preferences

Adaptivity to changing environments and constraints is key to success in modern society. We address this principle by proposing “incrementalized versions” of Stable Marriage and Stable Roommates, asking what the computational cost is of adapting an existing stable matching after agents’ preferences have changed. We additionally require that the new stable matching should not deviate too much from the old one. After formalizing these incremental versions, we provide a comprehensive computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results. In particular, with ties in preferences, both problems remain computationally intractable even under minimal preference changes, whereas with strict preferences, both become (fixed-parameter) tractable, regardless of the extent of preference changes.