Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron

Rothblum showed that the convex hull of the stable matchings of a bipartite preference system can be described by an elegant system of linear inequalities. In this paper we prove that the description given by Rothblum is totally dual integral. We give a constructive proof based on the results of Gusfield and Irving on rotations, which gives rise to a strongly polynomial algorithm for finding an integer optimal dual solution.