It's ironic that the original setting for the Gale-Shapley algorithm was the stable marriage problem, where it finds a stable matching between n men and n women in O(n^2) time, but what defeated it in its most prominent application, matching med students to hospitals for residency, was *actual love*, between med students who would only accept residences if they could go together. Factoring couples makes the problem NP-complete.