Stable Matching Problem and Its Approach to Determine Vital Link in 2-way Network

Abstract

1.1 Stable Matching Problem The Stable matching problem was first introduced by David Gale and Lloyd Shapely in 1962 in a paper entitled “College Admission and the Stability of Marriage” [1]. Gale and Shapely analysed the matching at abstract and general level where they used marriage problem as an illustrative example. Idea behind the marriage problem was “How matching should be done between set of men and set of women with their respective preference list?” The main challenge behind the simple idea was that matching should be done in such a way that no pair should break up and form new pair which would make them better off. For such idea, the solution was “Gale Shapely – deferred acceptance algorithm” consisting of set of simple rule and solvable in polynomial time.