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 = n2, so the run-time is O(n2). 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(m2) = O(n4). 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(m2 log K) = O(n4 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(m2 log n). A later algorithm by Orlin (2013) requires only O(|V| |E|) time, which leads to an O(m2) = O(n4) 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 K + K log 2 m ) {\displaystyle O(m{\sqrt {K}}+K\log ^{2}m)} , where K is the maximum flow size. The second one runs in time O ( w m log K ) {\displaystyle 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 log2K 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 K + K log 2 m ) {\displaystyle O(m{\sqrt {K}}+K\log ^{2}m)} and O ( n m log K ) {\displaystyle 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=n2, so the run-times are O ( n 2 K + K log 2 n ) {\displaystyle O(n^{2}{\sqrt {K}}+K\log ^{2}n)} and O ( n 3 log K ) {\displaystyle 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 ) {\displaystyle O(m^{1.5}+m\log ^{2}m)=O(m^{1.5}+m\log ^{2}m)=O(n^{3})} .
… excerpt ends here. Continue reading the full article.
