Multi-objective stable matching with ties

摘要

Stable Matching (SM) has received a lot of attention from researchers due to its useful applications in practice. Gale and Shapley were the first to propose a polynomial-time algorithm to find an SM solution, for matching with strict preferences. However, their algorithm often produces extreme stable solutions, favouring either men or women. In practice, the real-life problems have multiple objectives (equitable and welfare) and preferences are not strict, consequently ties occur. With the inclusion of ties and objectives, the problem becomes NP-hard. A few researchers proposed local search and evolutionary algorithms to solve multi-objective SM problem with ties, but these methods were not scalable. In this paper, we propose an efficient Goal Programming and Repair Heuristics based approach to solve this problem. On comparison with other related works, our approach shows significant improvement in respective objectives (equity and welfare). This approach with slight modification can be proved useful for solving other hard variants of the SM problem.