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 rating: 100% (QA)

In the menproposing Boston algorithm truthtelling may not always be a weakly dominant action for eac... View the full answer