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

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 ${\displaystyle e^{-1}n\ln n}$ 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.[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:

A: YXZ   B: ZYX   C: XZY  

X: BAC   Y: CBA   Z: ACB

There are three stable solutions to this matching arrangement:

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

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 ${\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.

Top and bottom elements

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]

Lattice operations

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]

Lattice properties

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]

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).[4] For the lattice of stable matchings, the elements of the partial order can instead be described in terms of structures called rotations, described by Irving & Leather (1986).[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. (That is, ${\displaystyle P}$ and ${\displaystyle Q}$ 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 ${\displaystyle P}$ and ${\displaystyle Q}$ (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.[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]

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 ${\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]

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

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

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

Minimum regret

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]

Median stable matching

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]

References

1. Knuth, Donald E. (1976), Mariages stables et leurs relations avec d'autres problèmes combinatoires (PDF) (in French), Montréal, Quebec: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3, MR 0488980. See in particular Problem 6, pp. 87–94.
2. Hwang, J. S. (1982), "The lattice of stable marriages and permutations", Journal of the Australian Mathematical Society, Series A: Pure Mathematics and Statistics, 33 (3): 401–410, doi:10.1017/S1446788700018838, MR 0678518
3. Peranson, E.; Randlett, R. R. (June 1995), "The NRMP matching algorithm revisited", Academic Medicine, 70 (6): 477–84, doi:10.1097/00001888-199506000-00008, PMID 7786367
4. Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal, 3 (3): 443–454, doi:10.1215/S0012-7094-37-00334-X
5. Irving, Robert W.; Leather, Paul (1986), "The complexity of counting stable marriages", SIAM Journal on Computing, 15 (3): 655–667, doi:10.1137/0215048, MR 0850415
6. Blair, Charles (1984), "Every finite distributive lattice is a set of stable matchings", Journal of Combinatorial Theory, Series A, 37 (3): 353–356, doi:10.1016/0097-3165(84)90056-6, MR 0769224
7. Gusfield, Dan; Irving, Robert; Leather, Paul; Saks, Michael (1987), "Every finite distributive lattice is a set of stable matchings for a small stable marriage instance", Journal of Combinatorial Theory, Series A, 44 (2): 304–309, doi:10.1016/0097-3165(87)90037-9, MR 0879688
8. Pittel, Boris (1989), "The average number of stable matchings", SIAM Journal on Discrete Mathematics, 2 (4): 530–549, doi:10.1137/0402048, MR 1018538
9. Karlin, Anna R.; Gharan, Shayan Oveis; Weber, Robbie (2018), "A simply exponential upper bound on the maximum number of stable matchings", in Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Proceedings of the 50th Symposium on Theory of Computing (STOC 2018), Association for Computing Machinery, pp. 920–925, arXiv:1711.01032, doi:10.1145/3188745.3188848, MR 3826305
10. Gusfield, Dan (1987), "Three fast algorithms for four problems in stable marriage", SIAM Journal on Computing, 16 (1): 111–128, doi:10.1137/0216010, MR 0873255
11. Vande Vate, John H. (1989), "Linear programming brings marital bliss", Operations Research Letters, 8 (3): 147–153, doi:10.1016/0167-6377(89)90041-2, MR 1007271
12. Irving, Robert W.; Leather, Paul; Gusfield, Dan (1987), "An efficient algorithm for the "optimal" stable marriage", Journal of the ACM, 34 (3): 532–543, doi:10.1145/28869.28871, MR 0904192
13. Birkhoff, Garrett; Kiss, S. A. (1947), "A ternary operation in distributive lattices", Bulletin of the American Mathematical Society, 53 (1): 749–752, doi:10.1090/S0002-9904-1947-08864-9, MR 0021540
14. Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), "Medians in median graphs", Discrete Applied Mathematics, 8 (2): 131–142, doi:10.1016/0166-218X(84)90096-9, MR 0743019
15. Teo, Chung-Piaw; Sethuraman, Jay (1998), "The geometry of fractional stable matchings and its applications", Mathematics of Operations Research, 23 (4): 874–891, doi:10.1287/moor.23.4.874, MR 1662426
16. Cheng, Christine T. (2010), "Understanding the generalized median stable matchings", Algorithmica, 58 (1): 34–51, doi:10.1007/s00453-009-9307-2, MR 2658099