Stable pairings and how to find them (Gale-Shapley algorithm and also puppies)

From dating apps to matchmaking in video games, and matching computers to the best servers, matching problems have a notable presence in computer science and game theory nowadays. So let’s look at one of this problems, which has a rather simple premise and a surprisingly simple solution.

The problem deals with finding stable pairing (say, for a date) between a group of n women and n men, given the preferences of each man and each woman.

Wait, before we start let’s change the premise. Instead of men and women, for adorableness sake let’s do matches between people and puppies (for an adorable puppy play session)!

So, first of all, what do we mean by the preferences of each person and each puppy. Well, each person ranks the n puppies from least favorite to favorite. Similarly, each puppy ranks the n people from least favorite to favorite. So in this example with 4 puppies and 4 people, here are the rankings the people gave the puppies:

And here is how the puppies rank the people: (of course, the puppies’ opinion is much more important)

Secondly, what do we mean by ‘stable’ pairings? When doing pairings like this, it’s expected that not everyone is fully satisfied with whomever they are paired to. Say, for example Rexy is paired with Alfred, but Rexy prefers Jenny over Alfred. Rexy would rather be with Jenny then Alfred. But if Jenny is matched say, to Bonnie, she may prefer to be with Bonnie then Rexy. So although the pair Rexy-Jenny is more preferable to Rexy, it is not more preferable to Jenny. If it was more preferable to Jenny, it would be better for Rexy and Jenny to ditch the chosen matching and be together. Then the matching won’t be ‘stable’, as it could break.

So a pairing will be called stable if there are no person and puppy who prefer each to be with the other rather then the pairing chosen to them.

(Formally, a pairing R will be called stable if there are no a,b,c,d such that aRb and cRd and a prefers d over b, and d prefers a over c)

So now that we defined what a stable pairing, let’s see an algorithm to find one. This is called the Gale-Shapley algorithm.

It goes as follows, each of the puppies has an adorable doggie house in which they reside. The people go to the houses and the puppies decide who stays as follows:

At each step, each person, if not already in a house, goes to the house of their favorite puppy who they did not visit already:

Then, each puppy allows their favorite person to stay, and kicks all other people:

The process repeats itself until each person is at a doggie house, and no two people are at the same house. Then each person is paired to the doggie they are in the house of. Let’s see how this algorithm proceeds:

So the final pairing is: Bob-Rexy, Jenny-Bonnie, Rachel-Sugar, Alfred-Booper

(Poor “Bob”, rejected three times and stuck with his least favorite puppy. It’s not like he did something wrong, say scamming people putting them in infinite debt, or something)

Why the algorithm works:

Let’s see why the algorithm indeed results in a stable pairing. It follows from these three properties of the algorithm:

1) If a person goes to a certain puppy’s house, they have been rejected by all puppies they prefer over them. Indeed, each person visits the puppies from favorite to least favorite. So if say, Robert visits Fluffy after Jumpy, it means Robert prefers Jumpy over Fluffy, and that Jumpy rejected Robert, else Robert would still be at Fluffy’s house.

2) If a person visits at a puppy’s house, all future people who stay (not visit, stay means they visit and are not rejected) are more favored by the puppy. Say at one step Maria stays at Tiny’s house, and at a later step Alice stays at Tiny’s house. That means when Alice went to Tiny’s house, Tiny rejected and kicked out whomever was already there, whom are less favored by Tiny. And when the person who was there entered another person who stayed got kicked who are also less favored by Tiny. Repeating this until we get to Maria, we get that Tiny prefers Alice over person 1, person 1 over 2, person 2 over 3, repeating until person k who is Maria. Thus Tiny prefers Alice over Maria.

3) Each puppy who gets visited by someone is has thereafter a person at their house at each future step of the algorithm (so they are in a pair by the end). This is simply because by the algorithms definition, whenever a person leaves a puppies house, another leaves.

Using these properties, let’s see first that the algorithm ends. If there are n puppies and people, each person is rejected by at most n-1 puppies. Else, someone is rejected by all the puppies. So they visited all the puppies. Then by the third property, after getting rejected by all puppies each puppy must have someone at their house. That means there are at least n people at a puppy’s house, plus the very unfortunate fellow who got rejected by all of them. So there are at least n+1>n people, impossible!

Therefore, as for the algorithm not to end it requires for someone to be rejected by a puppy, and since by the previous explanation each person has at must n-1 rejections, we conclude that the algorithm must end by n(n-1) steps as there can be at must that many rejections (n-1 for each of the n people).

Finally, let’s see that the pairing picked by the algorithm is indeed stable. Suppose the contrary, that is that the pairing is unstable. Then there must be four people and puppies, say puppies Rocky and Daisy, and people George and Lisa, such that:

• George is paired to Rocky
• Lisa is paired to Daisy
• George prefers Daisy over Rocky
• Daisy prefers George over Lisa

That is, George and Daisy break the stableness of the pairing. Then by the first property, as George prefers Daisy over Rocky, and is at the end at Rocky’s house, George got rejected by Daisy at one point. But then, Lisa stayed at Daisy’s house after George visited, so by the second property, Daisy prefers Lisa over George. Contradiction to our assumption that Daisy prefers George over Lisa.

We finally conclude the algorithm results in a stable pairing. Q.E.D

Is it fair?

Note that the roles between the people and puppies in the algorithm was not symmetrical, one group visited the houses and another only chose who stays. Unsurprisingly, if we have defined the algorithm by having the puppies be the ones who visit the houses, it would too have resulted in a stable pairing. So a natural question to ask is, does the visiting group have an advantage?

The answer yes, in a way. It turns out that the pairing chosen by the algorithm when people visit is the best stable pairing for the people, and the worst for the puppies. That means that in any other stable pairing, there is a person paired to a puppy less favorable to them, and a puppy paired to a person more favorable to them. And no person is paired to a puppy more favored to them than the one chosen by the algorithm. Similarly no puppy is paired to a person less favored to them than the one chosen by the algorithm. Of course, by symmetry this also means that the pairing chosen by the puppy visiting algorithm is the best for puppies and worst for people.

In the example given here however, the stable pairing chosen when the puppies visit is the same as the one as when people visit. A fun exercise is to show this implies there is only one stable pairing for those puppies and people.

For those familiar with partial orders, we can define a partial ordering on stable pairings where one pairing is higher than the other if it is better for all people. Then the people visiting pairing is the greatest element in the order and the puppy visiting is the least element. Similarly, we can define an order by the puppies’ preferences and get a similar result.

Other similar problems:

There can be many spins at the problem at hand. Say, you can have a different number of people and puppies. Then you can also add the preference of staying alone for each participant. Another alternative is having the pairing done from a single party. Say pairing the puppy’s to another puppy to play with, given each puppy’s preferences on the other puppies. Rather unfortunately for that case, a stable pairing is not guaranteed to exist.

But at the end, for the puppy pairing problem, who cares which puppy goes to whom. After all, all puppies are equally adorable and everyone deserves to pet one!

(Except for Bonnie she is obviously the most adorable doggie ever)