Chapter 1

• 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. The runtime of the algorithm is n^2. After designing the algorithm, we analyzed it. Some of the observations we made were 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, and m's sequence of partners to which she is engaged gets worse and worse among others. Finally, we further analyzed and proved that there is an unfairness phenomenon that favors the group that proposes and all executions of the algorithm yield the same matching.

• 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.

• 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.

      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

• 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

• “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

• 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? What if there are less applicants than spots? Then the algorithm would have to change, right? What if hospitals hire more than one applicant, then would that also have to be a new algorithm?

• After walking through the the termination proof, it became clearer how the text came to the conclusion that the algorithm's runtime was n^2, which is because there is a maximum of n^2 possible proposals. Moreover, the proof that the algorithm produces a perfect matching was also clearer after walking through it in class because the book presents proofs in a paragraph form, where as in class the proofs are presented as more of a bullet-point, sentence by sentence walk through. The slides cut out the “fluff” that the book uses when making the proofs multiple paragraphs long. Similarly, when we proved in class that the algorithm produces a stable matching, it also made more sense in class than when I read it in the book. I think sometimes its easy to get lot when lots of symbols and letters are presented in a clumpy paragraph, whereas in class proofs are presented in a more linear form.

• 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

• On a scale of 1 to 10, this section was a 8 because I thought that the book did a good job of explaining the process of constructing and analyzing an algorithm start to finish. The only reason it wasn't a 10 is because some of the proofs were a little hard to follow and highly repetitive.