Lattice of stable matchings

In its simplest form, an instance of the stable matching problem consists of two equal-sized finite sets of participants to be matched to each other, for instance doctors seeking jobs and hospitals seeking to hire a doctor. Each participant 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 doctor 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.^[3]

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 matchings for this system of preferences:

1. The doctors get their first choice and the hospitals get their third: AY, BZ, CX.
2. All participants get their second choice: AX, BY, CZ.
3. The hospitals get their first choice and the doctors their third: AZ, BX, CY.

The lattice of stable matchings organizes this collection of solutions, for any instance of stable matching, giving it the structure of a distributive lattice. (For the definition of a distributive lattice, see § Distributive lattice, below.)^[1]

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 participants to be matched, not just doctors and hospitals. The choice of which of the two sets of participants 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 stable matchings, but does not otherwise change the structure of the partial order.^[1]

This ordering gives the matchings the structure of a partially ordered set. A partially ordered set is defined as an ordering that obeys 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.^[1]

Define the best match of a participant ${\displaystyle x}$ of a stable matching instance to be the participant ${\displaystyle y}$ that ${\displaystyle x}$ most prefers, among all the participants for which there exists a stable matching that pairs ${\displaystyle x}$ with ${\displaystyle y}$, and define the worst match analogously. Then no two participants 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. However, a stable matching cannot have an unstable pair. This contradiction shows that best matches are distinct, and therefore 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. This matching, assigning all doctor to their best matches, also assigns all hospitals to their worst matches. In the partial ordering on stable 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 among the two doctors it is matched to.
• 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 to be matched, 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 (here, the set of stable matchings) 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]

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 matchings in the lattice, the join-irreducible matchings (matchings that cannot be formed as joins of a subset of other matchings).^[4]

When a stable matching ${\displaystyle M}$ is join-irreducible, let ${\displaystyle M'}$ be the join of the matchings below ${\displaystyle M}$ in the partial order of stable matchings. Then ${\displaystyle M'}$ is not ${\displaystyle M}$, because it is a join of matchings distinct from ${\displaystyle M}$ and ${\displaystyle M}$ is not such a join. ${\displaystyle M'}$ is below ${\displaystyle M}$ in the partial order of stable matchings, and there are no other stable matchings between ${\displaystyle M'}$ and ${\displaystyle M}$.^[5]

For the lattice of stable matchings, the partial order of Birkhoff's representation theorem can alternatively be described in terms of structures called rotations, first described in 1986 by Robert W. Irving and Paul Leather.^[5]

Suppose that two different stable matchings ${\displaystyle P}$ and ${\displaystyle Q}$ are comparable and have no third stable matching between them in the partial order. Another way of stating this is that ${\displaystyle P}$ and ${\displaystyle Q}$ form a pair of the covering relation of the partial order of stable matchings. For instance, this is true for any join-irreducible matching ${\displaystyle M}$ and the matching ${\displaystyle M'}$ formed by the join of the elements below ${\displaystyle M}$. Then the set of pairs of elements that are matched in one but not both of ${\displaystyle P}$ and ${\displaystyle Q}$ (the symmetric difference ${\displaystyle P\oplus Q}$ of their sets of matched pairs) is called a rotation. It forms a cycle graph whose edges alternate between matched pairs from ${\displaystyle P}$ and from ${\displaystyle Q}$. Removing one of these two alternating sets of pairs, and adding the other alternating set, transforms ${\displaystyle P}$ into ${\displaystyle Q}$ or vice versa.^[5]

More than one pair of matchings ${\displaystyle (P,Q)}$ and ${\displaystyle (R,S)}$ may define the same rotation ${\displaystyle P\oplus Q=R\oplus S}$. For any rotation, the top elements of pairs defining that rotation are closed under meet operations: if ${\displaystyle P}$ and ${\displaystyle R}$ are each the top matchings of pairs ${\displaystyle (P,Q)}$ and ${\displaystyle (R,S)}$ with ${\displaystyle P\oplus Q=R\oplus S}$, then their meet ${\displaystyle P\wedge R}$ is also the top matching of another pair defining the same rotation. For every rotation, let ${\displaystyle M}$ be the meet of all the top matchings of pairs defining that rotation. Then ${\displaystyle M}$ is join-irreducible, and the rotation is ${\displaystyle M\oplus M'}$ where ${\displaystyle M'}$ is the join of the matchings below ${\displaystyle M}$. This gives a one-to-one correspondence between rotations and join-irreducible stable matchings.^[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. 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.^[5]

Every pair ${\displaystyle (x,y)}$ 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 ${\displaystyle x}$ and ${\displaystyle y}$ and instead assigns them to each other, and a second rotation that, when applied to the lower of two matchings, removes pair ${\displaystyle (x,y)}$ from the matching and finds other assignments for those two elements. Because there are ${\displaystyle n^{2}}$ pairs of elements, there are ${\displaystyle O(n^{2})}$ rotations.^[5]