Finding all stable matchings with assignment constraints

Gregory Gutin, Philip R. Neary and Anders Yeo

Papers from arXiv.org

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, that determines if assignment constraints are compatible with stability. Whenever there is a stable matching that satisfies the assignment 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.

Date: 2022-04, Revised 2024-06
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://arxiv.org/pdf/2204.03989 Latest version (application/pdf)

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:arx:papers:2204.03989

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().