Introduction

1.1 Stable Matching

Assume two sets of \(n\) participants with strict, complete preferences. A stable matching pairs everyone with no pair who prefer each other to their assigned partners.

TipGale–Shapley

• Start unmatched. Free proposers approach their next preferred receiver; receivers keep their best offer so far. Repeat until all are matched.

• Result: Proposer-optimal among stable matchings; \(O(n^2)\) worst-case time and space with precomputed preference ranks.

NoteRandom Preferences: \(O(n \log n)\) Expected Proposals

• Assume all preference lists are independent, uniformly random permutations.
• Coupon collector: Sample receivers uniformly, ignoring repeated proposals by the same proposer. Once every receiver has received a proposal, everyone is matched.
• Counting these extra attempts gives \(\mathbb{E}[P] \le nH_n = n\sum_{k=1}^{n}1/k = O(n\log n)\) for the number of actual proposals \(P\).
• This bounds the proposal phase; explicitly building preference ranks still takes \(O(n^2)\) time.