The process of choosing a free man to propose is arbitrary in the algorithm description. Assume we will choose by earliest in alphabetical order. In this problem we want to maximize the number of broken engagements (a man going from engaged to free). i. To get started: every time a woman breaks an engagement, the rank of her partner goes up! What is the maximum number of times that the rank of a particular woman's partner can go up through the course of the Gale-Shapley algorithm if there are 2 men and 2 women? _____ ii. Make up preference lists that maximize the number of broken engagements during a run of the GS algorithm where there are 3 men and 3 women: m: [] n: [] o: [, ] w: [] x: [] y: [, ] iii. What was the maximum number of broken engagements using the preference lists you made up? (1 found preference lists that cause 4 broken engagements during the algorithm.) _____ H. If the size of the sets of men and women is some number n: i. What is an upper bound on the number of broken engagements in a run of the Gale-Shapley i. What is an upper bound on the number of broken engagements in a run of the Gale-Shapley algorithm for n = 2? _____ ii. For n = 3? _____ iii. For any n? _____ iv. What did our simple upper bound assume that wasn't right? (We're looking for something straightforward here) _____