UCLA

The Stable Marriage Problem (SMP) is concerned with the follow scenario: suppose we have two disjoint sets of agents—for example prospective students and colleges, medical residents and hospitals, or potential romantic partners—who wish to be matched into pairs. Each agent has preferences in the form of a ranking of her potential matches. How should we match agents based on their preferences?

We say that a matching is "stable" if no unmatched pair of agents mutually prefer each other to their assigned partners. In their seminal work on the SMP, Gale and Shapley prove that a stable matching exists for any preferences. They further describe an efficient algorithm for finding a stable matching. In this dissertation, we consider the computational complexity of the SMP in the distributed setting, and the complexity of finding “almost stable” matchings. Highlights include (1) communication lower bounds for finding stable and almost stable matchings, (2) a distributed algorithm which finds an almost stable matching in poly-logarithmic time, and (3) hardness of approximation results for three dimensional analogues of the SMP.