Local Search Approaches in Stable Matching Problems
Local Search Approaches in Stable Matching Problems
复制标题
稳定匹配问题中的局部搜索方法
作者：
M. Gelain;M. S. Pini;F. Rossi;K. Venable;T. Walsh
稳定婚姻（SM）问题有着广泛的实际应用，从住院医生与医院的匹配，到学生与学校的匹配，或者更普遍的是，任何双边市场。在经典公式中，n个男人和n个女人表达他们对另一性别成员的偏好（通过严格的全序）。解决SM问题意味着找到一个稳定的婚姻，稳定是一个没有嫉妒的概念：没有一个没有结婚的男人和女人会喜欢对方而不是他们的伴侣或单身。我们认为这两个经典的稳定的婚姻问题和它的一个有用的变化（表示SMTI（稳定的婚姻与领带和不完整的列表）），其中的男性和女性表达他们的偏好的形式，一个不完整的偏好列表的关系超过一个子集的其他性别的成员。只有出现在这些偏好列表中的人才允许匹配，我们试图找到一个稳定的匹配，尽可能多的人结婚。虽然SM问题是多项式来解决的，但SMTI问题是NP-难的。我们建议通过局部搜索方法来解决这两个问题，该方法利用问题的属性来减小邻域的大小并有效地进行局部移动。我们经验性地评估我们的算法SM问题，通过测量其运行时的行为和采样所有可能的稳定婚姻的晶格的能力。我们评估我们的算法SMTI问题的运行时行为和它的能力，找到一个最大的基数稳定的婚姻。实验结果表明，对于SM问题，我们的算法的步骤数仅增长为O（n log（n）），它很好地采样所有稳定婚姻的集合。因此，这是一个公平和有效的方法，以产生稳定的婚姻。此外，我们的SMTI问题的方法是能够解决大的问题，快速返回稳定的匹配大，往往是最佳的大小，尽管这个问题的NP-硬度。
The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as O(n log(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem.