Finding all stable matchings with assignment constraints

• 成果类型: Article
• 署名作者: Gutin, Gregory Z.; Neary, Philip R.; Yeo, Anders
• 署名单位: University of London; Royal Holloway University London; University of London; Royal Holloway University London; University of Southern Denmark; University of Johannesburg
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.09.004
• 发表日期: 2024
• 页码: 244-263
• 关键词: Stable matchings; Assignment constraints; Iterated deletion of unattractive alternatives; Normal form

摘要

In this paper we consider stable matchings subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are stable. Our main contribution is an algorithm, based on the iterated deletion of unattractive alternatives (Balinski and Ratier, 1997; Gutin et al., 2023), that determines if and when a given list of constraints is compatible with stability. Whenever there is a stable matching that satisfies the constraints, our algorithm outputs all of them (each in polynomial time per solution). This provides market designers with (i) a tool to test the feasibility of stable matchings subject to assignment constraints, and (ii) a tool to implement them when feasible.