论文标题
找到所有稳定的匹配和分配约束
Finding all stable matchings with assignment constraints
论文作者
论文摘要
在本文中，我们认为稳定的匹配受到分配约束。这些是需要包括某些分配的对的匹配项，坚持认为其他某些分配的对不是，而且重要的是稳定。我们的主要贡献是基于迭代删除未吸引人替代方案的算法，该算法确定了分配约束是否与稳定性兼容。每当有一个满足分配约束的稳定匹配时，我们的算法都会输出所有算法（每个解决方案中的多项式时间）。这为市场设计师提供了（i）测试受分配约束的稳定匹配可行性的工具，以及（ii）可在可行的工具。
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.
