Here is a pictorial depiction of the Gale-Shapley algorithm:
.JPG)
- Each man $M_i$ is drawn as a square and each woman $W_j$ as a circle.
- Each person's choices are arranged clockwise, in ascending order of desirability - i.e. the bottom choice first, followed by better and better choices and eventually the top choice in a clockwise manner.
- According to the algorithm
- Man proposes to his highest choice woman that he has not proposed to. So, in the diagram above, he goes through his choices anti-clockwise.
- Woman accepts a proposal if the man is better than her current fiance. So, in the diagram above, she goes through her choices clockwise.
- As the algorithm progresses, every woman can only improve her situation. In other words, the worst she can do is her current fiance - it only gets better for her!
- As the algorithm progresses, every man's position can only get worse. In other words, "it is all downhill" for him.
- The reason for rejecting a man's proposal is always that the woman's current choice is better than him (for her) and it can only get better for her, implying that he cannot introduce instability for those women who have rejected him.
- Since a woman can be proposed to only once by each man, she can get no more than $|M|$ proposals. Since there are $|W|$ women and some woman is proposed to at each step, the algorithm has to terminate in $O(|M|\times|W|)$ time.
- When we have an equal number of men and women, each woman will be proposed to (eventually). This means that each woman will have a fiance (she must accept a proposal if she has no fiance). Since $|M|=|W|$ in this case, this algorithm runs in $O(n^2)$ time.
References
