Optimal stable matching

In the theory of matching markets, an optimal stable matching is a matching that, among all stable matchings, satisfies some criterion of optimality. In the special case in which the matching market is bipartite (e.g. there are men and women, each man should be matched to woman and each woman should be matched to a man), the problem is called optimal stable marriage.

This is a challenging optimization problem, as even in the bipartite case, the number of stable marriages might be exponential in the number of agents.

Men-optimal and women-optimal stable marriage

In the bipartite case, the Gale–Shapley algorithm returns a matching that, among all stable matchings, is optimal for the proposing side. That is, if men propose, the outcome is the men-optimal stable marriage; if women propose, the outcome is the women-optimal stable marriage. The run-time of this algorithm is O(m), where m is the total length of the preference lists. In the case of complete preference lists m = n², so the run-time is O(n²).

There is no conflict within each group: every stable marriage that is better for one man, is better for all men; every stable marriage that is better for one woman, is better for all women. However, there is a total conflict between the sides: the men-optimal stable marriage is the worst for all women, and vice-versa. Hence, researchers have considered optimality criteria that treat both groups in a more balanced way.

Maximizing the total satisfaction

A natural optimization criterion, based on the utilitarian rule, is to maximize the sum of utilities of all agents, men and women alike. Such a matching can be called utilitarian stable matching.

Irving, Leather and Gusfield first consider the special case of rank-utilities --- the utility of each agent is minus the rank of his/her matched partner (e.g. if a man is assigned the woman he likes the best, then his rank is 1, and so his satisfaction is minus 1; if he is assigned his second-best woman, then his satisfaction is minus 2; and so on). They call an algorithm that maximizes the sum of rank-utilities (equivalently, minimizes the sum of ranks) egalitarian, although a more natural name would be rank-utilitarian stable matching. They present an algorithm for computing a rank-utilitarian stable marriage for n men and n women with strict preferences. It runs in time O(m²) = O(n⁴). The algorithm uses intricate structural properties of the lattice of stable matchings.

A variant of their algorithm computes a utilitarian stable marriage (with general utilities) in time O(m² log K) = O(n⁴ log K), where K is the weight of the optimal marriage. The run-time of their algorithm is dominated by computing the maximum network flow in a network with at most m nodes and at most m edges. They used the Sleator-Tarjan algorithm, a variant of Dinic's algorithm, whose run-time is in O(|V| |E| log |V|) = O(m² log n). A later algorithm by Orlin (2013) requires only O(|V| |E|) time, which leads to an O(m²) = O(n⁴) run-time.

Feder presents two faster algorithms for utilitarian stable matching. The main ingredients driving the speed-up are two new algorithms for maximum network flow on a network with m edges and integer capacities (recall that the classical algorithms run in time O(m n) on a network with m edges an n nodes):

• The first one runs in time $O(m\sqrt{K}+K{\log }^{2}m)$, where K is the maximum flow size.
• The second one runs in time $O(wm\log K)$, where w is the cut-width of the network (the maximum number of edges in a finite-capacity cut). It is based on iteratively replacing each capacity c with floor(c/2), thus decreasing the maximum flow to at most K/2, until the maximum flow becomes 0. So there are log₂K iterations, each of which runs in time O(w m).

The network flow algorithms are used to solve instances of weighted 2-satisfiability, and these in turn are used to compute utilitarian stable matchings. His algorithms for computing a utilitarian stable marriage run in time $O(m\sqrt{K}+K{\log }^{2}m)$ and $O(nm\log K)$ respectively, where n is the number of agents, m the total length of all preference lists, and K the weight of the optimal matching. With complete lists m=n², so the run-times are $O(n^2\sqrt{K}+K{\log }^{2}n)$ and $O(n^3\log K)$ respectively. For rank-utilitarian stable marriage (as well as any other case in which K ≤ m), the first algorithm has a better run-time: $O(m^{1.5}+m{\log }^{2}m)=O(m^{1.5}+m{\log }^{2}m)=O(n^3)$.

Maximizing the smallest satisfaction

Knuth defined a matching as minimum regret if it minimizes the maximum rank that any person receives. Equivalently, it maximizes the minimum utility of an agent, where the utility is defined as minus the rank. Maximizing the minimum utility is the egalitarian rule; hence, such a minimum-regret stable-matching can be called rank-egalitarian stable matching.

A stable marriage maximizing the minimum rank-utiltiy can be computed by reduction to utilitarian stable marriage, but this would require O(n⁴ log n) arithmetic operations. The algorithm described by Knuth (which he attributes to Alan Selkow) runs in time O(n⁴).

Gusfield developed a faster algorithm, that finds a minimum-regret (rank-egalitarian) stable marriage in time O(m) = O(n²). He also presented algorithms for closely related problems:

• Computing every man-woman pair that is contained in at least one stable matching, in time O(n²).
• Finding all "rotations" (transformations from one stable matching to another) in time O(n²).
• Enumerating all stable marriages, in time O(n² + n|S|), where |S| is the number of stable matchings, and space O(n²).

Lexicographically optimizing the rank-profile

Two different optimization criteria are based on lexicographic optimization of the rank-profile of the matching. The rank-profile of a matching is a vector in which the k-th element counts the number of agents who are matched to their k-th best option.

The first criterion is an adaptation of the rank-maximal matching criterion to stable matchings. A rank-maximal stable matching is a matching that maximizes the number of people who get their best option (1st rank); subject to that, maximizes the number of people who get their second-best option (2nd rank); and so on.

