We study the stable matching problem with partial information, where agents submit only partial approval preferences, and the goal is to find a matching that is as stable as possible in the worst-case scenario. Unlike previous studies that focus solely on the Stable Marriage setting and measure stability by the number of blocking pairs, we explore another well-explored stability measure: the number of blocking agents. Additionally, we extend our analysis to both the Stable Roommates and Hospital/Residents problems. Our findings offer a comprehensive view of the computational complexity across these problem variants, highlighting interesting contrasts between blocking agents and blocking pairs, as well as among the three stable matching settings.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimizing Blocking Agents for Stable Matching with Partial Approval Information

  • Yitian Gao,
  • Jiaxue Li,
  • Junjie Luo,
  • Yiheng Zhang

摘要

We study the stable matching problem with partial information, where agents submit only partial approval preferences, and the goal is to find a matching that is as stable as possible in the worst-case scenario. Unlike previous studies that focus solely on the Stable Marriage setting and measure stability by the number of blocking pairs, we explore another well-explored stability measure: the number of blocking agents. Additionally, we extend our analysis to both the Stable Roommates and Hospital/Residents problems. Our findings offer a comprehensive view of the computational complexity across these problem variants, highlighting interesting contrasts between blocking agents and blocking pairs, as well as among the three stable matching settings.