Solution
Who Ends Up with Z
Show the problem again
Four men (a, b, c, d) and four women (W, X, Y, Z) have strict preference lists, most preferred first: - a: W, X, Y, Z - b: X, W, Z, Y - c: W, X, Z, Y - d: Y, Z, W, X - W: c, b, d, a - X: a, b, c, d - Y: b, c, a, d - Z: d, c, a, b Run the Gale-Shapley algorithm with the men proposing: each unmatched man proposes to the best woman who has not yet rejected him, and each woman keeps the best proposer so far, rejecting the rest. Which man is matched to Z when the algorithm stops? Answer with the man's letter.
Worked solution
Round one: a proposes to W, b to X, c to W, d to Y. W prefers c to a and rejects a; X keeps b and Y keeps d. Round two: a proposes to X, who prefers a to b, so b is released. Round three: b proposes to W, who keeps c over b and rejects b. Round four: b proposes to Z, who has no one and accepts. The algorithm stops after 7 proposals with the matching a-X, b-Z, c-W, d-Y. Z ends up with **b**. (This is the man-optimal stable matching. There is a second stable matching, the woman-optimal one, in which Z is matched to d.)
Source: Gale-Shapley deferred acceptance (Gale and Shapley, 1962); the preference lists are invented for AxiomIQ. Statement written for AxiomIQ.