1.1

Why is stable matching important?: so we don’t have a situation that could spiral out of control, with one person/object/etc. throwing off another object which throws off another object, etc.

How should you initially approach complex problems, especially matching ones?: creating a “bare-bones” version of the problem (ex: simplify the recruitment process to only look at ONE company looking to hire ONE candidate from a set of n applicants)

Defining instability for this problem: when a woman in one marriage prefers a man in a different marriage to her current husband, and the man also prefers that woman over his own wife → infidelity, marriage falling apart, spiraling out of control as the abandoned spouses seek new mates

Matching set = a set in which each member of each group (each male and each female) appear in at most one pair

Perfect matching = when each male and each female appear in exactly one pair

Defining stable for this problem: A matching set is stable if

1. It is perfect (as defined above)
2. There is no instability (as defined above)

How the algorithm works:

• Participants rank members of the opposite sex in order of preference
• While each man is free and hasn’t proposed to every woman…
• A man proposes to the woman that is highest ranked on his list that he hasn’t proposed to yet
• If the woman is single, she must accept; if she is engaged but prefers this new engagement more, she’ll dump her original engagement; if she prefers her existing arrangement, she will deny the proposal and the man will then ask his next favorite choice

Analyzing the algorithm: 3 observations

1. Any woman’s partner = the highest-ranked man who’s proposed to her up to that point (her partner’s will only increase in preference ranking over the execution of the algorithm)
2. A woman’s state can go from single to engaged, but not back to single (unlike the males)
3. A man has a higher chance of getting who he wants than a woman since he asks first, but he is also able to be bumped out of his engagement, forcing him to enter one he doesn’t prefer as much (he can only downgrade)

Does the algorithm terminate?: Yes. There are only n^2 possible proposals → O(n^2)

Proving perfection by contradiction

• Remember that a “perfect match” is one in which everyone ends up in a single monogamous relationship
• So the claim we’re trying to prove wrong = “not all men and women get matched”
• Suppose some man and some woman weren’t matched before the algorithm terminated
• By observation 2, the woman was never proposed to (since she would have had to remain single if she had)
• However, if the loop terminated, it means that the last man standing must have either gotten engaged or proposed to each woman (by definition of the loop)
• Contradiction: how could he have proposed to everyone, whereas the woman never got a proposal?

Every execution of the G-S algorithm yields the same matching set S

• See pg 11 for proof by contradiction

Discrete: involving an implicit search over a large set of combinatorial possibilities

How do we measure runtime?: using the worst case runtime

• Why not avg runtime? –> what is average?
• When looking at polynomial runtimes, we only really need to pay attention to the highest-order term

An algorithm is efficient if it has a polynomial running time

Desirable Scaling Property: when the input size doubles, the algorithm should only slow down by some constant factor C (from ppt)

Runtimes in order from slowest to fastest:

• n
• nlog2n (the minimum runtime for comparison-based sorting algorithms)
• n^2
• n^3
• 1.5^n
• 2^n
• n!

Asymptotic Defs

Asymptotic Upper Bounds: We say T(n) = O(f(n)) (“T(n) is order f(n)”) if, for a sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n). Basically, if eventually f(n) stays greater than T(n) forever after a certain point, “T is asymptotically upper-bounded by f”

Asymptotic Lower Bounds: we say T(n) is Ω(f(n)) (“T is asymptotically lower bounded by f”) in the case opposite of the asymptotic lower bounds (f(n) < T(n) forever after a certain point).

Asymptotically Tight Bounds: if T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n))