CSCB36H3 Lecture Notes - Lecture 1: Pseudocode, Stable Marriage Problem, Lloyd Shapley
Document Summary
Suppose we are given n women w1, w2, . , wn and n men m1, m2, . Furthermore, each individual (man or woman) orders all n individuals of the opposite sex in strictly decreasing preference . (we do not allow ties, where a person likes equally well two members of the opposite sex. ) A matching m is an assignment of exactly one man to each woman. (since there are equally many women and men, a matching is also an assignment of exactly one woman to each man. ) If m is assigned to w (or, conversely, w is assigned to m) in a matching m , we say that w and m are married in m . 1. There are n! possible matchings; we would like to nd a good matching that re ects the preferences of the individuals. There are various ways one can de ne a good matching; a desirable property is stability.
