Seph Lietz

Stable Matching Problem

Imagine a scenario where there are exactly n boys and exactly n girls. Each boy has a ranking of each girl, from most preferred to least. Likewise, each girl has a ranking of each boy. There are no ties, so that each boy has a list of girls of length n, and each girl has a list of boys of length n.

How should each boy and girl be paired?

A stable solution will be one where all pairs are stable. For a boy-girl pair, (b, g), to be stable, it must be true that b prefers g to every other interested girl, where interested means that she would prefer b to her current partner. If a pair is stable, then there will be no motivation for them to split. It is important to understand that this does not mean that each boy must be paired with his most preferred girl, only that no other girls that he prefers (with respect to his current girl) also prefer him (with respect to her current boy).

A perfect solution will be one where each boy has one, and only one, partner. Since the number of boys and girls are equal, then the converse is also true.

Gale-Shapley Algorithm

Some, what should be easy to read pseudo-code:

while (totalUnpaired(boys) > 0) {
	for (each b in boys) {
		// choose the highest girl that b has not proposed to
		let g = b.nextHighestGirl()
		if (g.engagedTo == null || g.engagedTo == b) {
			b.engagedTo = g
			g.engagedTo = b
		} else {
			let b' = g.engagedTo
			if (g.rank(b') > g.rank(b)) {
				// do not ask this girl again
				b.forgetGirl(g)
			} else {
				b.engagedTo = g
				g.engagedTo = b
				b'.engagedTo = null
			}
		}
	}
}

Gale-Shapley terminates in at most n^2 iterations and it guarantees at least one solution that is both stable and perfect. Furthermore, the algorithm is optimal for the boys. Each boy is paired with his highest possible partner, given a stable pairing. Each girl is paired with her lowest possible partner. This does not mean that each boy is paired with the girl ranked first on his list, but that he will be paired the highest realistic girl, where realistic means in a stable solution. And vice versa for the girls.