# The Mathematics of Dating

This class normally covers a few mathematical problems that have implications to one's dating life. The problems vary based on how much time is left and the previous knowledge of students. Some problems that have been taught in the past follow.

## Secure Dating Protocol

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^{1}^{1} 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.

## Stable Marriage Problem

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.

## The Secretary Problem

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.

^{1}

Why is this so important? The world may never know; high schoolers are weird.