6.042J/18.062J 15. Stable Matching

1 Albert R Meyer, March 8, 2010 lec 6M.1 Mathematics for Computer Science MIT 6.042J/18.062J Stable MatchingClip art in this lecture © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.2 Clip art in this lecture © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.3 Albert R Meyer, March 8, 2010 Stable Marriage Stable Marriage Problem: Marry everyone without any rogue couples! lec 6M.14 Albert R Meyer, March 8, 2010 Stable Marriage More than a puzzle: College Admissions (original Gale & Shapley paper, 1962) Matching Hospitals & Residents. Matching Dance Partners. lec 6M.20 Albert R Meyer, March 8, 2010 Stable Marriage lec 6M.21 Albert R Meyer, March 8, 2010 lec 6M.22 The Mating Ritual (day by day) Photograph of dancing students removed due to copyright restrictions. Clip art in this lecture © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.4 Albert R Meyer, March 8, 2010 Mating Ritual Stop when no girl rejects. Each girl marries her favorite suitor (if any). lec 6M.26 Albert R Meyer, March 8, 2010 Mating Ritual Termination: there exists a Wedding Day. Partial Correctness: •everyone is married. •marriages are stable. lec 6M.27 Albert R Meyer, March 8, 2010 Stable Marriage: termination total # remaining names on boy’s lists: strictly decreasing & N-valued So Wedding Day lec 6M.28 Albert R Meyer, March 8, 2010 Mating Ritual: girls improve Lemma: A girl’s favorite tomorrow will be at least as desirable as today’s. …because today’s favorite will stay until she rejects him for someone better. lec 6M.31 Clip art in this lecture © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.5 Albert R Meyer, March 8, 2010 ( favorite(G) is weakly increasing for each G) lec 6M.32 Lemma: A girl’s favorite tomorrow will be at least as desirable as today’s. Mating Ritual: girls improve Albert R Meyer, March 8, 2010 …because boys work straight down their lists. lec 6M.33 Lemma: A boy’s 1st love tomorrow will be no more desirable than today’s. Mating Ritual: boys get worse Albert R Meyer, March 8, 2010 lec 6M.34 Lemma: A boy’s 1st love tomorrow will be no more desirable than today’s. ( serenading(B) is weakly decreasing for each B) Mating Ritual: boys get worse Albert R Meyer, March 8, 2010 Mating Ritual: invariant If G is not on B’s list, then she has a better current favorite. Proof: When G rejected B she had a better suitor, and favorite (G) is weakly increasing. lec 6M.35 Albert R Meyer, March 8, 2010 •Each girl has 1 suitors (by def of wedding day) •Each boy is married, or has no girls on his list lec 6M.36 On Wedding Day Albert R Meyer, March 8, 2010 Mating Ritual: everyone marries Everyone is married on wedding day Proof: by contradiction. If B is not married, his list is empty. By Invariant, all girls have favorites better than B --so they do have a favorite. lec 6M.37 That is, all girls are married, so all boys are married. 6 Albert R Meyer, March 8, 2010 Mating Ritual: stable marriages Marriages are Stable: Bob won’t be in rogue couple with case 1: a girl G on his final list, since he’s already married to the best of them. lec 6M.38 Albert R Meyer, March 8, 2010 Mating Ritual: stable marriages Marriages are Stable: Bob won’t be in rogue couple with case 2: a girl G not on his list, since by invariant, G likes her spouse better than Bob. lec 6M.39 Albert R Meyer, March 8, 2010 Mating Ritual Girls’ suitors get better, and boy’s sweethearts get worse, so girls do better? Who does better, boys or girls? No! lec 6M.40 Albert R Meyer, March 8, 2010 Boy Optimal Mating Ritual is Optimal for all Boys at once. Pessimal for all Girls. lec 6M.41 Albert R Meyer, March 8, 2010 Stable Marriage •other stable marriages possible? More questions, rich theory •do better by lying? boys -No! girls -Yes! lec 6M.47 -can be many Albert R Meyer, March 8, 2010 Team Problems Problems 1􀀁4 lec 6M.48 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.