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 Θ(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 |