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:41] – [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 58: | Line 64: | ||
| * 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 | * In the stable matching S*, each woman is paired with her worst valid partner | ||
| - | * General phenomenon: for any input, the side that does the proposing | + | * General phenomenon: for any input, the side that proposes |
| + | |||
| + | ==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 | + | |
