Lattice of stable matchings
In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth. By Birkhoff's representation theorem, this lattice can be represented as the lower sets of an underlying partially ordered set, and the elements of this set can be given a concrete structure as rotations, 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 for other problems on stable matching including the minimum or maximum weight stable matching. The Gale–Shapley algorithm can be used to construct two special lattice elements, its top and bottom element. Every finite distributive lattice can be represented as a lattice of stable matchings. The number of elements in the lattice can vary from an average case of formula_1 to a worst-case of exponential. Computing the number of elements is #P -complete. Background. 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. Each element has a preference ordering on the elements of the other type: the doctors each have different preferences for which hospital they would like to work at (for instance based on which cities they would prefer to live in), and the hospitals each have preferences for which doctors they would like to work for them (for instance based on specialization or recommendations). The  goal is to find a matching that is "stable": no pair of a doctor and a hospital prefer each other to their assigned match. Versions of this problem are used, for instance, by the National Resident Matching Program to match American medical students to hospitals. In general, there may be many different stable matchings. For example, suppose there are three doctors (A,B,C) and three hospitals (X,Y,Z) which have preferences of: There are three stable solutions to this matching arrangement: The lattice of stable matchings organizes this collection of solutions, for any instance of stable matching, giving  it the structure of a distributive lattice. Structure. Partial order on matchings. The lattice of stable matchings is based on the following weaker structure, a partially ordered set whose elements are the stable matchings. Define a comparison operation formula_2 on the stable matchings, where formula_3 if and only if all doctors prefer matching formula_4 to matching formula_5: either they have the same assigned hospital in both matchings, or they are assigned a better hospital in formula_4 than they are in formula_5. If the doctors disagree on which matching they prefer, then formula_5 and formula_4 are incomparable: neither one is formula_2  the other. 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. Swapping the roles of the doctors and hospitals reverses the ordering of every pair of elements, but does not otherwise change the structure of the partial order. Then this ordering gives the matchings the structure of a partially ordered set. To do so, it must obey the following three properties: For stable matchings, all three properties  follow directly from the definition of the comparison operation. Top and bottom elements. Define the best match of an element formula_23 of a stable matching instance to be the element formula_24 that formula_23 most prefers, among all the elements that can be matched to formula_23 in a stable matching, and define the worst match analogously. Then no two elements can have the same best match. For, suppose to the contrary that doctors formula_23 and formula_28 both have formula_24 as their best match, and that formula_24 prefers formula_23 to formula_28. Then, in the stable matching that matches formula_28 to formula_24 (which  must exist by the definition of the best match of formula_28), formula_23 and formula_24 would be an unstable pair, because formula_24 prefers formula_23 to formula_28 and formula_23 prefers formula_24 to any other partner in any stable matching. This contradiction shows that assigning all doctors to their best matches gives a matching. It is a stable matching, because any unstable pair would also be unstable for one of the matchings used to define best matches. As well as assigning all doctor to their best matches, it assigns all hospitals to their worst matches. In the partial ordering on the matchings, it  is greater than all other stable matchings. Symmetrically, assigning all doctors to their worst matches and assigning all hospitals to their best matches gives another stable matching. In the partial order on the matchings, it is less than all other stable matchings. 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. If the doctor  is unemployed or has a less-preferred assignment, the doctor accepts the offer (and resigns from their other assignment if it exists). The process always terminates, because each doctor and hospital interact only once. When it terminates, the result is a stable matching, the one that assigns each hospital to its best match and that assigns all doctors to their worst matches. 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. Lattice operations. Given any two stable matchings formula_5 and formula_4 for the same input, one can form two more matchings formula_45 and formula_46 in the following way: Then both formula_45 and formula_46 are matchings. It is not possible, for instance, for two doctors to have the same best choice and be matched to the same hospital in formula_45, for regardless of which of the two doctors is preferred  by the hospital, that doctor and hospital would form an unstable pair in whichever of formula_5 and formula_4 they are not already matched in. Because the doctors are matched in formula_45, the hospitals must also be matched. The same reasoning applies symmetrically to formula_46. Additionally, both formula_45 and formula_46 are stable. There cannot be a pair of a doctor and hospital who prefer each other to their match, because the same pair would necessarily also be an unstable pair for at least one of formula_5 and formula_4. Lattice properties. The two operations formula_45 and formula_46 form the join and  meet operations of a finite distributive lattice. In this context, a finite lattice is defined as a partially ordered finite set in which there is a unique minimum element and a unique maximum element, in which every two elements have a unique least element greater than or equal to both of them (their join) and every two elements have a unique greatest element less than or equal to both of them (their meet). In the case of the operations formula_45 and formula_46 defined above, the join formula_45 is greater than or equal to both formula_5 and formula_4 because it was  defined to give each doctor their preferred choice, and because these preferences of the doctors are how the ordering on matchings is defined. It is below any other matching that is also above both formula_5 and formula_4, because any such matching would have to give each doctor an assigned match that is at least as good. Therefore, it fits the requirements for the join operation of a lattice. Symmetrically, the operation formula_46 fits the requirements for the meet operation. 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 formula_5, formula_4, and formula_19, and Therefore, the lattice of stable matchings is a distributive lattice. Representation by rotations. 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. More specifically, these sets can be taken to be the lower sets of an associated partial order . In the general form of Birkhoff's theorem, this partial order can be taken as the induced order on a subset of the elements of the lattice, the join-irreducible elements (elements that cannot be formed as joins of two other elements). For the lattice of stable matchings, the elements of the partial order can instead be described in terms of structures called "rotations", described by . Suppose that two different stable matchings formula_5 and formula_4 are comparable and have no third stable matching between them in the partial order. (That is, formula_5 and formula_4 form a pair of the  covering relation of the partial order of stable matchings.) Then the set of pairs of elements that are matched in one but not both of formula_5 and formula_4 (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). If two different stable matchings are separately the higher  matching for the same rotation, then so is their meet. It follows that for any rotation, the set of stable matchings that can be the higher of a pair connected by the rotation has a unique lowest element. This lowest matching is join irreducible, and this gives a one-to-one correspondence between rotations and join-irreducible stable matchings. 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. The set of rotations associated  with any given stable matching can be obtained by changing the given matching by rotations downward in the partial ordering, choosing arbitrarily which rotation to perform at each step, until reaching the bottom element, and listing the rotations used in this sequence of changes. The stable matching associated with any lower set of rotations can be obtained by applying the rotations to the bottom element of the lattice of stable matchings, choosing arbitrarily which rotation to apply when more than one can apply. Every pair formula_85 of elements of a given stable matching instance belongs to at most two rotations : one rotation that, when applied to the lower of two matchings, removes other assignments to formula_23 and formula_24 and instead assigns them to each other, and a second rotation that, when applied to the lower of two matchings, removes pair formula_85 from the matching and finds other assignments for those two elements. Because there are formula_89 pairs of elements, there are formula_90 rotations. Mathematical properties. Universality. Beyond being a finite distributive lattice, there are no other constraints on the lattice structure of stable matchings. This is because, for every finite distributive lattice formula_91, there exists a stable matching instance whose  lattice of stable matchings is isomorphic to formula_91. More strongly, if a finite distributive lattice has formula_93 elements, then it can be realized using a stable matching instance with at most formula_94 doctors and hospitals. Number of lattice elements. The lattice of stable matchings can be used to study the computational complexity of counting the number of stable matchings of a given instance. 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. Computing the number of stable matchings is #P-complete. In a uniformly-random instance of the stable marriage problem with formula_95 doctors and formula_95 hospitals, the average number of stable matchings is asymptotically formula_1. In a stable marriage instance chosen to maximize the number of different stable matchings, this number can be at least formula_98, and us also upper-bounded by an exponential function of (significantly smaller than the naive factorial bound on the number of matchings). Algorithmic consequences. 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. Weighted stable matching and closure. 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. One possible method for this is to apply linear programming to the order polytope of the partial order of rotations , or to the stable matching polytope. An alternative, combinatorial algorithm is possible, based on the same partial order. From the weights on pairs of elements, one can assign weights to each rotation, where a rotation that changes a given stable matching to another one higher in the partial ordering of stable matchings is assigned the change in weight that it causes: the total weight of the higher matching minus the total weight of the lower matching. By the correspondence between stable matchings and lower sets of rotations, the total weight of any matching is then equal to the total weight  of its corresponding lower set, plus the weight of the bottom element of the lattice of matchings. 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. This optimal lower set problem is equivalent to an instance of the closure problem, a problem on vertex-weighted directed graphs in which the goal is to find a subset of vertices of optimal weight with no outgoing edges. The optimal  lower set is an optimal closure of a directed acyclic graph that has the elements of the partial order as its vertices, with an edge from formula_99 to formula_100 whenever formula_101 in the partial order. The closure problem can, in turn, be solved in polynomial time by transforming it into an instance of the maximum flow problem. Minimum regret. defines the regret of a participant in a stable matching to be the distance of their assigned match from the top of their preference list. He defines the regret of a stable matching to be the maximum regret of any participant . Then one can find the minimum-regret stable matching by a simple greedy algorithm that starts at the bottom element of the lattice of matching and then repeatedly applies any rotation that reduces the regret of a participant with maximum regret, until this would cause some other participant to have greater regret. Median stable matching. The elements of any distributive lattice form a median graph, a structure in which any three elements formula_5, formula_4, and formula_19 (here, stable matchings) have a unique median element formula_105 that lies on a shortest path between any two of them. It can be defined  as: For the lattice of stable matchings, this median can instead be taken element-wise, by assigning each doctor the median in the doctor's preferences of the three hospitals matched to that doctor in formula_5, formula_4, and formula_19 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 the median of an odd number of stable matchings, each participant is matched  to the median element of the multiset of their matches from the given matchings. 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. In particular, this leads to a definition for the median matching in the set of all stable matchings. However, for some instances of the stable matching problem, finding this median of all stable matchings is NP-hard.