In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is not stable if: There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and also prefers A over the element to which B is already matched. In other words, a matching is stable when there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched.

Complexity

  • Time:

References

Implementations

  • 1

    # TODO: Implement in Python

  • 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

    const ARank = {
  Flavio: ['Valentine', 'July', 'Summer', 'Violet'],
  Stephen: ['Summer', 'July', 'Valentine', 'Violet'],
  Albert: ['July', 'Violet', 'Valentine', 'Summer'],
  Jack: ['July', 'Violet', 'Valentine', 'Summer'],
};

const BRank = {
  July: ['Jack', 'Stephen', 'Albert', 'Flavio'],
  Valentine: ['Flavio', 'Jack', 'Stephen', 'Albert'],
  Violet: ['Jack', 'Stephen', 'Flavio', 'Albert'],
  Summer: ['Stephen', 'Flavio', 'Albert', 'Jack'],
};

function init(rank) {
  const o = {};
  for (const k in rank) {
    o[k] = {
      key: k,
      stable: false,
      rankKeys: rank[k],
    };
  }
  return o;
}

function extractUnstable(Q) {
  for (const k in Q) {
    if (Q[k].stable === false) {
      return Q[k];
    }
  }
}

const A = init(ARank);
const B = init(BRank);
let a;

while ((a = extractUnstable(A))) {
  
  logTracer.println(`Selecting ${a.key}`);
  Tracer.delay();

  const bKey = a.rankKeys.shift();
  const b = B[bKey];

  logTracer.println(`--> Choicing ${b.key}`);
  Tracer.delay();

  if (b.stable === false) {
    
    logTracer.println(`--> ${b.key} is not stable, stabilizing with ${a.key}`);
    Tracer.delay();

    a.stable = b;
    b.stable = a;

  } else {
    const rankAinB = b.rankKeys.indexOf(a.key);
    const rankPrevAinB = b.rankKeys.indexOf(b.stable.key);
    if (rankAinB < rankPrevAinB) {
      
      logTracer.println(`--> ${bKey} is more stable with ${a.key} rather than ${b.stable.key} - stabilizing again`);
      Tracer.delay();

      A[b.stable.key].stable = false;

      a.stable = b;
      b.stable = a;

    }
  }
}