The Mathematics of Dating

At a high school party, some individuals are romantically interested in others. But because this is high school, it is absolutely central that you find out if your romantic interest is interested in you without letting on whether you yourself are interested¹ [¹ Why is this so important? The world may never know; high schoolers are weird.]. Normal people rely on signals, hints, and elaborate ruses. Being mathematicians and computer scientists, we've got a better idea: cryptography can give us a protocol wherein you find out if the other person is interested only if you are. Here are some references that have the same material; no reason to copy good content into here.

• Notes from U.C. Berkeley's CS276: Cryptography
• Notes from MIT's 6.045: Automata, Computability, and Complexity Theory

If we have \(n\) women and \(n\) men, how can we match them with each other into partnerships? Imagine that each man and woman can rank all members of the opposite sex by how attractive a partner they are. Can a matching be made so that no two people would prefer to be with each other than their partners? It turns that an algorithm exists which always produces such a "stable" matching. But there are multiple such stable matching, and it turns that the people making proposals to potential partners are the ones which get the best outcome in this algorithm, teaching us all an important lesson about not being afraid to approach that one guy/girl.

• Wikipedia's description of the Stable Marriage Algorithm, which also describes the optimality of the solution for the men and women.
• Wikipedia on the Stable Roommate Algorithm, wherein you don't have to match people by gender. This problem is much harder – for example, it need not even have a stable solution. There is also a much more complicated algorithm to find a stable matching if it exists.
• A research project at the University of Glasgow, which investigated various algorithms for Stable Marriage, and which stable matchings they choose.

Imagine we have a long list of potential dates. We can date each for, say, a few months, after which we can rank that date relative to all the previous ones. After each date, we can either commit to that date as a partner, or break things off permanently (you aren't allowed to rekindle relationships). How can one maximize their possibility of committing to their best-matched date? It turns out that a sufficiently clever approach can give one the optimal partner more than a third of the time, no matter what order the dates are dated. We'll expand on this principle to discuss why you shouldn't start looking to get married until approximately 24.

• Wikipedia on the Secretary Problem; Wikipedia has information on a variety of similar problems and on generalizations of the Secretary Problem.
• The Odds Algorithm, which solves a general class of similar problems.
• Stein, W.E.; Seale, D.A.; Rapoport, A. (2003). "Analysis of heuristic solutions to the best choice problem". European Journal of Operational Research 151: 140–152. This paper analyzed various heuristic approaches to the secretary problem, ones ordinary people might use when confronted with this problem in practice.