Canonical monotone decompositions of fractional stable matchings

This paper continues recent work that introduced algebraic methods for studying the stable marriage problem of Gale and Shapley. Vande Vate and Rothblum identified a set of linear inequalities which define a polytope whose extreme points correspond to the stable matchings. Points in this polytope are called fractional stable matchings. Here the authors identify a unique representation of fractional stable matchings as a convex combination of stable matchings that are arrangeable in a man-decreasing order. They refer to this representation and to a dual one, in terms of woman-decreasing order, as the canonical monotone representations. These representations can be interpreted as time-sharing stable matchings where particular stable matchings are used at each time-instance but the scheduled stable matchings are (occasionally) switched over time. The new representations allow the authors to extend, in a natural way, the lattice structure of the set of stable matchings to the set of all fractional stable matchings.