Differences

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

--- courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/11 22:52] – boyese
+++ courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/22 21:56] (current) – [Section 1.1 : A First Problem: Stable Matching] boyese
@@ Line 1: / Line 1: @@
-===Section 1.1 : A First Problem: Stable Matching===
+====== Chapter 1 ======
+=====Section 1.1 : A First Problem: Stable Matching=====
 The stable matching problem/algorithm attempts to find a stable matching (pairing) between individuals of two sets of the same size given a ranking of preferences for each individual within the set. A matching is a mapping from the elements of one set to the elements of the other set.\\
@@ Line 14: / Line 16: @@
 There are several truths regarding the stable marriage problem that can all be verified by proof by contradiction.\\
 Note that w represents a woman and m represents a man.\\
-.1  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.\\
-.2  The sequence of women to whom m proposes gets worse and worse.\\
-.3  The G-S (Gale-Shapley) algorithm terminates after at most n<sup>2</sup> iterations of the While loop.\\
-.4  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.\\
-.5  The set S returned at termination is a perfect matching.\\
-.6  Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.\\
+.1  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.
+.2  The sequence of women to whom m proposes gets worse and worse.
+.3  The G-S (Gale-Shapley) algorithm terminates after at most n<sup>2</sup> iterations of the While loop.
+.4  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.
+.5  The set S returned at termination is a perfect matching.
+.6  Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.
+A sketch of the Gale-Shapley algorithm follows: \\
+<code>
+Initially all m in M and w in W are free
+While there is a man m who is free and hasn’t proposed to
+every woman
+    Choose such a man m
+    Let w be the highest-ranked woman in m’s preference list
+        to whom m has not yet proposed
+    If w is free then
+        (m, w) become engaged
+    Else w is currently engaged to m’
+        If w prefers m’ to m then
+            m remains free
+        Else w prefers m to m’
+            (m, w) become engaged
+            m' becomes free
+        Endif
+    Endif
+Endwhile
+Return the set S of engaged pairs
+</code>
+My main question while reading this section was, how practical is the stable marriage problem in the real world, if at all? This question was answered by the end of the section, but I am still curious about other applications of the stable matching problem. I thought this section was relatively easy to read and understand after the lecture, but I think if I had read it before the lecture I would have been pretty confused. I found this section to be about a 7 in terms of interestingness on a scale of one to ten because of all the possible real world applications. I'm not sure why it was necessary to prove each of the six lemmas separately in order to understand the problem itself, but this process will probably become more helpful as the algorithms and proofs become more complicated.