CODEWITHSUNDEEP
algorithmcomputer-sciencecomputer-science-theory
BritJam
BritJam

Reputation: 29

Any tips on understanding Stable matching and unstable pairs

enter image description here

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

Upvotes: 0

Views: 943

Answers (1)

Ahx
Ahx

Reputation: 8005

Let's quickly remember Gale-Shapley Algorithm:

    1. One of the two sets is chosen to make proposals.
    • S selects from H.
    1. 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.
    1. 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

Upvotes: 0

Related Questions