The math, for the curious

Seating a speed-dating night sounds simple, until people can meet whoever they like. Here's what happens behind the "Next round" button.

1. A night is a graph

Picture every guest as a dot. Draw a line between two dots when both would like to meet the other. That's a graph. In a classic night there are two sides, men and women, and lines only go across. As soon as some guests want to meet "everyone", or someone of their own gender, lines appear within a side too, and there are no clean sides anymore.

2. Each round is a matching

A round picks some of those lines so that everyone is on at most one: that's called a matching. Of all possible matchings, we want the best one. Every line gets a weight (a score), and the app picks the matching with the highest total, a maximum-weight matching.

With two clean sides that's a well-known, easy problem. Without them, odd loops like the triangle above (called blossoms) can fool simple methods. Jack Edmonds solved it in 1965 with the blossom algorithm^[1][2]: when it finds an odd loop, it temporarily shrinks it into a single dot, solves the smaller problem, then opens it back up. Shapley Match uses it every round, in a fast version of the method^[3][4]. For a bar with 100 guests it takes a fraction of a second.

3. The weights are where fairness lives

A line between two guests who can meet tonight is worth:

• No line at all if they already had a date tonight, or the host said to keep them apart.
• 10,000 per date is so large that the best matching always has as many dates as possible.
• The waiting bonus makes people who sat out more often more valuable to pair, so breaks get shared fairly.
• The random bit breaks ties, so equal options don't always come out the same way.

When there are fewer tables than possible dates, the app adds pretend "sit-out" spots that are worth more than any date. The algorithm fills those first, so exactly the right number of people take a break, and it picks the best dates among the rest.

4. Tables: the fewest people standing up

Once the pairs are chosen, each pair needs a table. Putting a pair at a table costs 0 if both are already sitting there, 1 if one is, and 2 if neither is. Finding the cheapest overall placement is the assignment problem, solved by the Hungarian algorithm (Kuhn, 1955)^[5][6]. Pairs are always chosen first and tables second, so a better date never loses to a shorter walk. On a balanced night, about one person per table moves.

5. The end of the night: stable connections

A mutual like is a match. If you have several matches, you put them in order. Then everyone gets at most one connection, and the result is stable: there are never two people who would both rather be with each other than with who they got.

For two sides this is the famous Gale–Shapley problem (1962)^[7], work that earned Lloyd Shapley a share of the 2012 Nobel Prize in Economics^[8]. That's where Shapley Match gets its name. With one mixed group it's the stable roommates problem, solved by Irving's algorithm (1985)^[9][10]. One catch: sometimes no stable answer exists. If Ana prefers Bea, Bea prefers Cleo and Cleo prefers Ana, someone is always unhappy. In that rare case Shapley Match falls back to the pairing that's best for everyone's rankings overall.

In numbers

Every step is checked in our tests against trying every possible answer on thousands of random small groups.

References

1. J. Edmonds (1965). “Paths, trees, and flowers.” Canadian Journal of Mathematics, 17, 449–467. doi.org/10.4153/CJM-1965-045-4
2. J. Edmonds (1965). “Maximum matching and a polyhedron with 0,1-vertices.” Journal of Research of the National Bureau of Standards, 69B, 125–130. doi.org/10.6028/jres.069B.013
3. Z. Galil (1986). “Efficient algorithms for finding maximum matching in graphs.” ACM Computing Surveys, 18(1), 23–38.
4. J. van Rantwijk. “Maximum Weighted Matching” (reference implementation, public domain), which Shapley Match’s code follows. jorisvr.nl/article/maximum-matching
5. H. W. Kuhn (1955). “The Hungarian method for the assignment problem.” Naval Research Logistics Quarterly, 2(1–2), 83–97. doi.org/10.1002/nav.3800020109
6. J. Munkres (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38.
7. D. Gale and L. S. Shapley (1962). “College admissions and the stability of marriage.” The American Mathematical Monthly, 69(1), 9–15. doi.org/10.1080/00029890.1962.11989827
8. The Royal Swedish Academy of Sciences (2012). “The Prize in Economic Sciences 2012” to Alvin E. Roth and Lloyd S. Shapley, “for the theory of stable allocations and the practice of market design.” www.nobelprize.org/prizes/economic-sciences/2012/summary/
9. R. W. Irving (1985). “An efficient algorithm for the ‘stable roommates’ problem.” Journal of Algorithms, 6(4), 577–595. doi.org/10.1016/0196-6774(85)90033-1
10. D. Gusfield and R. W. Irving (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press.