Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 15:42] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 22:13] (current) – devlinn
@@ Line 1: / Line 1: @@
 ====== Chapter 1: Introduction ======
-===== 1.1 A First Problem: Stable Matching =====
+==== 1.1 A First Problem: Stable Matching ====
 The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:
     * "Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E, and every applicant A who is not scheduled to work for E...[either] E prefers every one of its accepted applicants to A; or A prefers her current situation over working for employer E."
-In order to simplify the problem, we can assume there is a 1:1 ratio of applicants to companies, so each applicant will only be matched at one company. Two terms are important in this problem and in the study of algorithms as a whole. Consider two sets, X and Y:
+In order to simplify the problem, we can assume there is a 1:1 ratio of applicants to companies, so each applicant will only be matched at one company. Two terms are important in this problem and in the study of algorithms as a whole. Consider two sets, M and W:
-    * //matching//: a set of ordered pairs, composed from X and Y, where each item of X and each item of Y occurs at most once
+    * //matching//: a set of ordered pairs, composed from M and W, where each item of M and each item of W occurs at most once
-    * //perfect matching//: a matching such that each item in X and each item in Y occurs exactly once
+    * //perfect matching//: a matching such that each item in M and each item in W occurs exactly once
-A stable matching occurs when a matching is both perfect and contains no instability. It is important to note that an instance can have multiple stable matchings.
+A stable matching occurs when a matching is both perfect and contains no instability. It is important to note that an instance can have multiple stable matchings. The Gale-Shapley algorithm can be roughly sketched as follows:
+    Start all m ∈ M and w ∈ W are available for proposal
+    While man m not proposed to every woman:
+        Choose m
+        Let w be highest-ranked woman for m that m has not
+            proposed to
+        If w available:
+            (m, w) engaged
+        Else w engaged to m':
+            If w prefers m' to m:
+                m remain available
+            Else w prefers m to m':
+                (m, w) become engaged
+                m' become available
+    Return S (set of engaged pairs)
+The runtime of this algorithm is at most n<sup>2</sup> iterations. Another interesting fact of the Gale-Shapley algorithm is that all executions return the same matching, one in which each m ∈ M is paired with its ideal w (provided no overlapping preferences). However, for all w ∈ W, their pairings are the worst possible m.
+I am interested by the claims being proved in this section; I do not always see the relevance in their arguments. I would assume the purpose is to illustrate the trends and facts of this algorithm. I found this section to provide a strong introduction to algorithms in a simple manner using an understandable example.