The process of choosing a free man to propose is arbitrary in the algorithm desc
ID: 2247593 • Letter: T
Question
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) _____Explanation / Answer
i. Maximum number of times the rank of a woman can go up during the run of Gale Shapely algorithm for 2 men and 2 women = 2 times
[Formula used:
n^2 - 2n+2 is the maximum number of iterations for the algorithm
During each iteration there can be broken engagement for a pair.
During each broken engagement the rank of the partner will increase.
]
ii) Sample Preference list :
m:[w,x,y]
n:[x,y,w]
o:[y,w,x]
w:[o,n,m]
x:[m,o,n]
y:[n,m,o]
iii) Maximum number of broken marriages using this preference list: 5
ii. Upper bound on number of broken engagements for n=2: 2 times
[n^2-2n+2]
II.II)For n=3: upper bound=5
II.III)For n : upper bound=n^2-2n+2
II.IV).
Simplifying assumption which may not be true: At each step each man will be proposing to one woman and a pair wiill be formed between the two.
In real world there might be a scenario where some men and women are not paired up during an iteration step
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.