It was originally described in the 1970s by John Horton Conway and Donald Knuth.
The elements of this set can be given a concrete structure as rotations, with cycle graphs describing the changes between adjacent stable matchings in the lattice.
The family of all rotations and their partial order can be constructed in polynomial time, leading to polynomial time solutions for other problems on stable matching including the minimum or maximum weight stable matching.
The number of elements in the lattice can vary from an average case of
In its simplest form, an instance of the stable matching problem consists of two sets of the same number of elements to be matched to each other, for instance doctors and positions at hospitals.
The same comparison operation can be defined in the same way for any two sets of elements, not just doctors and hospitals.
The choice of which of the two sets of elements to use in the role of the doctors is arbitrary.
[1] The Gale–Shapley algorithm gives a process for constructing stable matchings, that can be described as follows: until a matching is reached, the algorithm chooses an arbitrary hospital with an unfilled position, and that hospital makes a job offer to the doctor it most prefers among the ones it has not already made offers to.
An algorithm that swaps the roles of the doctors and hospitals (in which unemployed doctors send a job applications to their next preference among the hospitals, and hospitals accept applications either when they have an unfilled position or they prefer the new applicant, firing the doctor they had previously accepted) instead produces the stable matching that assigns all doctors to their best matches and each hospital to its worst match.
in the following way: (The same operations can be defined in the same way for any two sets of elements, not just doctors and hospitals.
form the join and meet operations of a finite distributive lattice.
[1] Because they are defined using an element-wise minimum or element-wise maximum in the preference ordering, these two operations obey the same distributive laws obeyed by the minimum and maximum operations on linear orderings: for every three different matchings
[1] Birkhoff's representation theorem states that any finite distributive lattice can be represented by a family of finite sets, with intersection and union as the meet and join operations, and with the relation of being a subset as the comparison operation for the associated partial order.
form a pair of the covering relation of the partial order of stable matchings.)
(the symmetric difference of their sets of matched pairs) is called a rotation.
It forms a cycle graph whose edges alternate between the two matchings.
Equivalently, the rotation can be described as the set of changes that would need to be performed to change the lower of the two matchings into the higher one (with lower and higher determined using the partial order).
[5] If the rotations are given the same partial ordering as their corresponding join-irreducible stable matchings, then Birkhoff's representation theorem gives a one-to-one correspondence between lower sets of rotations and all stable matchings.
and instead assigns them to each other, and a second rotation that, when applied to the lower of two matchings, removes pair
From the equivalence between lattices of stable matchings and arbitrary finite distributive lattices, it follows that this problem has equivalent computational complexity to counting the number of elements in an arbitrary finite distributive lattice, or to counting the antichains in an arbitrary partially ordered set.
hospitals, the average number of stable matchings is asymptotically
,[5] and us also upper-bounded by an exponential function of n (significantly smaller than the naive factorial bound on the number of matchings).
[9] The family of rotations and their partial ordering can be constructed in polynomial time from a given instance of stable matching, and provides a concise representation to the family of all stable matchings, which can for some instances be exponentially larger when listed explicitly.
This allows several other computations on stable matching instances to be performed efficiently.
[10] If each pair of elements in a stable matching instance is assigned a real-valued weight, it is possible to find the minimum or maximum weight stable matching in polynomial time.
[11] An alternative, combinatorial algorithm is possible, based on the same partial order.
The problem of finding the minimum or maximum weight stable matching becomes in this way equivalent to the problem of finding the minimum or maximum weight lower set in a partially ordered set of polynomial size, the partially ordered set of rotations.
and similarly by assigning each hospital the median of the three doctors matched to it.
More generally, any set of an odd number of elements of any distributive lattice (or median graph) has a median, a unique element minimizing its sum of distances to the given set.
For an even set of stable matchings, this can be disambiguated by choosing the assignment that matches each doctor to the higher of the two median elements, and each hospital to the lower of the two median elements.