Question

N men and N women were participating in a stable matching process in a small town named Walnut Grove. A stable matching was found after the matching process finished and everyone got engaged. However, a man named Almazo Wilder, who is engaged with a woman named Nelly Oleson, suddenly changes his mind by preferring another woman named Laura Ingles, who was originally ranked right below Nelly in his preference list, therefore Laura and Nelly swapped their positions in Almanzos preference list. Your job now is to find a new matching for all of these people and to take into account the new preference of Almanzo, but you don't want to run the whole process from the beginning again, and want to take advantage of the results you currently have from the previous matching. Describe your algorithm for this problem. Assume that no woman gets offended if she got refused and then gets proposed by the same person again.

Answer 1

Answer:

The simple algorithm is described below

Explanation:

assign all men and women as free

while some man m is free do

  w = highest ranked women on m's list

  if w is free

      then m proposes w and m and w are engaged

  else if w is not free and with m1

      and if w picks m over m1

          then w and m are engaged

          free m1

end

output all the pairs