Late Birthday Wishes

Happy 70th birthday, Don Knuth! This is a post, arriving late and contrite, behind the slew of beautiful blog-homages (follow the thread from scott). Each of us can write volumes about his impact, and we would still be short.

One of his research threads I like (and explored a little in school and more now in my work) is on Mariages Stables. Consider n men with strict preference order for n women and vice versa, and the standard "deferred acceptance" algorithm that has men running to women down their preference list, getting tentatively accepted, getting rejected when higher preferred men come along, and eventually finding their stable mate, a bonding that cannot be broken for a better pairing with others simultaneously. This gives men-optimal stable matching M. An analogous algorithm that makes the women run produces women-optimal stable matching W. Knuth showed that M is the worst stable matching for women and W is the worst stable matching for the men. Formally, there is a lattice among matchings defined by the preference relations, and an algebra on the space of matchings gives nice properties of stable matchings.

Since the early days of work by Gale, Shapley, Knuth, Conway and others, the study of stable matchings --- algorithms, strategies, properties, and applications --- continues to thrive. See the book; there is even an upcoming workshop.