Tag Archives: Sanjeev Motwani

Test Your Intuition (19): The Advantage of the Proposers in the Stable Matching Algorithm

Posted on April 9, 2013 by

Stable mariage The Gale-Shapley stable matching theorem and the algorithm. GALE-SHAPLEY THEOREM Consider a society of n men and n women and suppose that every man [and every woman] have a preference (linear) relation on the women [men] he [she] knows. Then … Continue reading →

Posted in Combinatorics, Games, Probability, Test your intuition | Tagged , , , , , , | 7 Comments