Any tips on understanding Stable matching and unstable pairs

Question

I thought i understood stable matching but am really confused with pairs, can anybody help me understand this simply?

Answer 1

Let's quickly remember Gale-Shapley Algorithm:

---

• 1. One of the two sets is chosen to make proposals.
  • S selects from H.

---

• 2. One individual from the proposing group who is not already selected H will propose to their most preferable option.
  • Hospital

  ---

  • Accept: If it is the hospital's first offer or the S is at better ranking than their current S ranking.

    • For instance: If Whittington's(W) current is Ahmed(A) and Laura(L) proposes for W. L replaced with À

  • Reject: S ranking is worse than their current S ranking.

    • For instance: If Whittington's(W) current is Ahmed(A) and Elena(E) proposes for W. E is rejected.
• 3. When each member of the set is matched, loops terminate.

So:

---

Laura(L) selects Royal Free(R)

Elena(E) selects St. Thomas(T)

Ahmad(A) selects Whittington(W)

Simon(S) selects HighGate(H) ok.

• If Elena(E) selects Royal Free(R), this will create an unstable pair. Since E is accepted. According to the R, E has a higher rank compared to the L.

• If Simon(S) selects Whittington(W), he will be rejected. Since his rank is the lowest according to the W.

• If Ahmad(A) selects St. Thomas(T), he will be rejected. The highest rank of the H is E.

• If Elena(E) selects HighGate(H), she will be rejected. Since her rank is the lowest according to the H.

---

For Gale-Shapley Algorithm

---

For Unstable-pairs