Cheap and Secure Web Hosting Provider : See Now

[Solved]: Stable marriage problem preferential to asking side

, , No Comments
Problem Detail: 

Watching this youtube video: 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?

Asked By : Androme

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback