Question

In the context of matching problems, another famous assignment algorithm is the Boston algorithm which is similar to the Gale-Shapley algorithm. The difference is that no “temporary acceptance” is allowed. That is if a women accepts the offer of a man, that man and woman marry and leave the algorithm. More precisely, the men-proposing Boston algorithm runs as follows: Step 1: Each man proposes to their top ranked woman. Step 2: Each woman accepts the best offer she receives. Matched man and woman marry and leave the algorithm. Step 3: Each single man proposes to their top ranked woman among the unmar- ried ones, and algorithm continue until there is no single man left. Consider the matching game played with the men-proposing Boston algorithm. Show whether truthtelling (reporting the true preferences) is a weakly dominant action for each man or not?

Answer 1

Answer: