Finding all stable matchings with assignment constraints
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.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
Solving stable matching problems using answer set programming
Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each varian…
Matching markets with farsighted couples
We adopt the notion of the farsighted stable set to determine which matchings are stable when agents are farsighted in matching markets with couples. We show that a singleton matching is a farsighted stable set if and on…
Priority-Neutral Matching Lattices Are Not Distributive
Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal fo…
On the many-to-one strongly stable fractional matching set
For a many-to-one matching market where firms have strict and $\boldsymbol{q}$-responsive preferences, we give a characterization of the set of strongly stable fractional matchings as the union of the convex hull of all …
AllAnytime Capacity Expansion in Medical Residency Match by Monte Carlo Tree Search
This paper considers the capacity expansion problem in two-sided matchings, where the policymaker is allowed to allocate some extra seats as well as the standard seats. In medical residency match, each hospital accepts a…