4.6.7 Stable Marriage (Gale-Shapley)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/*

The stable marriage problem takes $n$ men and $n$ women, with every person ranking all members of
the opposite group in strict order of preference, and seeks a bijection between the two groups. An
unmatched pair $(m, w)$ is a blocking pair if man $m$ prefers woman $w$ to his assigned partner and
woman $w$ prefers man $m$ to hers. A matching is stable if it has no blocking pair. Unlike maximum
matching, the goal is therefore not to maximize the number of pairs, but to find a complete pairing
that satisfies this stability condition.

The Gale-Shapley algorithm produces a stable matching, and a stable matching always exists. Each
free man proposes to the most preferred woman who has not yet rejected him. A woman provisionally
accepts her best proposal so far and rejects the rest, possibly breaking a previous engagement when
a man she prefers proposes later. Because every man descends his list at most once and each proposal
is constant work after precomputing the women's rankings, the algorithm runs in quadratic time. The
result is man-optimal: every man receives the best partner he could have in any stable matching.

- `stable_marriage(men_pref, women_pref)` returns a vector `wife` where `wife[m]` is the woman
  matched to man `m` in the man-optimal stable matching, given the input preference lists each as
  $n$ by $n$ matrices. `men_pref[m]` lists the women in `m`'s order of preference, most preferred
  first, and `women_pref[w]` lists the men in `w`'s order of preference.

Time Complexity:
- O(n^2) per call, where $n$ is the number of men (equivalently, women).

Space Complexity:
- O(n^2) auxiliary for the precomputed rankings.

*/

#include <cassert>
#include <queue>
#include <vector>

std::vector<int> stable_marriage(
    const std::vector<std::vector<int>> &men_pref, const std::vector<std::vector<int>> &women_pref
) {
  int n = static_cast<int>(men_pref.size());
  assert(static_cast<int>(women_pref.size()) == n);
  std::vector<std::vector<int>> rank(n, std::vector<int>(n));
  for (int w = 0; w < n; w++) {
    for (int i = 0; i < n; i++) {
      rank[w][women_pref[w][i]] = i;  // How woman w ranks each man (smaller is better).
    }
  }
  std::vector<int> next_proposal(n), husband(n, -1), wife(n, -1);
  std::queue<int> free_men;
  for (int m = 0; m < n; m++) {
    free_men.push(m);
  }
  while (!free_men.empty()) {
    int m = free_men.front();
    free_men.pop();
    int w = men_pref[m][next_proposal[m]++];
    if (husband[w] == -1) {
      husband[w] = m;
      wife[m] = w;
    } else if (rank[w][m] < rank[w][husband[w]]) {
      wife[husband[w]] = -1;
      free_men.push(husband[w]);
      husband[w] = m;
      wife[m] = w;
    } else {
      free_men.push(m);  // Rejected; m remains free and will propose to the next woman.
    }
  }
  return wife;
}

/*** Example Usage ***/

using namespace std;

int main() {
  // All three men prefer w0 > w1 > w2; all three women prefer m2 > m1 > m0.
  vector<vector<int>> men_pref{{0, 1, 2}, {0, 1, 2}, {0, 1, 2}};
  vector<vector<int>> women_pref{{2, 1, 0}, {2, 1, 0}, {2, 1, 0}};

  // Cascading proposals leave m2 with w0, m1 with w1, m0 with w2.
  assert((stable_marriage(men_pref, women_pref) == vector<int>{2, 1, 0}));
  return 0;
}