Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:deirdre:chapter1 [2014/01/14 21:33] – tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter1 [2014/01/16 15:59] (current) – tobind
@@ Line 17: / Line 17: @@
 Description of the algorithm:
-     Initially all //m ∈ M// and //w ∈ W// are free
+     Initially all m ∈ M and w ∈ W are free
-     While there is a man //m// who is free and hasn't proposed to every woman
+     While there is a man m who is free and hasn't proposed to every woman
-          Choose such a man //m//
+          Choose such a man m
-          Let //w// be the highest-ranked woman in //m//'s preference list to whom //m// has not yet proposed
+          Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed
-          If //w// is free then
+          If w is free then
-               (//m//, //w//) become engaged
+               (m, w) become engaged
-          Else //w// is currently engaged to //m'//
+          Else w is currently engaged to m'
-               If //w// prefers //m'// to //m// then
+               If w prefers m' to m then
-                    //m// remains free
+                    m remains free
-               Else //w// prefers //m// to //m;//
+               Else w prefers m to m;
-                    (//m//, //w//) become engaged
+                    (m, w) become engaged
-                    //m'// becomes free
+                    m' becomes free
                Endif
           Endif
      Endwhile
-     Return the set //S// of engaged pairs
+     Return the set S of engaged pairs
+From looking into the algorithm, we can prove the following things.
+  - w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better (in terms of her preference list)
+  - The sequence of women to whom m proposes gets worse and worse (in terms of his preference list)
+  - The G-S algorithm terminates after at most n^2 iterations of the While loop.
+      - There are only n^2 possible pairs of men and women in total
+  - If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
+  - The set S returned at termination is a perfect matching.
+  - A set of pairs S returned at termination is a stable matching.
+The algorithm shows a certain degree of "unfairness" where one side always ends up happier overall. If the men propose, then their preferences are more likely to be matched; the same goes if we change it so that the women propose.
+**All executions yield the same matching.** First, we will say that a woman is a valid partner of a man if there is a stable matching that contains the pair (//m,w//). //w// is the //best valid partner// of //m// if //w// is a valid partner of //m// and no woman whom //m// ranks higher than //w// is a valid partner of his. We will use //best(m)// to denote this.
+If we let //S*// denote the set of pairs {(//m, best(m)) : m ∈ M//}, we can prove that every execution of the G-S algorithm results in the set //S*//.
+So, for men, the G-S algorithm is ideal (but not ideal for women!). We say that //m// is a valid partner for a woman //w// if there is a stable matching that contains the pair (//m,w//) and that //m// is the //worst valid partner// of //w/ if //m// is a valid partner of //w// and no man whom //w// ranks lower than //m// is a valid partner of hers. So, we can then prove that in the stable matching //S*//, each woman is paired with her worst valid partner.
+I give this a 10 for level of interest. I think the Stable Matching Problem was very cool and also applicable to real-life situations, such as the residents in the hospitals or students looking for internships. There definitely is a very real need for stable matchings to occur. I also realized that an extension of this is most likely what is used by W&L's formal rush process. We've always been told there's a computer program developed by someone at MIT that is used to decide who goes back to what house each night. I can see how this algorithm would be extremely likely to be related because you take into account both the sororities' and the girls' preferences and see how they match with each other. Haley and I talked about this after class one day.