6.042J Lecture Notes - Lecture 23: Stable Marriage Problem, Akamai Technologies, F. Thomson Leighton
Document Summary
That is, jennifer might like brad best, but brad doesn"t necessarily like jennifer best. The goal is to marry everyone: every man must marry exactly one woman and vice-versa. Moreover, we would like to nd a matching between men and women that is stable in the sense that there is no pair of. No polygamy and heterosexual marriages only. who prefer one another to their spouses. For example, suppose brad likes angelina best, and angelina likes brad best, but brad and angelina are married to other people, say jennifer and billy bob. Now brad and angelina prefer each other to their spouses, which puts their marriages at risk. More generally, in any matching, a man and woman who are not married to each other and who like each other better their spouses is called a rogue couple. That is, brad and angelina would be a rogue couple.