# Stable matching

See also: Wikipedia:Stable matching.

## Preference system

A **preference system** is given by a graph *G=(V,E)* and for every node [math]v \in V[/math] a linear order [math]\lt_v[/math] on the edges incident to *v*. If *e* and *f* are edges incident to *v* and [math]e \lt_v f[/math], then we say that *v* **prefers** *e* to *f* and *f* is **dominated** by *e*. It may be confusing at first that the nodes have preferences on the edges (and not other nodes), but this makes sense if we take into account that *G* may have parallel edges. If *G* is bipartite, then we have a **bipartite preference system**.

If partial orders are given at each node instead of linear orders, we speak of a **preference system with ties**. If *e* and *f* are edges incident to *v* but they are incomparable in [math]\lt_v[/math], then we say that *v* is **indifferent** between *e* and *f* (or *e* is indifferent to *f*).

## Stable matching

Let *(G,<)* be a preference system. A matching *M* of *G* is **stable** if every edge not in *M* is dominated by at least one edge in *M*. The problem of finding a stable matching is traditionally called the *stable marriage problem* if *G* is bipartite and the *stable roommates problem* if *G* is non-bipartite.

By the classic result of Gale and Shapley ^{[1]}, every bipartite preference system has a stable matching and one can be found by the deferred acceptance algorithm. A non-bipartite preference system may not have a stable matching, but Irving ^{[2]} gave a polynomial algorithm to decide if it exists and find one.

In a preference system with ties we can define three different kinds of stability. A matching *M* is **super-stable** if every edge not in *M* is dominated by at least one edge in *M*. It is **strongly stable** if every edge not in *M* is either dominated by at least one edge in *M*, or is indifferent to two edges in *M*. Finally, *M* is **weakly stable** if every edge not in *M* is dominated by or indifferent to at least one edge in *M*.

While deciding the existence of a weakly stable matching is NP-complete, strongly stable and super-stable matchings can be found in polynomial time. In particular, Fleiner, Irving and Manlove ^{[3]} showed that Irving's stable roommates algorithm can be generalized to find a strongly stable matching in a preference system with ties.

## Popular matching

Let *(G,<)* be a preference system. Given two matchings *M* and *N*, we say that a node *v* prefers *M* to *N* if either *v* is matched in *M* but not in *N*, or *v* is matched in both and it prefers the edge incident to it in *M* to the edge incident to it in *N*.

A matching *M* is **popular** (**strongly popular**) if for every other matching *N*, the number of nodes who prefer *M* to *N* is at least (is larger than) the number of nodes who prefer *N* to *M*. If there are no ties, then every stable matching is popular, but not every popular matching has the same size. If there is a strongly popular matching, then it is unique and stable.

In a **node-weighted popular matching** problem, we also have weights for each node of the graph, and a matching *M* is **popular** if for every other matching *N* the sum of the weights of nodes who prefer *M* to *N* is at least the sum of the weights of nodes who prefer *N* to *M*. We can also consider edge weights, and try to find a popular matching of maximum ede-weight.

## References

- ↑ D. Gale, L.S. Shapley,
*College admissions and stability of marriage*, Amer. Math. Monthly (1962) 69(1), 9-15. JSTOR link. - ↑ R. W. Irving,
*An efficient algorithm for the stable roommates problem*, J. Algorithms 6 (1985), 577-595. DOI link. - ↑ T. Fleiner, R. W. Irwing, D. F. Manlove,
*An algorithm for a super-stable roommates problem*, DOI link, EGRES Technical Report no. 2008-06.