Brian C. Dean Associate Professor Division of Computer Science School of Computing, Clemson University Office: McAdams Hall, Room 205 Phone: 864-656-5866 Mail: Brian C. Dean, School of Computing, Box 340974, Clemson SC 29634-0974 Email: bcdean@cs.clemson.edu

Adaptive Stable Marriage Algorithms

Although it takes O(n^2) worst-case time to solve a stable marriage problem instance with n men and n women, a trivial O(n) algorithm suffices if all men are known to have identical preference lists and all women also are known to have identical preference lists. Since real-world instances often involve men or women with similar but not necessarily identical preference lists, this motivates us to introduce the notion of an adaptive stable marriage algorithm -- an algorithm whose running time is of the form O(n + k), where k describes the aggregate amount of disagreement between the preference lists in our instance versus a pair of specified "consensus" preference lists, one for the men and one for women. The running time of an adaptive stable matching algorithm therefore gracefully scales from O(n^2) in the worse case down to O(n) in the case where preference lists are all in close agreement. We show how the O(n + k) running time bound can be achieved if all women are known to have identical preference lists, leaving the case where both men and women can have non-identical but similar preference lists as an open question. We also show how this special case may serve as a good model for sports drafts.

Available in pdf.