Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2018:journals:beckg:ch1 [2018/01/15 01:59] – created beckg | courses:cs211:winter2018:journals:beckg:ch1 [2018/01/15 02:21] (current) – [1.1: Stable Matching] beckg | ||
|---|---|---|---|
| Line 5: | Line 5: | ||
| In formulating the problem, simplification becomes extremely helpful. This is done through re-defining it in terms of marriages between men from a set, //M//, and women from set //W//, each with equal numbers (nominally, //n// men and //n// women). Further defining the problem mathematically, | In formulating the problem, simplification becomes extremely helpful. This is done through re-defining it in terms of marriages between men from a set, //M//, and women from set //W//, each with equal numbers (nominally, //n// men and //n// women). Further defining the problem mathematically, | ||
| - | Each man and woman rank all members of the opposing group in a preference list, with no tied rankings. Then, we define a //stable matching// to be a perfect matching in which every couple meets the above definition of being stable. | + | Each man and woman rank all members of the opposing group in a preference list, with no tied rankings. Then, we define a //stable matching// to be a perfect matching in which every couple meets the above definition of being stable. The algorithm function is as follows: |
| + | |||
| + | * Initially, all are unmarried. | ||
| + | * '' | ||
| + | * Let //w// be a woman to whom he hasn't proposed | ||
| + | * //m// proposes to //w// | ||
| + | * If //w// is free: //m// and //w// are engaged | ||
| + | * Else //w// is engaged to other man // | ||
| + | * If //w// prefers // | ||
| + | * Else //w// prefers //m//: //w// and //m// engaged and //m'// now free | ||
| + | |||
| + | Analyzing the algorithm we find and prove (proofs in book) that it: | ||
| + | * terminates after at most // | ||
| + | * always returns a stable matching | ||
| + | * returns the __same__ stable matching after every execution. | ||
| + | |||
| + | Though too long to put into the summary, the proof of the third property is very nice and enjoyable to read. It then leads to the observation that the side that does the proposing ends up with the best possible stable matching from their perspective, | ||
| + | |||
| + | I found this section a 8-9 out of 10 as readable and interesting. I particularly liked the tight adherence to mathematical formalism. | ||
