Title: Improved Hill Climbing for the Stable Marriage Problem

Speaker: Justin Marks (Biola University)

Abstract: In the Nobel Prize-awarded stable marriage problem, first introduced by Gale and Shapley in 1962, n men and n women rank participants of the opposite group in order of preference.  Every preference profile admits at least one stable matching, a consequence of the constructive algorithm of Gale and Shapley, which we will simulate as part of this talk. The goal of our work is to find preference profiles that maximize the number of stable matchings, which is a long-standing research problem first proposed by Knuth in 1975. Each participant has n! ways of ranking the opposite group yielding (n!)^(2n) possible preference profiles, and thus a search space that suffers from combinatorial explosion. Using hill climbing and systematic seed selection, we improve on five records that have been in place for decades, for orders n = 7, 9, 11, 13, 15.  This research is at the intersection of combinatorics and computational algorithm design, and extends the work of beloved Biola University mathematics professor emeritus Ed Thurber.