In the stable matching problem, I am trying to generate the preference lists for worst case.I came across a paper that says this is the worst case for n=5
m1: w1 w2 w3 w4 w5
m2: w2 w3 w4 w1 w5
m3: w3 w4 w1 w2 w5
m4: w4 w1 w2 w3 w5
m5: w1 w2 w3 w4 w5
w1: m2 m3 m4 m5 m1
w2: m3 m4 m5 m1 m2
w3: m4 m5 m1 m2 m3
w4: m5 m1 m2 m3 m4
w5: m1 m2 m3 m4 m5
Intuitively, this kind of makes sense.But can anyone formally argue why this is the worst case and why we cannot get a worse case than that?
The Gale-Shapley algorithm is one method used to solve the stable matching problem, ensuring both a perfect matching and no instabilities. This algorithm consists of repeated offers and ends when everybody has been paired. In this case of the stable marriage problem, the men would propose to the women in their order of preference. If the woman is not in a pair, she must accept the proposal. If the woman is in a pair, she is able to accept another proposal if the man proposing is higher on her preference list than the current man she is paired with. Once every woman has been proposed to (and thus everybody has been paired) the algorithm ends.
The preference lists you mentioned are one example of a worst case scenario for the stable matching problem. To see how this works, it helps to draw it out and run through each step. First, m1 will propose to w1, and w1 must accept because she is not currently in a pair. m2 will propose to w2, m3 will propose to w3, m4 will propose to w4. As you can see, currently every man has their FIRST preference woman and every woman has their FIFTH preference man (except for m5 and w5). The algorithm continues because w5 is left unpaired.
Next, m5 will propose to w1. w1 is able to accept because she has ranked m5 higher than m1. Now, m1 is unmatched so he proposed to w2. w2 accepts because m1 is ranked higher than m2 on her preference list. This continues down and you will notice every man is being paired up with their SECOND preference woman and every woman is accepting offers from their FOURTH preference man (except for w5). The algorithm continues because w5 is still left unpaired.
Once you have run through the entire algorithm, you will notice the final pairings as m1-w5, m2-w1, m3-w2, m4-w3, and m5-w4. Each male has their FOURTH preference woman (aside from m1 who has his FIFTH preference) and each woman has their FIRST preference man.
Notice how each man has w5 as their fifth preference. Because of this, every man will go through their entire list before extending an offer to w5. The list of preferences for w5 could be in any order and it would still be the worst case. The preference lists you mentioned are just one example of a worst case, but there are other variations that follow the same logic as this one.
Here is a more formal way to prove the worst case. No woman can receive more than n proposals, but once every woman receives a proposal the algorithm stops. Therefore, in the worst case, every woman except for one (n - 1 women) receive a proposal from every man (n). The last woman will receive 1 proposal which will ultimately end the algorithm. Combining these together, the worst case occurs when n(n-1) + 1 proposals are extended. In your example, 4 men ended with their fourth preference (4 proposals each) and 1 man with his fifth preference (5 proposals). 4*4 + 5 = 21 which is equal to plugging n = 5 into n(n-1) + 1.
I hope this helps.