Adapting stable matchings to evolving preferences

• 成果类型: Article
• 署名作者: Bredereck, Robert; Chen, Jiehua; Knop, Dusan; Luo, Junjie; Niedermeier, Rolf
• 署名单位: TU Clausthal; Technische Universitat Wien; Czech Technical University Prague; Beijing Jiaotong University; Technical University of Berlin
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2026.02.006
• 发表日期: 2026
• 关键词: marriage; complexity; algorithms

摘要

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 STA-BLE 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 MAR-RIAGE 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.