Application Letters

The Problem

You have $n$ job applicants and $n$ positions. Each applicant has a strict ranking of positions (most to least preferred), and each position has a strict ranking of applicants.

Use the Gale-Shapley deferred acceptance algorithm to find a stable matching. Prove:

1. The algorithm always terminates with a stable matching.
2. The matching is applicant-optimal: among all stable matchings, every applicant gets the best position they could get in any stable matching.
3. The matching is position-pessimal: among all stable matchings, every position gets the worst applicant they could get in any stable matching.

(Stability: no applicant-position pair $(a,p)$ where $a$ prefers $p$ to their current match AND $p$ prefers $a$ to their current match.)