Differences

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

--- courses:cs211:winter2014:journals:emily:home [2014/01/22 02:29] – [Computational Tractability] hardye
+++ courses:cs211:winter2014:journals:emily:home [2014/04/01 23:04] (current) – [6.1, 6.2, 6.3, 6.4] hardye
@@ Line 1: / Line 1: @@
 ====== Emily's Journal ======
+===== Journal Entries Listed In Order: =====
-====  The Stable Matching Problem - Gale and Shapely ====
+===== Preface, 1.1, 2.1, 2,2 =====
-    * design an admissions/recruiting process that was self-enforcing
+[[courses:cs211:winter2014:journals:emily:entryone|First Entry]]
-    * based on matching preference lists
-    * if the process is based on self interests, then there will be situations where people will commit and possibly go back on their commitments if a better offer comes along (retract and redirect)
-    * question asked: given a list of preferences can we assign applicants to employers so at least one of the following is the case
-      * the employer prefers one of its accepted applicants to another
-      * the applicant prefers her current situation over working for another employer
-  * Formulating the Problem
-    * to eliminate complications we assume that each n applicants applies to each n companies and each company accepts one applicant -> we will use the case of devising a system of matching males and females for marriage
-    * a matching S is a set of ordered pairs from the sets of M men and W women where each member of M and W appears in at most 1 pair
-    * a perfect matching S' is a matching where each member of M and W appears in **exactly** one pair in S'
-      * there is neither single hood nor polygamy
-    * each M and W creates a preference list where they rank the opposite gender
-    * **instability** a pair is unstable if one of the pair prefers another male/female
-      * it is possible for an instance to have more than one stable matching
-  * Designing the Algorithm
-    * women will naturally accept an engagement even if she prefers another male
-    * if a free m proposes to a woman w who is already engaged to m', she may accept the proposal from m if he ranks higher than m' on her preference list
-    * the algorithm will stop when everyone is engaged.
-  * Analyzing the Algorithm
-    * from the view of the woman
-      * once w is engaged she will remain engaged to a sequence of men who get higher on her ranking list as they propose
-    * from the view of a man
-      * as m proposes, the sequence of women he proposes to gets lower on his list of ranked women
-    * **maximum iterations needed for termination is n^2**
-      * PROOF:
-        * measure the progress- way of saying each step of the algorithm brings it closer to termination
-        * each iteration is a man proposing to a woman he has never proposed to before -> P(t) denotes the set of pairs (m,w) where m has proposed to w by the end of the iteration t
-        * there are only n^2 possible pairs of men and women total so P() can only increase n^2 times over the whole algorithm
-    * How do we show that the set S at the end of termination is a perfect matching?
-      * if a man is free at some point during the algorithm then there is a women he has not proposed to
-        * proof by contradiction
-      * the set of engaged pairs always forms a perfect matching because the algorithm cannot terminate with a free man
-    * How do we prove that the algorithm returns a set of stable matching?
-      * we already know that S is a perfect matching so by way of contradiction we prove that S is a stable matching. (if m did not proposed to w then w' must be higher on his preference list)
-  * there is an unfairness in the algorithm that favors male preferences over female
-  * question do all executions of the algorithm yield the same matching? ... YES!
-    * characterize the matching by showing each man gets the "best possible partner"
-    * a woman, w,  is a //valid partner// for m if there is a stable matching with the pair (m, w)
-    * the order of the proposals in the algorithm has no effect on the final outcome
-    * PROOF
-      * by way of contradiction prove that S' is stable
-    * in this stable matching each woman is paired with her //worst// valid partner
-===== Chapter Two =====
+===== 2.3, 2.4, 2.5 =====
+[[courses:cs211:winter2014:journals:emily:entrytwo|Second Entry]]
+===== 3.1, 3.2., 3.3 =====
+[[courses:cs211:winter2014:journals:emily:entrythree|Third Entry]]
+===== 3.4, 3.5, 3.6, 4.1  =====
+[[courses:cs211:winter2014:journals:emily:entryfour|Fourth Entry]]
+===== 4.2, 4.4, 4.5, 4.6 =====
+[[courses:cs211:winter2014:journals:emily:entryfive|Fifth Entry]]
+===== 4.7, 4.8, 5.1 =====
+[[courses:cs211:winter2014:journals:emily:entrysix|Sixth Entry]]
+===== 5.2, 5.3, 5.4 =====
+[[courses:cs211:winter2014:journals:emily:entryseven|Seventh Entry]]
+===== 6.1, 6.2, 6.3, 6.4 =====
+[[courses:cs211:winter2014:journals:emily:entryeight|Eighth Entry]]
+===== 7.1, 7.2, 7.5, 7.7 =====
+[[courses:cs211:winter2014:journals:emily:entrynine|Ninth Entry]]