Chapter 1

• Summary of the section
  • 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?” The goal was to assign every applicant A to every employer E such that E prefers every accepted applicant to A or A prefers her current employment situation over working for E. From there, we learn how to turn that very broad issue into a clearer problem. We changed from a problem in which there was a potential for asymmetries with employers and applicants (more spots than applicants, multiple spots for applicants but each applicant can only have one job, etc.) to a problem in which n men and n women get married with no instabilities. A matching is only considered stable if it is perfect and there are no instabilities with respect to the set of marriages. Now that the problem was specifically defined, we could formulate the algorithm, which consists of a while loop with if/else statements within it. The loop only terminates when no more men are free.
• 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.
  • 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

      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 algorithm terminates
  • 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 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 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)
• 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

• How readable the section was (a pretty fair 9)