Sun, 17 May 2009
Bipartite matching and same-sex marriage
My use of the identifiers husband and wife in Thursday's example code
should not be taken as any sort of political statement against
same-sex marriage. The function was written as part of a program to
solve the stable bipartite
matching problem. In this problem, which has historically been
presented as concerning "marriage", there are two disjoint
equinumerous sets, which we may call "men" and "women". Each man
ranks the women in preference order, and each woman ranks the men in
preference order. Men are then matched to women. A matching is
"stable" if there is no man m and no woman w such that
m and w both prefer each other to their current
partners. A theorem of Gale and Shapley guarantees the existence of a
stable matching and provides an algorithm to construct one.
However, if same-sex marriages are permitted, there may not be a stable matching, so the character of the problem changes significantly.
A minimal counterexample is:
| A prefers: | B | C | X |
| B prefers: | C | A | X |
| C prefers: | A | B | X |
| X prefers: | A | B | C |
Suppose we match A–B, C–X. Then since B prefers C to A, and C prefers B to X, B and C divorce their mates and marry each other, yielding B–C, A–X.
But now C can improve her situation further by divorcing B in favor of A, who is only too glad to dump the miserable X. The marriages are now A–C, B–X.
B now realizes that his first divorce was a bad idea, since he thought he was trading up from A to C, but has gotten stuck with X instead. So he reconciles with A, who regards the fickle B as superior to her current mate C. The marriages are now A–B, C–X, and we are back where we started, having gone through every possible matching.
This should not be taken as an argument against same-sex marriage. The model fails to generate the following obvious real-world solution: A, B, and C should all move in together and live in joyous tripartite depravity, and X should jump off a bridge.
[Other articles in category /math] permanent link