• Irving, Leather and Gusfield show that a rank-maximal stable marriage can be computed by reduction to utilitarian stable marriage: each agent i assigns to his/her k-th best choice, a utility of n^n-k. Then, any matching maximizing the sum of utilities, also lexicographically maximizes the rank vector. The run-time is O(m² log K), where K here is in O(nⁿ), so log K is in O(n log n) and the actual runtime is in O(n m² log n) = O(n⁵ log n).
• Feder presents a faster algorithm for rank-maximal stable marriage, that does not require exponential weights, and runs in time O(n^1/2 m^3/2) = O(n^3.5).
• Cooper and Manlove present an algorithm for computing a rank-maximal stable marriage. Instead of using exponential weights, they use vector weights. Their algorithm runs in time O(n m² log n) = O(n⁵ log n), but the use vector weights allows a substantial decrease in the required memory; in their experiments, the memory requirement is 10 to 100 times smaller.

A second criterion, that can be seen as a dual of the first, is generous stable matching. It minimizes the number of people who get their worst option (n-th rank); subject to that, minimizes the number of people who get their second-worst option; and so on. Note that this is a strictly stronger condition than rank-egalitarian ("minimum regret") stable matching. It could be called lexicographic rank-egalitarian stable matching. It is similar to lexicographic max-min optimization (leximin) of the utility vector, where the utilities are minus the ranks.

• A generous stable marriage can be computed by reduction to utilitarian stable marriage, using exponential weights.
• Cooper and Manlove present an algorithm for computing a generous stable marriage with vector weights instead of exponential weights. Their algorithm runs in time O(min(m,n d)² d log(n)), where m is the total length of the preference lists and d is the maximum (worst) rank. As d is in O(n) and m is in O(n²), the worst-case run-time is in O(n⁵ log(n)), as for rank-maximal stable marriage.

Fleiner, Frank and Kirali study stable marriage with strict preferences. They define a condition they call level fair. Each agent assigns to every agent of the other group an integer between 1 and 2*|Est|, where Est is the set of stable edges (edges that appear in some stable matching). Higher level is better. A matching is called level-fair if it minimizes the number of agents with level 1; subject to that, minimizes the number of agents with level 2; and so on. Level-fair stable matchings can be found by reduction to utiltiarian stable matchings with exponential weights, but the authors present a different approach that does not require exponential weights.

Median stable matching

A median stable matching is a stable matching in which each agent is matched to his/her median partner (median taken over all partners of the agent in stable matchings).

Balancing men and women

Irving, Leather and Gusfield define two criteria that explicitly aim to balance the utilities of the two sides of the market - men and women:

• A sex-equal stable matching minimizes the difference between the sum of rank-utilities of all men, and sum of rank-utilities of all women.
• A balanced weighted stable matching minimizes the maximum between the sum of utilities of all men, and the sum of utilities of all women.

Both these problems are NP-hard even in the bipartite case, even in the case of rank utilities. But there is a 2-approximation algorithm with run-time O(n²), even for general utilities.

One-to-many and many-to-many optimal stable matching

Utilitarian stable matching

Eirinakis, Magos, Mourtos and Miliotis study optimal stable matchings in the many-to-many ("workers-firms") setting. They assume that each worker-firm pair has a cost, and aim to minimize the total cost of assignments, subject to stability (they define several notions of stability for the many-to-many setting).

Csaji and Sun extend these by allowing each institute (e.g. firm) to define an arbitrary (not necessarily additive) utility function on sets of workers. Such functions can encode e.g. diversity constraints (maximize smallest number of residents per sector), complementarity constraints (maximize couples / siblings matched to the same institute), etc. They prove that, for each institute, the number of different "stable sets" (sets of residents that can be matched to it in a stable matching) is linear in n, and they can be enumerated efficiently. Moreover, each stable set has a unique worst resident. Hence, for any utility function on sets, one can compute in polytime an additive utility function on residents, that yields the same utility for sets. Then, any utilitarian stable matching algorithm can be applied to maximize the sum of utility functions over all institutes.

To maximize the smallest utility of an institute, one can run utilitarian stable matching iteratively with an increasing threshold, and modified utility functions that equal 1 when the original utility is at least the threshold and 0 otherwise.

The techniques can be extended to two-sided many-to-many matchings, where each agent on one side has arbitrary utilities on subsets of agents on the other side.

Leximin stable matching

Narang, Biswas and Narahari study many-to-one matchings, and aim to find a stable matching that is lexicographically max-min optimal for agents on both sides, among the set of stable matchings. Suppose there are n₁ agents on the "one" side (e.g. colleges) and n₂ agents on the "many" side (e.g. students). Their computational results are:

• For ranked and isometric valuations: with strict preferences - O(n₁ n₂); with weak preferences - strongly NP-hard when n₂=3n₁.
• For ranked valuations - with strict preferences - O(n₁² n₂²); with weak preferences - APX-hard.
• For general valuations - with strict preferences - NP-hard; with weak preferences - APX-hard.
• For general isometric valuations with n₁=2 (only two colleges): with strict preferences - O(n₂²); with weak preferences - NP-hard (by reduction from balanced partition: given an instance P, they construct an instance with two colleges with isometric valuations, such that P has a balanced partition iff the leximin-optimal solution allocates a high value to both colleges).

Some of their algorithms are implemented in the fairpyx Python library.

Non-bipartite optimal matching

In the non-bipartite case (the stable roommates problem), the known results are as follows:

• A rank-egalitarian ("minimum regret") stable matching can be found in time O(n²).
• Computing a rank-utilitarian stable matching is NP-hard. Its approximation ratio is the same as that of the minimum vertex cover problem.
• Computing a utilitarian stable matching with general utilities is NP-hard, but there is a 2-approximation algorithm with run-time O(n²).
• Computing a rank-maximal or a generous stable matching is NP-hard. Moreover, even finding a stable matching that maximizes the number of agents matched to their top choices, or minimizes the number of agents matched to their d-th choice (without the lexicographic extension), is NP-hard.