How do you pair up two sides of a market so that nobody wants to switch?

You pair them so that no two people on opposite sides would both rather have each other than the partners they got. That property is called stability, and it is the whole point: a matching is stable when there does not exist any pair where both prefer each other to their current partner. If an unstable pair existed, the two of them would have every reason to leave their matches and team up.

It is not obvious that such a pairing always exists. In 1962 David Gale and Lloyd Shapley proved that, for any equal number of participants of each type, it is always possible to find a matching in which all pairs are stable, and they presented an algorithm to do so. Picture it as a dance of proposals. In the first round each unengaged person on one side proposes to the person on the other side they prefer most, and each person who receives offers answers "maybe" to the best suitor and "no" to the rest. Engagements are provisional: someone engaged can trade up when a better offer arrives, and the dropped suitor proposes again to the next name on his list. The process repeats until everyone is engaged.

The algorithm is best known for assigning graduating medical students to their first hospital appointments. Odd twist: in 1984 Alvin Roth observed that essentially the same algorithm had already been in practical use since the early 1950s, as the "Boston Pool algorithm" used by the National Resident Matching Program. The theory had caught up with a working market, not the other way round. In 2012 the Nobel Memorial Prize in Economic Sciences went to Shapley and Roth for the theory of stable allocations and the practice of market design.

The story is often told as marriages between men and women, but that metaphor has been criticized as both sexist and unrealistic: the algorithm's steps do not reflect typical human behavior. It is a tool for markets, not for love.