The points satisfying all of these constraints can be thought of as the fractional solutions of a linear programming relaxation of the stable matching problem.
This can be seen as an analogue of the theorem of Garrett Birkhoff that an analogous polytope, the Birkhoff polytope describing the set of all fractional matchings between two sets, is integral.
To do so, they perform the following steps: The resulting randomly chosen stable matching chooses any particular matched pair with probability equal to the fractional coordinate value of that pair.
This partial order has a unique largest element, the integer stable matching found by a version of the Gale–Shapley algorithm in which the doctors propose matches and the hospitals respond to the proposals.
It also has a unique smallest element, the integer stable matching found by a version of the Gale–Shapley algorithm in which the hospitals make the proposals.
[7] However, the meet and join operations for the stable matching polytope are defined in a different way than coordinatewise maximization and minimization.