Structure of the Stable Marriage and Stable Roommate Problems and Applications

The well-known Gale-Shapley algorithm is a solution to the stable marriage problem, but always results in the same stable marriage, regardless of how the algorithm is executed. Robert Irving and Paul Leather constructed the rotation poset, whose downward closed sets are in one-to-one correspondence with the set of stable marriage assignments. We discuss how to use the rotation poset to find the k-optimal matching, and prove that a k-optimal matching is the same as a minimum regret matching for high enough k. Finally, Dan Gusfield defines the rotation poset for the stable roommate problem, and uses it to efficiently enumerate all stable roommate assignments.