Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:goldm:ch1 [2018/01/17 00:13] – goldm | courses:cs211:winter2018:journals:goldm:ch1 [2018/01/17 00:18] (current) – goldm |
|---|
| This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: "Could one design a college admissions process, or a job recruiting process, that was | This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: "Could one design a college admissions process, or a job recruiting process, that was |
| self-enforcing?" This algorithm can also be illustrated by matching groups of people into "couples" so that they all are matched with the best possible individual to lead to a stable relationship environment. The remainder of the section goes on to discuss implementation and results of the algorithm and related proofs which will be discussed after this summary. | self-enforcing?" This algorithm can also be illustrated by matching groups of people into "couples" so that they all are matched with the best possible individual to lead to a stable relationship environment. The remainder of the section goes on to discuss implementation and results of the algorithm and related proofs which will be discussed after this summary. |
| As aforementioned, the motivation for the problem is to develop a college admissions/job recruitment process that self-enforced and avoided people "jumping ship" to other opportunities. | |
| | As aforementioned, the motivation for the problem is to develop a college admissions/job recruitment process that self-enforced and avoided people "jumping ship" to other opportunities. |
| Here is a sketch of the algorithm as given by the text: | Here is a sketch of the algorithm as given by the text: |
| Initially all m E M and w E W are free | Initially all m E M and w E W are free |
| Endif | Endif |
| Endif | Endif |
| Endwhile | Endwhile |
| Return the set S of engaged pairs | Return the set S of engaged pairs |
| | |
| | The algorithm runs in n squared. |
| | |
| | I found the discussion in class much more enlightening than the reading, and as such, I give this reading a 2/10. |
| | |
