Have you ever dreamed of being a match maker? Ya me neither but still this is a pretty cool theorem. There is a theorem called the stable marriage theorem. The basic gist of the theorem is that if you go to a town with n number of men and n number of women and you have each one of the make a list of there most desirable match there is a way to match all of the people up so that everyone will be with someone that they desire and no cheating will take place. 

So lets go through an example:

So suppose that you are a matchmaker and you get the following lists from a town of 5 men and 5 women. 

Men 1 (1, 2, 3, 4, 5)   Women 1 (2, 3, 4, 5, 1)

Men 2 (3, 1, 4, 2, 5)   Women 2 (3, 4, 5, 1, 2)

Men 3 (1, 3, 5, 2, 4)   Women 3 (3, 5, 1, 4, 2)

Men 4 (5, 4, 3, 2, 1)   Women 4 (3, 1, 2, 4, 5)

Men 5 (1, 5, 4, 2, 3)   Women 5 (5, 4, 2, 3, 1)


Step 1: We are going to start with round 1, in round 1 each man will propose to their first choice like so:

Man 1  \(\rightarrow\) Women 1
Man 2 \(\rightarrow\)Women 3\(\checkmark\)
Man 3 \(\rightarrow\)Women 1\(\checkmark\)
Man 4 \(\rightarrow\)Women 5\(\checkmark\)
Man 5 \(\rightarrow\)Women 1
Each women will except the best offer. So women 1 will except the offer from man 3, women 3 will except the offer from man 2, and women 5 will except the offer from man 4.

Step 2: Each man that was rejected will ask his second choice to marry him.

Man 1  \(\rightarrow\) Women 2\(\checkmark\)

Man 5 \(\rightarrow\)Women 5\(\checkmark\)
Women 2 will except because it is the best offer she has gotten and Women 5 will leave Man 4 for Man 5 because Man 5 was her first choice. 

Step 3: Man 4 will ask his second choice to marry him.
Man 4 \(\rightarrow\)Women 4
She excepts

Last Step: We have all our pairs. 

Man 1  \(\rightarrow\) Women 2\(\checkmark\)

Man 2 \(\rightarrow\)Women 3\(\checkmark\)

Man 3 \(\rightarrow\)Women 1\(\checkmark\)

Man 4 \(\rightarrow\)Women 4\(\checkmark\)

Man 5 \(\rightarrow\)Women 5\(\checkmark\)\(\rightarrow\)

All thats left is for you to try one now, switch the men and women so the women are the ones who propose and see what matches you end up with.