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 , 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 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 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.