In mathematics, economics, and computer science, a lattice of stable matchings is a distributive lattice whose elements are all the solutions to a given instance of the stable matching problem. These solutions, called stable matchings, pair up participants of two types in such a way that no two participants would prefer to be paired with each other than to accept their assigned pairings. Being a lattice means that, for a comparison operation between stable matchings based on the preferences of the participants, each two stable matchings have a unique greatest lower bound and a unique least upper bound. Together, the greatest lower bound and least upper bound operations obey the distributive law. This structure was originally described in the 1970s by John Horton Conway and Donald Knuth. The Gale–Shapley algorithm can find either of two special stable matchings, the greatest and least matchings in the lattice. The entire lattice has a concise representation that can be constructed in polynomial time, by using Birkhoff's representation theorem to describe it as the family of lower sets of an underlying partially ordered set. The elements of this partially ordered set are called rotations; they are cycle graphs that describe the symmetric difference between two stable matchings that are adjacent in the lattice. Algorithms that operate on this partial order instead of directly on stable matchings, and that search for lower sets that are optimal in some way, can find in polynomial time the minimum or maximum weight stable matching, for weighted instances of the stable matching problem. Every finite distributive lattice can be represented as a lattice of stable matchings. The number of matchings in the lattice can vary from an average case of e − 1 n ln n {\displaystyle e^{-1}n\ln n} to a worst case of exponential, where n {\displaystyle n} is the number of participants of each kind to be matched. Computing the number of stable matchings for a given instance of stable matching is #P-complete.
Background
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. 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:
The doctors get their first choice and the hospitals get their third: AY, BZ, CX. All participants get their second choice: AX, BY, CZ. 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.)
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 P ≤ Q {\displaystyle P\leq Q} if and only if all doctors prefer matching Q {\displaystyle Q} to matching P {\displaystyle P} : either they have the same assigned hospital in both matchings, or they are assigned a better hospital in Q {\displaystyle Q} than they are in P {\displaystyle P} . If the doctors disagree on which matching they prefer, then P {\displaystyle P} and Q {\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. 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 P {\displaystyle P} , P ≤ P {\displaystyle P\leq P}
… excerpt ends here. Continue reading the full article.
