Minimizing Blocking Agents for Stable Matching with Partial Approval Information
摘要
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.