pear’s Matching Algorithm – Behind the Scenes
If you 're asking yourself how this application really works, what makes it different from everything else on the market, then this is the post to read.
pear is simple and fun to use, but what goes on behind the scenes is much more complicated. We employed an algorithm that D. Gale and S.L. Shapley developed in a paper published in 1962, titled "On the stability of marriage", and later honoured with a Nobel Prize in Economics. Although the algorithm is currently used in a variety of settings (e.g. to allocate medical students to hospitals in the US), it has never been used for the purpose we like to think it was intended for by its creators: a dating app.
Gale and Shapley showed that a simple mechanism, called "the deferred acceptance algorithm", was able to produce matches between men and women that are optimal, better or "stable", in the sense that when everybody has been allocated a partner by the algorithm, it’s not possible to find two people who are not matched together, who prefer each other to their current partners.
How does the algorithm work?
OK, so we have now a set of users and each of them has a ranking over users of opposite sex. What does the algorithm do at this stage to produce a stable matching?
To get this point across, let’s assume that there are just three men and three women. The name and preference rankings of the men and women in our example are shown in the figure below.
What we describe now happens in the background, so users don’t get to see it. Our servers run the deferred acceptance algorithm using the preferences that are delivered by the binary comparison (this is when you pick a user over another).
In the first step of the algorithm, all the women propose to their most preferred man (i.e., we take each woman and we provisionally match her with her most preferred man). Recalling the preferences from the table above, this is represented below, where an arrow represents a proposal from a woman to a man.
As you can see from the picture above, both Ann and Beatrice opt for Charles, while Chloe opts for Brian.
In the second step of the algorithm, all men decide which proposal to keep, if they have more than one proposal. We do so on their behalf, and we let each man retain the proposal from the woman he ranks highest. So, in this example, Charles accepts Beatrice’s proposal and rejects Ann’s since Beatrice is higher in his ranking than Ann. Brian accepts Chloe’s proposal since it is the only one he received. In the picture below the rejection of a proposal is shown by a crossed arrow.
If after this first step not everyone has been pear-ed, the algorithm proceeds with a second round of proposals. Women whose proposal had been rejected make another proposal, and only to men to whom they have not proposed yet. The only woman that is still single is Ann, so she proposes to her second highest ranked man, which is Brian. Now, since Brian prefers Ann to Chloe, he leaves the latter one and accepts Ann’s proposal. The situation now looks as follows.
Finally, Chloe is single and she now proposes to Alex, who has no other proposal. We have now a stable matching, and three couples.
In this example, the algorithm terminates quite quickly, but in general it may take several steps of proposals for it to converge to a stable matching. The good news is that the algorithm indeed terminates in finite time and converges to a stable matching. This is essentially the celebrated result of Gale and Shapley.
It is not difficult to see why the algorithm terminates: in each turn women that are still single must choose men that have not chosen before. As the number of men is finite, there are only so many requests that can be made and the algorithm must terminate.
It’s easy to verify that the couples we have produced are stable in the sense we have specified. That is, if someone is not matched with his or her first choice, then the first choice must be matched to someone she or he prefers to him or her. This also applies to the second choice when someone is matched to his or her third choice. For instance, Chloe is matched with Alex, her second choice. This is because her first choice, Brian, prefers to be match with Ann, who is higher in ranking with respect to Chloe.
With a bit of irony, as XCDC puts it: