Discussion 01

Prove that every execution of the G-S algorithm (when men are proposing) results in the same stable matching regardless of the order in which men propose.
Answer:
By way of contradiction, assume that every execution of the G-S algorithm did not result in the same stable matching. Consider two distinct orderings $O_1$ and $O_2$ of proposals resulting in two distinct perfect matchings, $M_1$ and $M_2$ respectively.
The stable matching returned by G-S ends in every man proposing at least once, and ending with every man getting engaged to his most-preferred woman, apart from those who rejected him for a man they later found more preferable.
Every woman accepts every proposal extended to her, provided she receives it from a man she prefers over her current partner. Without loss of generality, consider the woman $w$ who had married one man $m_1$ in $M_1$ during $O_1$ but ends up with a different man $m_2$ in $M_2$ during $O_2$. There are three cases in which this could have happened:
1. The proposal she had originally received from $m_1$ during $O_1$ was not extended to her again by $m_1$ during $O_2$
  Case 1: If she did not receive it again in $O_2$, then the man she ended up with in $M_1$ must have married someone he finds more preferable. Every man ends up with their most preferred partner who didn't accept a subsequent proposal, so if the woman did not receive the proposal again in $O_2$, then the man she originally married in $M_1$ must have ended up with someone he prefers over her in $M_2$. If he ended up with that woman, she must prefer that man over the one she originally married in $M_1$. If that is the case, however, then $M_1$ was never a stable match to begin with, which is a contradiction. This case, therefore, can never happen.
2. The proposal she had originally received from $m_1$ during $O_1$ was once again extended to her during $O_2$, but she rejected it, having already accepted a proposal from $m_2$.
  Case 2: If she did not accept the proposal from $m_1$, then she has already received one from $m_2$, who she prefers over $m_1$, but didn't receive a proposal from in $m_2$. If $m_2$ did not propose to her during $O_1$ but did during $O_2$, his fiance must have ended up with someone she likes better, which means $M_1$ was never a stable matching to begin with, which is a contradiction. This case, therefore, can never happen.
3. The proposal she had originally received from $m_1$ during $O_1$ was once again extended to her during $O_2$, and she accepted it, but later broke things off with $m_1$ after receiving a proposal from $m_2$.
  Case 3: If she prefers $m_2$ over $m_1$, then $m_2$ must not have proposed to her during $O_1$, or else she would have ended up with him and not $m_1$. If $m_2$ proposed to her during $O_2$ however, the woman who originally agreed to marry him during $O_1$ must have ended up with someone she likes better, which means $M_1$ was never a stable matching to begin with, which is a contradiction. This case, therefore, can never happen.
Prove that when we run the G-S algorithm with men proposing, women end up with their worst valid partners.
Answer: Women will accept any proposal that they receive, and will end up with the man they preferred most among those who proposed to her. If a woman prefers another man over her current partner, he must have ended up with someone he prefers better, or else this woman would have received a proposal from him. Therefore, the set of men a woman prefers over the man she ended up with after running Gale Shapley is comprised exclusively of men who are with women they find more preferable.
True or False: In every stable matching that Gale–Shapley algorithm may end up with when men propose, there is a man who is matched to his highest-ranked woman.
Answer: True. Every man will propose to their highest-ranked woman. He may propose to subsequently ranked women, but he is guaranteed to propose to at least his highest ranked woman. The worst case is the one in which all men have the order of preference. All will propose to the same woman first, and she will ultimately reject any proposal she received after the one that came from the man she preferred most.
In a connected bipartite graph, is the bipartition unique? Justify your answer.
Answer: Not necessarily. Consider the following graph:
```
A - B
|   |
C - D
```
This graph contains two distinct bipartitions: {{A, B}, {C, D}} along with {{A, C}, {B, D}}.