A Stable Marriage Requires Communication

Yannai A. Gonczarowski
Noam Nisan

The Gale-Shapely algorithm for the Stable Marriage Problem is known to take \Theta(n^2) steps to find a stable marriage
in the worst case, but only \Theta(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked
whether the worst-case running time can be improved in a model of computation that does not require sequential access
to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that \Theta(n^2) queries are
required in a model that allows certain natural random-access queries to the participants' preferences. Using a
reduction to the communication complexity of the disjointness problem, we prove a significantly more general - albeit
slightly weaker - result, showing that \Omega(n^2) Boolean queries of any type are required. Our lower bound
generalizes to (A) randomized algorithms, (B) even just verifying the stability of a proposed marriage, (C) even
allowing arbitrary separate preprocessing of the women's preferences and of the men's preferences, and (D) several
variants of the basic problem, such as whether a given pair is married in every/some stable marriage.

June, 2014