Differences

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

--- courses:cs211:winter2014:journals:colin:chapter1 [2014/01/09 02:02] – created mohnacsc
+++ courses:cs211:winter2014:journals:colin:chapter1 [2014/01/16 07:02] (current) – Initial commit mohnacsc
@@ Line 1: / Line 1: @@
 ===== Chapter 1: Introduction =====
-=== 1.1 - Stable Matching ===
+==== 1.1 - Stable Matching ====
+The Stable Matching Problem was created by David Gale and Lloyd Shapley in 1962 based on the question: //Could one design a college admissions process, or a job recruiting process, that was self-enforcing?//
+Concerns with the process:
+Better offers come along and change the matching of applicants, causing a domino effect
+Both applicants and employers must be happy to maintain a stable state.  One of the two must hold true:
+  * E prefers every one of its accepted applicants to A; or
+  * A prefers her current situation over working for employer E
+=== The Problem ===
+Consider matching men and women where set M = {m(1),m(2),…,m(n)} represents n men and set W = {w(1),w(2),…w(n)} represents n women.
+M X W denotes the set of all ordered pairs of the form (m, w).
+A matching S is a set of ordered pairs with the property that each member of M and W appears in at most one pair in S.  A perfect matching S’ is a matching with the property that each member of M and W appears in exactly one pair in S’.
+Preferences must also be accounted for - in this problem, men rank all women.  For example: m  of (m,w) and w’ of (m’,w’) may prefer each other to their matching in S.  In this case, the matching is unstable.
+Matching S is stable if:
+  * It is perfect
+  * There is no instability with respect to S
+=== Designing the Algorithm ===
+Basic ideas:
+  * Initially, every person is free.  During the matching process, pairs may enter a state of engagement.
+  * If an engaged women w of pair (m,w) receives a more preferred offer from m’, she becomes engaged to m’ and m becomes free.
+  * The algorithm terminates when no one is free.
+Concrete description of Gale-Shapley algorithm:
+<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>
+=== Analyzing the Algorithm ===
+w remains engaged from first proposal, and her partners increase in terms of preference.
+The sequence of women to whom m proposes gets worse in terms of preference.
+The G-S algorithm terminates after at most n^2 iterations of the while loop.
+  * Proof:  Each iteration is a man proposing to a new woman.  There are only n^2 possible pairs of men and women and so only n^2 iterations at most.
+If m is free at some point, then there remains a free w
+The set S returned at termination is a perfect matching
+  * Proof:  At termination, m must have proposed to every woman, otherwise the while loop would not have exited.  This contradicts the statement that there can’t be a free man who has proposed to every woman.
+Consider and execution of the G-S algorithm that returns a set of pairs S.  The set S is a stable matching.
+  * Proof:  Because S is a perfect matching, an instability is assumed to create a contradiction.  We must prove that (i) m prefers w’ to w or (ii) w’ prefers m to m’.  Following the proven statements above, it concludes that S is a stable matching.
+All executions yield the same matching, set S*.
+  * Proof:  Suppose that an execution resulted in a match with a woman who is not his valid partner.  Since men propose in descending order of preference, this means the man is rejected because the woman has a preferred partner or he was left for a preferred partner.  Either way, w continues an engagement to a man.  Because the matching must adhere to the code of descending preference, this statement becomes a contradiction.
+In the stable matching S*, each woman is paired with her worst valid partner.
+  * Proof:  Suppose there were a pair (m, w) in S* where m is not the worst valid partner.  Then there is a stable matching with a man m’ who she likes less than m.  In this situation, m is paired with a woman w’; since w is the best valid partner of m, and w’ is a valid partner of m, we see that m prefers w to w’.  This shows an instability in the stable matching, leading to a contradiction.
+From this we can conclude that the gender doing the proposing ends up with a more desirable stable matching.
-=== 1.2 - Five Representative Problems ===