Chapter 1

• Summary of the section
• Motivations for the given problem
  • 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.
  • 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.
• brief sketch of algorithm, intuition, and implementation (including runtime)
  • 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
    • there could be less applicants than spots to fill
    • each applicant may not apply to every company
  • This is why it is useful to strip the problem down and turn it into an easier version of the problem.
    • There are n applicants and n employers. Each company wants a single employer. Each applicant applies to all employers and ranks them on a preference list. The employers rank all of the applicants.
  • 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.

Gale-Shapely Algorithm

      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
               choose such a man m
               w = highest ranked woman in m’s preferences to whom m has not yet proposed
               if w is free:
                      (m, w) become engaged
               else w is currently engaged to m’:
                      if w prefers m’ to m:
                             m remains free (w remains engaged to m’)
                      else w prefers m to m’:
                             (m, w) become engaged
                             m’ becomes free
       return the set S of engaged pairs

• Observations
  • 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's sequence of partners to which she is engaged gets better and better
  • 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
  • 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
• Further Anlysis
  • “unfairness” phenomenon
    • the algorithm favors the men (those who propose in the heteronormative execution of the algorithm)
    • someone is destined to end up unhappy: women are unhappy if men propose, and me are unhappy if women propose
  • all executions yield the same matching
    • every execution of the G-S algorithm results in the set S*
    • despite the fact that the algorithm runs asynchronously, there is no variability in the final result of the algorithm
    • Proof: assume that some execution E of the G-S algorithm results in a matching S in which some man is paired with a woman who is not his best valid partner
      • Since men propose in decreasing order of preference, some man is rejected by a valid partner during E
      • Consider the first moment in E in which m is rejected by valid partner w (w is m’s best valid partner best(m))
      • Rejection of m by w happened either because m proposed and was turned down in favor of w’s existing partner, or w got a better proposal and broke the engagement
      • Since w is a valid partner of m, there is a stable matching S’ containing the pair (m, w)
      • Since rejection of m was the first rejection, m’ had not yet been rejected by any valid partner at the point in E when he became engaged to w
      • Since he proposed in decreasing order of preference, since w’ is a valid partner of m’, must be the m’ prefers w to w’
      • However, we have already seen that w prefers m’ to m for in E she rejected m in favor of m’
      • 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
  • 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 in the G-S algorithm ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching

• Questions I have about motivation/solution/proofs/analysis
  • Would the same stable matchings occur if the women got to pick first?
• Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa)
• Notes on the section (stuff to remember)
• How readable the section was (a pretty fair 9)