Gale-and-Shapley-algorithm

The stable marriage problem

In this project, a number, n, of stable marriage problems, each entailing n men and n women, will rank the members of the opposite sex in order of preference. A stable marriage can hence be described to be a complete match for both the man and woman. This means that there do not exist any two couples, m w and m w, whereby m prefers w to w and on the other hand, that w has a preference to m over m`.Such an event is hence considered to be unstable for a number of simple reasons. According to Gayle Shapley algorithm theorem, there exists at least one stable match for all problem instances, which has the effect of providing an efficient algorithm by which such matches can be found. The main idea of this project then is to solve the stable marriage problem that includes female and male preference lists for a large number of problems and using the Gale and Shapley algorithm. One of the main results of this project is that it is possible to show that the Gale and Shapley algorithm has been designed to be efficient and further, it is possible to show that it is able to handle more than 8000 male and female preference lists. The stable match list can also be found over a large number of males and females. The list of optimal matches can also be found by removing some of the rotation lists that have a maximum weight. In regard to the experiments performed, results from the first experiment show that the function F (n) of n increases when the value of n is increased. This is apparent after evaluating the average difference of a large number of trials for a fixed value of n. The second experiment aims at determining the number of rotations that can be exposed when the value of n is changed. The results of the second experiment indicate that the number of rotations exposed slightly increases when the value of n is increased.