Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter1 [2018/01/14 21:39] – [1.1: Stable Matching] nasona | courses:cs211:winter2018:journals:nasona:chapter1 [2018/01/16 00:06] (current) – [1.1: Stable Matching] nasona | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ======= Chapter 1 ======= | ======= Chapter 1 ======= | ||
| ===== 1.1: Stable Matching ===== | ===== 1.1: Stable Matching ===== | ||
| - | * Summary of the section | + | ==Summary of the Section== |
| - | * Motivations | + | * We start off with the question of "is there a way to make have a college admission process or a job application process self-enforcing?" |
| + | |||
| + | ==Motivations for the Given Problem== | ||
| * Can one design a college admission process, job application process, etc. that is self-enforcing? | * Can one design a college admission process, job application process, etc. that is self-enforcing? | ||
| * Many things can go wrong in these processes if nothing is there to enforce the status quo; the system risks breaking down if people act in their own self-interest and make deals behind the scenes. | * Many things can go wrong in these processes if nothing is there to enforce the status quo; the system risks breaking down if people act in their own self-interest and make deals behind the scenes. | ||
| * The goal was to assign every applicant A to every employer E such that there are no unstable matches. E prefers every accepted applicant to A or A prefers her current employment situation over working for E. | * The goal was to assign every applicant A to every employer E such that there are no unstable matches. E prefers every accepted applicant to A or A prefers her current employment situation over working for E. | ||
| * It is important that there are no unstable matches because there would be nothing keeping an unstable match from making a behind the scene deal to accommodate their personal interests. Then, the system would break down. | * It is important that there are no unstable matches because there would be nothing keeping an unstable match from making a behind the scene deal to accommodate their personal interests. Then, the system would break down. | ||
| - | * brief sketch | + | |
| + | ==The Construction | ||
| * There are some distracting asymmetries in this problem: | * There are some distracting asymmetries in this problem: | ||
| * each applicant is looking for a single employer, but the each employer could be looking to fill multiple spots with applicants | * each applicant is looking for a single employer, but the each employer could be looking to fill multiple spots with applicants | ||
| Line 16: | Line 19: | ||
| * This problem with that we've manipulated into a special case can be viewed as a problem in which n men and n women end up married. So from this point forward, I will refer to the problem in this sense. | * This problem with that we've manipulated into a special case can be viewed as a problem in which n men and n women end up married. So from this point forward, I will refer to the problem in this sense. | ||
| * Our Goal: a set of n marriages with no instabilities. A match is considered stable if it is perfect and there is no instability with respect to the set of marriages. | * Our Goal: a set of n marriages with no instabilities. A match is considered stable if it is perfect and there is no instability with respect to the set of marriages. | ||
| + | * We are given that there are n men and n woman, we are given their preference lists, and we are going based on the assumption that at the beginning everyone is single. | ||
| - | Gale-Shapely Algorithm | + | ==Gale-Shapely Algorithm== |
| initially all m in M and w in W are free | initially all m in M and w in W are free | ||
| - | while there is a man m who is free and hasn’t proposed to every woman | + | while there is a man m who is free and hasn’t proposed to every woman: |
| | | ||
| w = highest ranked woman in m’s preferences to whom m has not yet proposed | w = highest ranked woman in m’s preferences to whom m has not yet proposed | ||
| Line 32: | Line 36: | ||
| | | ||
| - | * Observations | + | ==Observations== |
| * the runtime of this algorithm is n^2 because there are at most n^2 matches of men and women | * the runtime of this algorithm is n^2 because there are at most n^2 matches of men and women | ||
| * w remains engaged from the point at which she receives her first proposal | * w remains engaged from the point at which she receives her first proposal | ||
| Line 38: | Line 42: | ||
| * m's sequence of partners to which she is engaged gets worse and worse | * m's sequence of partners to which she is engaged gets worse and worse | ||
| * if m is free at some point in the algorithm, then there is a w that he has not yet proposed to | * if m is free at some point in the algorithm, then there is a w that he has not yet proposed to | ||
| + | * the algorithm terminates | ||
| * the set S returned at termination is a perfect match | * the set S returned at termination is a perfect match | ||
| * consider an execution of the G-S algorithm that returns a set of pairs S, which is a stable matching | * consider an execution of the G-S algorithm that returns a set of pairs S, which is a stable matching | ||
| - | * Further Anlysis | + | |
| + | ==Further Anlysis== | ||
| * “unfairness” phenomenon | * “unfairness” phenomenon | ||
| * the algorithm favors the men (those who propose in the heteronormative execution of the algorithm) | * the algorithm favors the men (those who propose in the heteronormative execution of the algorithm) | ||
| Line 57: | Line 63: | ||
| * Since (m’, w) is not in S’, it follows that (m’, w) is an instability in S’ | * Since (m’, w) is not in S’, it follows that (m’, w) is an instability in S’ | ||
| * This contradicts our claim that S’ is stable and therefore contradicts our initial assumption | * This contradicts our claim that S’ is stable and therefore contradicts our initial assumption | ||
| + | * In the stable matching S*, each woman is paired with her worst valid partner | ||
| + | * General phenomenon: for any input, the side that proposes in the algorithm ends up with the best possible stable matching (from their view), while the side that does not propose ends up with the worst possible stable matching | ||
| + | |||
| + | ==Questions== | ||
| + | * Would the same stable matchings occur if the women got to propose as when the men proposed? | ||
| + | * Does the runtime of the algorithm change at all if we bring back in the asymmetries? | ||
| + | ==Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa)== | ||
| + | * After walking through the the termination proof, it became clearer how the text came to the conclusion that the algorithm' | ||
| + | ==Stuff to remember== | ||
| + | * Matching S: a set of ordered pairs, each from M x W, with the property that each member of M and each member of W appears in at most one pair in S | ||
| + | * Perfect matching S’: a matching with the property that each member of M and each member of W appears in exactly one pair in S’ | ||
| + | * Example of an unstable matching | ||
| + | * Perfect Matching S: (m, w) and (m’, w’) however m prefers w’ to w and w’ prefers m to m’ | ||
| + | * nothing to stop m and w’ from abandoning their current partners and heading off together; the set of marriages is not self-enforcing | ||
| + | * Therefore, (m, w’) is an instability with respect to S | ||
| - | * Questions I have about motivation/ | + | ==How Readable the Section was== |
| - | * Would the same stable matchings occur if the women got to pick first? | + | * On a scale of 1 to 10, this section |
| - | * Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa) | + | |
| - | * Notes on the section (stuff | + | |
| - | * How readable | + | |
