Question

5. Stability of marriage. There are four men, α, β, γ, δ, and four women, A, B,C,D, The first number of each second number is the ranking of men by the women. For example, a-male ranks women C on third place, while C ranks α on the first place. A marriage profile is a pairing of men to women. A marriage profile is stable if there is no pair of a man and a woman who are not married to each other, and the woman prefers this man to her husband, and this man prefers this woman to his wife. Find a stable marriage profile.

Answer 1

Preferences of men:

$\alpha$ = A,B,C,D
$\beta$ = A,B,C,D
$\gamma$ = B,C,A,D
$\delta$ = C,A,B,D

Preferences of women:

A = $\gamma$,$\delta$,$\alpha$,$\beta$
B = $\delta$,$\alpha$,$\beta$,$\gamma$
C = $\alpha$,$\beta$,$\gamma$,$\delta$
D = $\delta$,$\gamma$,$\alpha$,$\beta$

What does the algorithm look like? The algorithm is called "men-proposing algorithm". In each iteration, an unmarried man proposes to the first woman on his list that he hasn’t proposed to yet. A woman who receives a proposal that she prefers to her current assignment accepts it and rejects her current assignment.

• Now, $\alpha$ proposes to the first woman on his list: A. A has no offers and accepts.
• $\beta$ proposes to A, who rejects. He moves on to the second woman on his list: B. She has no offers and accepts.
• Now, $\gamma$ proposes to B. B prefers $\beta$ over $\gamma$ and rejects him. $\gamma$ moves on to the second woman on his list: C. C has no offers and accepts.
• Next, $\delta$ asks out C, who refuses, because she prefers $\gamma$ over $\delta$. $\delta$ moves on to the second woman on his list: A. Now, A prefers $\delta$ to $\alpha$, so she agrees and rejects $\alpha$.
• $\alpha$ moves on to B, who prefers him to $\beta$.
• $\beta$ asks out C who prefers him over $\gamma$, she accepts his offer and rejects $\gamma$.
• $\gamma$ asks out A, who prefers him over everyone else, she accepts $\gamma$ and rejects $\delta$.
• $\delta$ asks out B, the third woman on his list, who prefers him over others, so she accepts him and rejects $\alpha$.
• $\alpha$ asks out C, who prefers him over everyone else, and she accepts him, rejects $\beta$.
• $\beta$ asks out the final woman on his list, D, who has no offers and accepts.

Hence, we get,
$\alpha$ with C
$\beta$ with D
$\gamma$ with A
$\delta$ with B
This association meets the definition of a stable marriage profile.

Hope this helped!