Lattice of stable 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 ${\displaystyle \leq }$ on the stable matchings, where ${\displaystyle P\leq Q}$ if and only if all doctors prefer matching ${\displaystyle Q}$ to matching ${\displaystyle P}$: either they have the same assigned hospital in both matchings, or they are assigned a better hospital in ${\displaystyle Q}$ than they are in ${\displaystyle P}$. If the doctors disagree on which matching they prefer, then ${\displaystyle P}$ and ${\displaystyle Q}$ are incomparable: neither one is ${\displaystyle \leq }$ 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.[1]

Then this ordering gives the matchings the structure of a partially ordered set. To do so, it must obey the following three properties:

• For every matching ${\displaystyle P}$, ${\displaystyle P\leq P}$
• For every two different matchings ${\displaystyle P}$ and ${\displaystyle Q}$, it cannot be the case that both ${\displaystyle P\leq Q}$ and ${\displaystyle Q\leq P}$ are true.
• For every three different matchings ${\displaystyle P}$, ${\displaystyle Q}$, and ${\displaystyle R}$, if ${\displaystyle P\leq Q}$ and ${\displaystyle Q\leq R}$, then ${\displaystyle P\leq R}$.

For stable matchings, all three properties follow directly from the definition of the comparison operation.

Define the best match of an element ${\displaystyle x}$ of a stable matching instance to be the element ${\displaystyle y}$ that ${\displaystyle x}$ most prefers, among all the elements that can be matched to ${\displaystyle x}$ 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 ${\displaystyle x}$ and ${\displaystyle x'}$ both have ${\displaystyle y}$ as their best match, and that ${\displaystyle y}$ prefers ${\displaystyle x}$ to ${\displaystyle x'}$. Then, in the stable matching that matches ${\displaystyle x'}$ to ${\displaystyle y}$ (which must exist by the definition of the best match of ${\displaystyle x'}$), ${\displaystyle x}$ and ${\displaystyle y}$ would be an unstable pair, because ${\displaystyle y}$ prefers ${\displaystyle x}$ to ${\displaystyle x'}$ and ${\displaystyle x}$ prefers ${\displaystyle y}$ 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.[1]

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.[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. 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.[1]

Given any two stable matchings ${\displaystyle P}$ and ${\displaystyle Q}$ for the same input, one can form two more matchings ${\displaystyle P\vee Q}$ and ${\displaystyle P\wedge Q}$ in the following way:

In ${\displaystyle P\vee Q}$, each doctor gets their best choice among the two hospitals they are matched to in ${\displaystyle P}$ and ${\displaystyle Q}$ (if these differ) and each hospital gets its worst choice.

In ${\displaystyle P\wedge Q}$, each doctor gets their worst choice among the two hospitals they are matched to in ${\displaystyle P}$ and ${\displaystyle Q}$ (if these differ) and each hospital gets its best choice.

(The same operations can be defined in the same way for any two sets of elements, not just doctors and hospitals.)[1]

Then both ${\displaystyle P\vee Q}$ and ${\displaystyle P\wedge Q}$ 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 ${\displaystyle P\vee Q}$, 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 ${\displaystyle P}$ and ${\displaystyle Q}$ they are not already matched in. Because the doctors are matched in ${\displaystyle P\vee Q}$, the hospitals must also be matched. The same reasoning applies symmetrically to ${\displaystyle P\wedge Q}$.[1]

Additionally, both ${\displaystyle P\vee Q}$ and ${\displaystyle P\wedge Q}$ 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 ${\displaystyle P}$ and ${\displaystyle Q}$.[1]

The two operations ${\displaystyle P\vee Q}$ and ${\displaystyle P\wedge Q}$ 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).[1]

In the case of the operations ${\displaystyle P\vee Q}$ and ${\displaystyle P\wedge Q}$ defined above, the join ${\displaystyle P\vee Q}$ is greater than or equal to both ${\displaystyle P}$ and ${\displaystyle Q}$ 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 ${\displaystyle P}$ and ${\displaystyle Q}$, 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 ${\displaystyle P\wedge Q}$ fits the requirements for the meet operation.[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 ${\displaystyle P}$, ${\displaystyle Q}$, and ${\displaystyle R}$,

${\displaystyle P\wedge (Q\vee R)=(P\wedge Q)\vee (P\wedge R)}$

and

${\displaystyle P\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)}$

Therefore, the lattice of stable matchings is a distributive lattice.[1]

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 ${\displaystyle L}$, there exists a stable matching instance whose lattice of stable matchings is isomorphic to ${\displaystyle L}$.[6] More strongly, if a finite distributive lattice has ${\displaystyle k}$ elements, then it can be realized using a stable matching instance with at most ${\displaystyle k^{2}-k+4}$ doctors and hospitals.[7]

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.[5]

In a uniformly-random instance of the stable marriage problem with ${\displaystyle n}$ doctors and ${\displaystyle n}$ hospitals, the average number of stable matchings is asymptotically ${\displaystyle e^{-1}n\ln n}$.[8] In a stable marriage instance chosen to maximize the number of different stable matchings, this number can be at least ${\displaystyle 2^{n-1}}$,[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]

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.[11] An alternative, combinatorial algorithm is possible, based on the same partial order.[12]

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.[12]

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 ${\displaystyle \alpha }$ to ${\displaystyle \beta }$ whenever ${\displaystyle \alpha \leq \beta }$ 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.[12]

Gusfield (1987) 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.[10]

The elements of any distributive lattice form a median graph, a structure in which any three elements ${\displaystyle P}$, ${\displaystyle Q}$, and ${\displaystyle R}$ (here, stable matchings) have a unique median element ${\displaystyle m(P,Q,R)}$ that lies on a shortest path between any two of them. It can be defined as:[13]

${\displaystyle m(P,Q,R)=(P\wedge Q)\vee (P\wedge R)\vee (Q\wedge R)=(P\vee Q)\wedge (P\vee R)\wedge (Q\vee R).}$

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 ${\displaystyle P}$, ${\displaystyle Q}$, and ${\displaystyle R}$ 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.[14] 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.[15] However, for some instances of the stable matching problem, finding this median of all stable matchings is NP-hard.[16]