Stable matching polytope
In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem. Description. The stable matching polytope is the convex hull of the indicator vectors of the stable matchings of the given problem. It has a dimension for each pair of elements that can be matched, and a vertex for each stable matchings. For each vertex, the Cartesian coordinates are one for pairs that are matched in the corresponding matching, and zero for pairs that are not matched. The  stable matching polytope has a polynomial number of facets. These include the conventional inequalities describing matchings without the requirement of stability (each coordinate must be between 0 and 1, and for each element to be matched the sum of coordinates for the pairs involving that element must be exactly one), together with inequalities constraining the resulting matching to be stable (for each potential matched pair elements, the sum of coordinates for matches that are at least as good for one of the two elements must be at least one). 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. Integrality. It is a theorem of that the polytope described by the facet constraints listed above has only the vertices described above. In particular it is an integral polytope. 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. An equivalent way of stating the same theorem is that every fractional matching can be expressed as a convex combination of integral matchings. prove this  by constructing a probability distribution on integral matchings whose expected value can be set equal to any given fractional matching. 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. Therefore, the probability distribution over stable matchings constructed in this way provides a representation of the given fractional matching as a convex combination of integral stable matchings. Lattice of fractional matchings. The family of all stable matchings forms a distributive lattice, the lattice of stable matchings, in which the join  of two matchings gives all doctors their preference among their assigned hospitals in the two matchings, and the meet gives all hospitals their preference. The same is true of the family of all fractional stable matchings, the points of the stable matching polytope. In the stable matching polytope, one can define one matching to dominate another if, for every doctor and hospital, the total fractional value assigned to matches for that doctor that are at least as good (for the doctor) as that hospital are at least as large in the first matching as in the second. This defines a  partial order on the fractional matchings. 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. Consistently with this partial order, one can define the meet of two fractional matchings to be a fractional matching that is as low as possible in the partial order while dominating the two  matchings. For each doctor and hospital, it assigns to that potential matched pair a weight that makes the total weight of that pair and all better pairs for the same doctor equal to the larger of the corresponding totals from the two given matchings. The join is defined symmetrically. Applications. By applying linear programming to the stable matching polytope, one can find the minimum or maximum weight stable matching. Alternative methods for the same problem include applying the closure problem to a partially ordered set derived from the lattice of stable matchings, or applying linear programming to the order polytope  of this partial order. Relation to order polytope. The property of the stable matching polytope, of defining a continuous distributive lattice is analogous to the defining property of a distributive polytope, a polytope in which coordinatewise maximization and minimization form the meet and join operations of a lattice. However, the meet and join operations for the stable matching polytope are defined in a different way than coordinatewise maximization and minimization. Instead, the order polytope of the underlying partial order of the lattice of stable matchings provides a distributive polytope associated with the set of stable matchings, but one for which  it is more difficult to read off the fractional value associated with each matched pair. In fact, the stable matching polytope and the order polytope of the underlying partial order are very closely related to each other: each is an affine transformation of the other.