csci 570

Context: Originated from medical residency pairings; involves matching two equal-sized sets (e.g., men and women) where each person has strict preferences over the opposite set.
Goal: Find a perfect matching (everyone is paired) that is stable, meaning no unmatched pair prefers each other over their current partners.
Key Terminology:
- Matching: A set of disjoint pairs.
- Perfect matching: Every individual in both sets is paired.
- Bipartite graph: Two disjoint sets (e.g., men and women).
- Stability: A perfect matching with no blocking pair.
- Blocking pair (instability): An unmatched pair $(M, W)$ where $M prefers $W to his current partner, and $W prefers $M to her current partner.
- Complete preference order: Each individual ranks all opposite-sex members without ties.

A stable matching is a perfect matching without instability.
Existence: At least one stable matching always exists (proven by Gale-Shapley).
Uniqueness: Stable matchings are not always unique; multiple can exist.
Real-world alignment: Stability prevents blocking coalitions, ensuring the matching holds.

Examples include students and internships.
Key assumptions: equal numbers of individuals on both sides for a perfect matching, and strict preferences without ties.

Core idea: An iterative process where one side (e.g., men) proposes to the other (women) based on their preference lists.
Procedure:
- Free men propose to their highest-ranked available women.
- Women either accept (if free or if the proposer is preferred to current fiancé, freeing the old fiancé) or reject.
- This continues until all men are engaged.
Engagement behavior: Women's partners only improve; men's proposals move down their lists.
Termination: Guaranteed within $n^2$ iterations because each rejected proposal is unique and not repeated.
Result: The algorithm always produces a perfect and stable matching by ensuring no free men remain and no blocking pairs can exist due to the proposal/acceptance logic.

Proposer's advantage: The proposing side generally achieves their best possible stable matching, while the other side gets their worst.
Non-uniqueness: Multiple stable matchings can exist; Gale-Shapley finds one, not necessarily all.

The algorithm isn't inherently 'fair'; the choice of proposer impacts outcomes, raising ethical considerations for real-world applications where other objectives like general utility might be prioritized.

Illustrations with 2x2 cases show that stable matchings prioritize structural stability over universal satisfaction, and multiple stable outcomes are possible.

Extensions include scenarios like multiple openings per company (treated as separate slots) and handling ties in preferences (requires algorithm modification or relaxed stability definitions).

Common proof techniques include direct proofs, proofs by cases, induction, indirect proofs (contradiction), and contrapositive proofs.

Structure: Assume the hypothesis and logically derive the conclusion.
Example: If $m=2p$ and $n=2q$ , then $m+n=2(p+q)$ , which is even. Also, if $m+n$ and $n+p$ are even, then $m+p$ is even.

Structure: Break a statement into exhaustive cases and prove each case. Often used with parity (even/odd) arguments.

Structure: Proves statements for natural numbers (base case for $n=1$ , Inductive Hypothesis for $k$ , Inductive Step for $k+1$ ).
Example: Sum of first $n$ natural numbers is $frac{n(n+1)}{2}$ . For $k+1$ : $frac{k(k+1)}{2} + (k+1) = frac{(k+1)(k+2)}{2}$ .

Structure: Assume the hypothesis AND the negation of the conclusion, then derive a contradiction.
Example: To prove infinitely many primes, assume a finite list $p<em>1, …, p</em>n$ . Consider $P!+1$ ; it must have a prime factor not in the list, a contradiction.