Solving the Dating Problem
The premise of the Black Mirror episode “Hang the DJ” is a walled-off society where people are required to be matched into romantic relationships by an unknown matchmaking algorithm. Given an arbitrary expiration date, each relationship supposedly provides the algorithm with the data to ultimately make the optimal match for the person. But – spoiler alert – in the end, this society is revealed to be a simulation contained within a Tinder-like app that provides people with compatibility scores in the real world. However, the question left unanswered by the episode is what exactly do the compatibility scores mean? How does someone know that 97% compatibility is good when there might be a thousand people out there with whom they would be 98% compatible? Does the simulation get run on every possible pair of users?
Dating is not just about gathering data on compatibility but also about comparing that data across multiple matches. “Hang the DJ” highlights the use of technology to expedite that data collection process, in fact alluding to the idea that technology can be used to instantaneously aggregate and compare the information. Today’s dating apps and websites like Tinder and eharmony are far from being capable of doing that, but by centralizing dating profiles, they do make it easier to collect data quickly and make more comparisons. So in theory, we should be able to find our “soulmate” in a shorter amount of time. But this doesn’t quite seem to be true. While divorce rates in the U.S. have fallen in the past two decades, marriage rates have fallen as well, and people are getting married later. Moreover, you’d be hard-pressed to find a young adult that feels like finding a suitable partner has gotten substantially easier. So what gives?
+++
To answer this, let’s take a look at the Stable Marriage Problem (SMP). The SMP (also known as the Roommate Problem) is a classic problem in computer science and mathematics – given n members of group 1 and n members of group 2 where each member has ranked all members of the other group, match members of group 1 with a member of group 2 such that there are no two individuals who would rather be matched with each other than their current partners. When we’ve eliminated any such pair of wistful individuals, we have a set of “stable marriages”; hence the problem’s name. Of course, SMP captures a number of situations found in the field of economics (generally any time matchmaking within a closed group is required), but the premise models the problem of dating with particular accuracy. This is especially true for communities with defined boundaries like small towns or universities, and perhaps more true for a dating app or website.
As you can probably tell from the number of dates you’ve been on that haven’t yielded your future or current spouse, the SMP is not an easy problem to solve. While SMP is not in the class of “nondeterministic polynomial time” problems (the hardest problems known to humankind), the n² dates required for the Gale-Shapley algorithm is around the best we can do. Constructed in 1962 by two mathematicians, David Gale and Lloyd Shapley, this algorithm proposes a solution to SMP consisting of a number of iterations until all members of group 1 are matched with a unique member of group 2. Each iteration contains the following steps:
(1) Each unmatched member of group 1 proposes to the member of group 2 they prefer most and have not yet proposed to (regardless of whether or not the member of group 2 is “provisionally matched”).
(2) Each member of group 2 tentatively accepts the proposal from the suitor they prefer most and rejects all others.
(3) If a member of group 2 is already “provisionally matched” with a suitor, they will still accept the proposal from a suitor they prefer more, rejecting their current match. The rejected match then becomes unmatched.
(4) After accepting a proposal, a member of group 2 is then “provisionally matched” with the suitor, and likewise, the suitor is “provisionally matched” to them.
You’ll notice that not only is the Gale-Shapley solution time consuming, it’s entirely impractical in real life. Dating is an “online algorithm,” an algorithm that is fed data piece-by-piece forcing it to make decisions with incomplete data. You can’t “provisionally” commit to someone, contingent upon whether someone better comes along. Nor does anyone have a complete list of their dating pool ordered by preference. But even more important, the Gale-Shapley algorithm aims to maximize the overall utility across the entire population. That means that if one person actually does find their optimal match, this might not be part of the optimal solution for the rest of the population. Put another way, Tinder or Hinge might help you meet more people that could be the person you most want to end up with, but the same app might also help that person find someone they prefer more than you, leaving you to continue searching for the next best option in a dwindling pool of candidates.
Obviously, there are plenty of other non-structural factors that make modern dating difficult, from the paradox of choice to the depersonalization of romantic encounters. Yet solutions to the SMP, including Gale-Shapley, illustrate the idea that even if we solve the implementation issues of our current technology-enabled dating system, we are no closer to solving the dating problem holistically. Short of turning dating into an offline algorithm, by running a multitude of instantaneous simulations or reshaping how we view commitment, we do not have the data to optimally matchmake. But maybe that isn’t what we want. After all, dating has always been an individual sport, allowing for natural selection to take place, and trying to maximize happiness could disrupt the natural order with untold consequences.
Published exclusively in Brown Tech Review. Image source.
