Rafail Ostrovsky - Publications

A Stable Marriage Requires Communication

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


The Gale-Shapley algorithm for the Stable Marriage Problem is known to take Θ(n2) 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 Θ(n2) 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