Finding all stable matchings with assignment constraints

Gregory Z. Gutin, Philip R. Neary and Anders Yeo

Games and Economic Behavior, 2024, vol. 148, issue C, 244-263

Abstract: 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.

Keywords: Stable matchings; Assignment constraints; Iterated deletion of unattractive alternatives; Normal form (search for similar items in EconPapers)
JEL-codes: C78 D47 D82 (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825624001350
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:148:y:2024:i:c:p:244-263

DOI: 10.1016/j.geb.2024.09.004

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().