Dating Simulator: Stable Pairings and Endless Breakups
Each dot below is a person looking for a partner. People drift toward the people they find attractive, and when two people meet who would each rather be with the other than with their current partners, they leave their partners and pair up. A pairing of people is stable if no two people would rather be with each other than with their partners. With some attractions, no pairing is stable, so the breakups never stop.
Who can be a couple:
- Anyone with anyone: every two people can be a couple (the “stable roommates problem”).
- Two groups: each person can pair only with someone from the other group, shown in the other color (the “stable marriage problem”). With two groups of the same size, a stable pairing exists for every choice of attractions.
How the attraction of each person to each other person is chosen, from 0 to 1:
- Random: chosen independently, so attraction is often one-sided.
- Mutual: each two people are equally attracted to each other.
- Shared ranking: everyone agrees how attractive each person is.
- Custom: values you entered in the table below the plot.
“New attractions” chooses new random values of the same kind.
How much each attraction rises and falls over time around its usual value (the value in the table), like the ebb and flow of real relationships. Each attraction drifts on its own, slowly (over tens of seconds), so a partner can become less attractive for a while, or someone new more attractive, and couples that were stable can break up. An attraction of 0 stays 0.
- Off: attractions stay fixed.
- Small: swings of up to about ±0.1.
- Medium: swings of up to about ±0.2.
- Large: swings of up to about ±0.35.
How much attraction grows for people who are near each other, like the familiarity that comes from spending time together. The increase is largest for people who are touching and fades to nothing at about eight body widths apart. Partners stay close, so their attraction to each other grows too, which works like loyalty. An attraction of 0 stays 0.
- Off: distance doesn't change attraction.
- Small: increases of up to 0.1.
- Medium: increases of up to 0.2.
- Large: increases of up to 0.4.
How much a person's own partner is worth to them, beyond their attraction:
- None: a person leaves their partner for anyone more attractive who wants them back.
- Never leave: once paired, a person stays with their partner.
- Fixed boost: each person's attraction to their partner is increased by a fixed amount.
- Grows over time: the boost grows with the time the couple has been together.
- Boredom: the attraction to a partner shrinks with the time the couple has been together.
- Mixed: half of the people (A, C, E, …) grow more loyal over time, and the other half (B, D, F, …) grow bored.
Hover over a person to see their attractions and their couple's, or click a person to keep following them. Drag a person to introduce them to someone. Filled dots have partners; hollow dots are single. A couple's heart is larger when the partners are more attracted to each other. With fluctuation on, a black heart outline shows the partners' usual attraction, and the solid heart behind it grows and shrinks with their attraction right now. People who were just left by a partner are grayed out while their heartbreak fades.
Breakups per minute counts the breakups in each 5-second interval (0–5 s, 5–10 s, and so on), so it falls to 0 when the pairing settles; the current interval, drawn dashed, steps up with each breakup in it. Total happiness adds up each partnered person's attraction to their partner, plus the happiness of each single person (0 unless set above). Each person who was just left by a partner subtracts the heartbreak cost (0.5 unless set above), which fades exponentially, to about a third after 8 seconds. The happiness settings change only the graph, including its history, not the people's motion. The dashed line is the total happiness of the stable pairing reported above, when one exists, with no heartbreak or loyalty.
Attractions
Each row lists how attracted one person is to each other person, from 0 to 1. Attraction is not necessarily mutual: A's attraction to B is in row A, and B's attraction to A is in row B. The outlined cells are each person's attraction to their current partner. Edit a value to change the attraction. With fluctuation on, the table shows each person's usual attraction, and the attraction at each moment differs from it.
How it works
Each person is a boid, an agent that steers by simple rules, like a bird in a flock. Each person is pulled toward the people they would rather be with than their current partner, and the pull is stronger toward people who are more attractive to them than their partner. The pull is also stronger toward people who want them back. A single person is pulled toward everyone, in proportion to their attraction. People also keep out of the plot's top-right corner, where the info box appears, wander a little, drift slightly toward the middle (unless they are happily paired), keep their distance from people they don't want, and keep from bumping into each other. Partners stay a short distance apart and move together, and a couple in which both partners want someone else follows the partner who is pulled more strongly.
Let $a_{ij}$ be the attraction of person $i$ to person $j$, and let $p(i)$ be the partner of person $i$. Two people $i$ and $j$ who are not partners form a blocking pair if each would rather be with the other than with their partner:
An attraction of 0 means no interest, so people pair only with people they are attracted to. A single person would rather be with anyone they are attracted to than be single. When the two people in a blocking pair meet, they pair up, and their former partners become single. A person who is left by their partner is heartbroken: they are drawn grayed out, they are pulled more weakly toward other people, and their heartbreak counts against the total happiness. The heartbreak decays exponentially, falling to about a third every 8 seconds, and a second heartbreak adds to what remains of the first. After a change of partner, the people involved wait 1.5 seconds before they can change partners again, so that each breakup is visible. A crush that isn't returned doesn't lead to a breakup. A pairing is stable if it has no blocking pairs.
Four people with no stable pairing
Load the example “Love triangle plus D.” A likes B best, B likes C best, and C likes A best, and every person likes D least. Every pairing has a blocking pair:
- If A is with B and C is with D, then B and C prefer each other (B likes C best, and C prefers B to D).
- If B is with C and A is with D, then A and C prefer each other (C likes A best, and A prefers C to D).
- If A is with C and B is with D, then A and B prefer each other (A likes B best, and B prefers A to D).
Whoever is with D wants to leave, and someone in the other couple wants them back. So the couples cycle through the three pairings forever, and D is left in each round. This example is from David Gale and Lloyd Shapley's 1962 paper “College Admissions and the Stability of Marriage.” This page was inspired by the discussion of stable pairings in Algorithms to Live By, by Brian Christian and Tom Griffiths.
When a stable pairing exists
For people who can pair with anyone, Robert Irving's algorithm (1985) decides whether a stable pairing exists and finds one if it does. This page uses it to report, below the plot, whether the current attractions have a stable pairing. Some kinds of attraction have a stable pairing for every choice of values:
- Two groups. Gale and Shapley proved that if each person can pair only with someone from the other group, and the groups are the same size, then a stable pairing exists. Their deferred acceptance algorithm finds one. Breakups in an unlucky order can cycle, but if each breakup is by a blocking pair chosen at random, then the pairing becomes stable with probability 1 (Roth and Vande Vate, 1990).
- Mutual attraction. If $a_{ij} = a_{ji}$ for every two people, then the two people in each new couple are more attracted to each other than the people in the couples they broke up were. So the pairing never returns to an earlier pairing, and it becomes stable after finitely many breakups.
- Shared ranking. If everyone agrees how attractive each person is, then the two most attractive people like each other best, so they form a couple that no one can break up. The next two form the next couple, and so on.
Fluctuating attraction
With the Fluctuation setting on, each attraction $a_{ij}$ rises and falls slowly around its usual value, and each person's attraction to each other person changes on its own schedule. A pairing that is stable at one moment can have blocking pairs a little later, so couples keep breaking up and forming, even when a stable pairing exists for the usual attractions. Loyalty can hold couples together through the ebbs.
Loyalty
Loyalty changes how attractive each person's own partner seems to them. In the plot, more loyal couples are drawn more merged together, and bored couples barely touch. With loyalty, $a_{i\,p(i)}$ in the blocking-pair condition is replaced by
- $\infty$ for “Never leave,” so nobody leaves a partner, and each person keeps the first partner they meet, even if a better pairing is possible;
- $a_{i\,p(i)} + b$ for a fixed boost $b$, so small differences in attraction no longer cause breakups (in the love-triangle example, a boost greater than $0.3$ makes every pairing stable);
- $a_{i\,p(i)} + \min(r t, m)$ for loyalty that grows at rate $r$ up to a maximum $m$, where $t$ is the time the couple has been together, so new couples are fragile and lasting couples become hard to break up (permanent, for $m = 1$);
- $a_{i\,p(i)} - r t$ for boredom at rate $r$, so each couple eventually breaks up, even when a stable pairing exists;
- $a_{i\,p(i)} + r t$ for half of the people and $a_{i\,p(i)} - r t$ for the other half with “Mixed,” so a loyal person can be left by a bored partner.