[[courses:cs211:winter2018:journals:nasona:chapter1]]
Trace: • sidebar • chapter1 • chapter1 • preface • chapter4 • chapter2 • chapter3 • chapter3 • chapter3 • chapter7
Show page
Recent ChangesSitemap

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
courses:cs211:winter2018:journals:nasona:chapter1 [2018/01/14 21:53] – [1.1: Stable Matching] nasonacourses:cs211:winter2018:journals:nasona:chapter1 [2018/01/16 00:06] (current) – [1.1: Stable Matching] nasona
Line 1: Line 1:
 ======= Chapter 1 ======= ======= Chapter 1 =======
 ===== 1.1: Stable Matching ===== ===== 1.1: Stable Matching =====
-  * Summary of the section +==Summary of the Section== 
-  * Motivations for the given problem+    * We start off with the question of "is there a way to make have a college admission process or a job application process self-enforcing?" The goal was to assign every applicant A to every employer E such that E prefers every accepted applicant to A or A prefers her current employment situation over working for E. From there, we learn how to turn that very broad issue into a clearer problem. We changed from a problem in which there was a potential for asymmetries with employers and applicants (more spots than applicants, multiple spots for applicants but each applicant can only have one job, etc.) to a problem in which n men and n women get married with no instabilities. A matching is only considered stable if it is perfect and there are no instabilities with respect to the set of marriages. Now that the problem was specifically defined, we could formulate the algorithm, which consists of a while loop with if/else statements within it; the loop only terminates when no more men are free. The runtime of the algorithm is n^2. After designing the algorithm, we analyzed it. Some of the observations we made were w remains engaged from the point at which she receives her first proposal, w's sequence of partners to which she is engaged gets better and better, and m's sequence of partners to which she is engaged gets worse and worse among others. Finally, we further analyzed and proved that there is an unfairness phenomenon that favors the group that proposes and all executions of the algorithm yield the same matching. 
 + 
 +==Motivations for the Given Problem==
     * Can one design a college admission process, job application process, etc. that is self-enforcing?     * Can one design a college admission process, job application process, etc. that is self-enforcing?
     * Many things can go wrong in these processes if nothing is there to enforce the status quo; the system risks breaking down if people act in their own self-interest and make deals behind the scenes.     * Many things can go wrong in these processes if nothing is there to enforce the status quo; the system risks breaking down if people act in their own self-interest and make deals behind the scenes.
     * The goal was to assign every applicant A to every employer E such that there are no unstable matches. E prefers every accepted applicant to A or A prefers her current employment situation over working for E.     * The goal was to assign every applicant A to every employer E such that there are no unstable matches. E prefers every accepted applicant to A or A prefers her current employment situation over working for E.
     * It is important that there are no unstable matches because there would be nothing keeping an unstable match from making a behind the scene deal to accommodate their personal interests. Then, the system would break down.     * It is important that there are no unstable matches because there would be nothing keeping an unstable match from making a behind the scene deal to accommodate their personal interests. Then, the system would break down.
-  * brief sketch of algorithm, intuition, and implementation (including runtime)+ 
 +==The Construction of the Gale-Shapely Algorithm==
     * There are some distracting asymmetries in this problem:      * There are some distracting asymmetries in this problem: 
       * each applicant is looking for a single employer, but the each employer could be looking to fill multiple spots with applicants        * each applicant is looking for a single employer, but the each employer could be looking to fill multiple spots with applicants 
Line 18: Line 21:
     * We are given that there are n men and n woman, we are given their preference lists, and we are going based on the assumption that at the beginning everyone is single.     * We are given that there are n men and n woman, we are given their preference lists, and we are going based on the assumption that at the beginning everyone is single.
  
-Gale-Shapely Algorithm+==Gale-Shapely Algorithm==
         initially all m in M and w in W are free         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+        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
                  w = highest ranked woman in m’s preferences to whom m has not yet proposed                  w = highest ranked woman in m’s preferences to whom m has not yet proposed
Line 33: Line 36:
          return the set S of engaged pairs          return the set S of engaged pairs
  
-  * Observations+==Observations==
     * the runtime of this algorithm is n^2 because there are at most n^2 matches of men and women     * the runtime of this algorithm is n^2 because there are at most n^2 matches of men and women
     * w remains engaged from the point at which she receives her first proposal     * w remains engaged from the point at which she receives her first proposal
Line 42: Line 45:
     * the set S returned at termination is a perfect match     * the set S returned at termination is a perfect match
     * consider an execution of the G-S algorithm that returns a set of pairs S, which is a stable matching     * consider an execution of the G-S algorithm that returns a set of pairs S, which is a stable matching
-  * Further Anlysis+ 
 +==Further Anlysis==
     * “unfairness” phenomenon     * “unfairness” phenomenon
       * the algorithm favors the men (those who propose in the heteronormative execution of the algorithm)       * the algorithm favors the men (those who propose in the heteronormative execution of the algorithm)
Line 62: Line 66:
       * General phenomenon: for any input, the side that proposes in the algorithm ends up with the best possible stable matching (from their view), while the side that does not propose ends up with the worst possible stable matching       * General phenomenon: for any input, the side that proposes in the algorithm ends up with the best possible stable matching (from their view), while the side that does not propose ends up with the worst possible stable matching
  
-  * Questions I have about motivation/solution/proofs/analysis +==Questions== 
-    * Would the same stable matchings occur if the women got to pick first? +    * Would the same stable matchings occur if the women got to propose as when the men proposed? 
-  * Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa) +    * Does the runtime of the algorithm change at all if we bring back in the asymmetries? What if there are less applicants than spots? Then the algorithm would have to change, right? What if hospitals hire more than one applicant, then would that also have to be a new algorithm? 
-  * Stuff to remember+ 
 +==Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa)== 
 +    * After walking through the the termination proof, it became clearer how the text came to the conclusion that the algorithm's runtime was n^2, which is because there is a maximum of n^2 possible proposals. Moreover, the proof that the algorithm produces a perfect matching was also clearer after walking through it in class because the book presents proofs in a paragraph form, where as in class the proofs are presented as more of a bullet-point, sentence by sentence walk through. The slides cut out the "fluff" that the book uses when making the proofs multiple paragraphs long. Similarly, when we proved in class that the algorithm produces a stable matching, it also made more sense in class than when I read it in the book. I think sometimes its easy to get lot when lots of symbols and letters are presented in a clumpy paragraph, whereas in class proofs are presented in a more linear form. 
 + 
 +==Stuff to remember==
     * Matching S: a set of ordered pairs, each from M x W, with the property that each member of M and each member of W appears in at most one pair in S     * Matching S: a set of ordered pairs, each from M x W, with the property that each member of M and each member of W appears in at most one pair in S
     * Perfect matching S’: a matching with the property that each member of M and each member of W appears in exactly one pair in S’     * Perfect matching S’: a matching with the property that each member of M and each member of W appears in exactly one pair in S’
Line 73: Line 81:
         * Therefore, (m, w’) is an instability with respect to S         * Therefore, (m, w’) is an instability with respect to S
  
- +==How Readable the Section was== 
-  * How readable the section was (a pretty fair 9)+    * On a scale of 1 to 10, this section was a 8 because I thought that the book did a good job of explaining the process of constructing and analyzing an algorithm start to finish. The only reason it wasn't a 10 is because some of the proofs were a little hard to follow and highly repetitive.
courses/cs211/winter2018/journals/nasona/chapter1.1515966793.txt.gz · Last modified: by nasona
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0