Gale-Shapley Algorithm for Stable Matching

In this scenario, we are matching animals with families. The Gale-Shapley algorithm matches by having one group request the other, and the other either accepts or declines.

Suppose we have the animals request the families. The animals will request their most-preferred family. If the family has not already accepted another animal, then it will accept.

If the family has already accepted another animal, then there are two options.

1) If the family prefers this animal over the current animal it has accepted, then it will abandon the old animal and accept the new one.

2) If the family does not prefer this animal over the current animal, it will reject the animal.



If an animal has been rejected or abandoned, then they will choose their next prefered family to repeat the process.

This algorithm ensures that every animal and every family each has a match, and that the matches are stable, since every animal and family are matched in a manner so that there would not be a situation where both a student and school prefer each other over the matches they have.

        stableMatching():
          init all a in animals to free
          init all f in families to free

          while(a is free):
            f = most-preferred family by a which a has not requested
            if f is free:
              a and f become paired
            else if f is not free (matched with a'):
              if f prefers a to a':
                a' becomes free
                a and f become paired
              else:
                a' and f remain paired