0
$\begingroup$

Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning that the result may differ if the woman ask the men instead of the men asking the women. I have test this and found it to be true, but i can not find any scientific papers on this, so i where hoping that some of you guys might know of one or more?

$\endgroup$
  • $\begingroup$ What research have you done? Wikipedia's article contains references that describe this in more detail, including a citation to the original scientific paper. That should have everything you ever wanted to know. en.wikipedia.org/wiki/Stable_marriage A tip for the future: I expect you to do much more research before asking. Check Wikipedia, use Google, check textbooks, etc. $\endgroup$ – D.W. Jul 18 '14 at 19:24
2
$\begingroup$

One place to look at is the classic book The stable marriage problem. The link provides a relevant excerpt, showing that the matching produced by the standard Gale–Shapley algorithm is male optimal and female pessimal: any man gets the best possible partner (in his view) he can get in any perfect matching, and any woman gets the worst possible partner (in her view) she can get in any perfect matching. If we switch men and women, we will obtain the female optimal, male pessimal matching.

The quoted book, as well as Knuth's book on the subject, contain other material on stable marriages, including the number of different stable marriages, the lattice structure of stable marriages, sampling a random stable marriage, related problems such as the stable roommate problem, and much more.

From another angle, a distinctly different algorithm for the stable marriage problem has been developed by Subramanian and picked up by Feder; see for example Section 6 of this paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.