**
A Stable Marriage Requires Communication
**

*
Yannai A. Gonczarowski,
Noam Nisan,
Rafail Ostrovsky,
Will Rosenbaum
*

**
Abstract:
**

The Gale-Shapley algorithm for the Stable Marriage Problem is known to take Θ(n^{2}) steps to find a stable marriage in the worst case, but only Θ(nlog 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 Θ(n^{2})
queries are required in a model that allows certain natural random-access queries to the participants' preferences. A significantly more general- albeit slightly weaker- lower bound follows
from Segal's elaborate analysis of communication complexity, namely Ω(n^{ }).Boolean
queries are required in order to find a stable marriage, regardless of the set of allowed .Boolean queries.

Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that Ω(n^{ })Boolean queries of any type are indeed required.
Notably, unlike Segal's lower bound, our bound generalizes also to (A) randomized algorithms, (B) finding approximately-stable marriages (C) verifying the stability (or the approximate stability)
of a proposed marriage, (D) allowing arbitrary separate preprocessing of the women's preferences profile and of the men's preferences profile, and (E) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.

**comment:**
SODA 2015 pp:1003-1017

Fetch PDF file of the paper

Back to Publications List |