Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 21:34] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 22:29] (current) – mugabej
@@ Line 38: / Line 38: @@
   * The G-S algorithm terminates after at most n<sup>2</sup> iterations of the while loop at which point there is no free man
   * 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.
-  * The set S returned at termination is a perfect matching. S is also a stable matching.
+  * The set S returned at termination is a perfect matching. S is also a stable matching.\\
+=== Extensions===
+  * If all men list different women as their first choice, then in all runs of the G-S algorithm, all men end up matched with their first choice,independent of the preferences of the women. If the women's preferences completely clash with the men 's preferences, then the resulting stable matching is as bad as possible for the women. Thus someone is destined to end up unhappy: women are unhappy if men propose, and men are unhappy if women propose. The G-S algorithm is therefore unfair as it favors the group that proposes.
+  * All executions of the G-S algorithm yield the same matching. Each man ends up with the best possible partner as long as all men prefer different women.
+      * A woman //w// is a //valid partner// of man //m// if there is a stable matching that contains the pair (//m,w//).
+      * //w// is the // best valid partner // of // m//  if // w//  is a // valid partner// of // m// and no woman whom // m//  ranks higher than // w//  is his // valid partner// . The notation // best(m)//  denotes the // best valid partner//  of // m// .
+      * If we let S* denote the set of pairs {(// m,best(m)// ):// m// in M}, every execution of the G-S algorithm results in the set S*.
+      * For a woman // w// , // m//  is a // valid partner//  if there is a stable matching that contains the pair (// m,w// ). // m//  is the // worst valid partner//  of // w// if // m//  is a valid partner of // w//  and no man whom // w//  ranks lower than // m//  is a valid partner of hers.
+      * In the stable matching S*, each woman is paired with her // worst valid partner// .
+\\
+\\
+After re-reading this section, I still think that it is very hard to implement an algorithm that may satisfy both those who propose and those who are proposed to. In practice,it's hard to have a stable matching.Also, when the size of the individuals increases( if we go back to the applicants and companies/colleges), the problem increases its complexity and the solution becomes harder to find. So the question I have is: To what extent can this solution be extended to solve the more complex problem involving applicants/companies?\\
+After re-reading this section, I appreciated even more the way the approach of this problem was made: from a clearly complex problem, devise a simpler version of the problem whose solution may extend to the more complex problem. It's a very admirable process that is really useful in solving most of the problems.\\
+The reading was interesting but I had trouble progressing at times. I give this section a 7 out of 10.