Gale-Shapley and SMP doesn't make sense for Tinder


By: Andy Lee

Between the Vox article and the Verge article which both make passing references to Gale-Shapley there seems to be a popular theory that Tinder uses something like Gale-Shapley as a matchmaking algorithm. While it's certainly possibile that they do and I have no evidence either way, I'm not convinced that it's a particularly good model even if it is the one they use.

There is some existing work on how matches on Tinder are not actually stable and it delves into the more rigorous explanations as to why. I won't be focusing on that since it's readily available already. Instead I'll present some of my informal thoughts on the problems with modeling Tinder as an SMP. These thoughts don't necessarily apply to all dating mediums though, a sufficiently clever mechanism designer could probably circumvent all of these.

Relaxing assumptions


For the sake of simplicity we assume there are two bipartite groups on Tinder. We will also assume they are similar in size. We will also assume that people are truthful, both in terms of their self-representation and of their own represented preferences. The assumption on truthfulness is actually not too outlandish.

Intrasex intersex competition



The asymmetries between how men and women find partners differently are well documented. Women are more selective and care more about charaterestics of their potential partners whereas men are less selective. This is well illustrated by this study on education level and success on Tinder. Given this we cannot reasonably expect matches on Tinder to be one to one. The set of male users will be significantly more willing to substitute matches than the set of female users. Thus Tinder must optimize for many to many matches. This takes us away from matchings in the graph theoretic sense. What's more is the empirical evidence suggests that likes are roughly Pareto distributed amongst men. Women perhaps fair a bit better. What these two points suggest to me is that Tinder matching is less a matching problem and more a recommender problem. Instead of queueing profiles which Tinder believes will create stable matchings it is far more likely the case that Tinder is just recommending profiles that it believes you will like.

Alternative models



One fun alternate model is the multi-arm bandit. Consider the problem from some user Alice's perspective. Here the bandits are split into two tiers. There are profiles which have not been seen and there are profiles which have already been matched with. Over all new, unseen profiles there is some distribution of how much utility Alice stands to gain by liking these profiles. This may come from the self-validation of having someone you liked like you back or from expected utility gained from interacting with them in the event of a match. Tinder is designed such that there is virtually no risk and no consequence to swiping right and so there is no disutility gained from liking someone (except expected disutility from interacting with someone whom Alice does not expect to like though we assume Alice on "likes" people who she actually likes). Thus for most users the desire to explore in this tier will be high.

The second tier of users is those whom Alice has already matched with. Here there is a real cost to interacting with her matches: she has to spend time to respond to conversations and expends mental energy on trying to think of responses. Thus she must be more selective in how she allocates her time. Here the standard multiarm bandit model comes through. Each unit of time spent interacting with a match is equivalent to pulling the arm of the bandit. The explore-exploit function here will be more dependent on Alice perseonally. There is a potential spillover into the first tier however as if Alice spends an extremely large amount of time in this tier she may become less likely to spend time in the unknown profiles tier.

What this implies for Tinder is that how profiles are queued should not be based on trying to create stable matchings but instead on trying to show users the most likely gratifying profiles. This could range from the most physically attractive (based on observed swiping behavior) to the most conversationally compatible (based on observed messaging behavior).

If you have any thoughts this site has comments now.

--------------------------------------------------------
Last Edited: 2020-02-04
View Count: 390