1. The Gale-Shapley algorithm is man-optimal and woman-pessimal, as men are allowed to propose (in decreasing order of preference).

(a) How bad can it get for a woman? Can you construct a worst-case example? Try starting with n = 2 or n = 3, and then generalize to arbitrary n.

(b) How good can it get for a man? Can you construct the best-case example for men? Again, you can start with n = 2 or n = 3, and then generalize to arbitrary n.

(c) What happens if you switch the role of men and women in Gale-Shapley for the above two examples?