# The Center of Math Blog

DO the math, DON'T overpay. We make high quality, low-cost math resources a reality.

## Friday, May 8, 2015

### Mother's Day Special: Variation of the Simple Marriage Problem

One of my favorite things to do at the Center is create video content for fun math topics. The intern here before me did two "Holiday Specials" around Thanksgiving and Christmas, and I decided to continue his work! One of my first math videos was the Valentine's Day Special: Monty Hall problem. That one was a lot of fun.

This Sunday is Mother's Day (hi Mom!), so I took a math topic that I think is fun and themed it to fit the holiday. The Stable Marriage Problem is the famous mathematical scenario that we chose. Instead of a small village that has 10 women and 10 men who need to be paired in matrimony, we used mothers and the presents that their children picked out for Mother's Day.

So let's imagine that we have 5 mothers and 5 kids that want to put together a party. The children go out and buy five gifts. Now, the kids decide that in order for the moms to be as happy as possible with their gifts, they should give the moms some input in deciding what gift they want.

The moms are able to see each of the five gifts, and rank their choices from first to last. The kids make their rankings as well- each of them picks their own mother first, but then ranks their second to last choice behind them. Our question is this: Is it possible to arrange mothers with gifts so that each pair is stable and every mother and child is as happy as they can be? Then the Gale-Shapely algorithm begins! Make sure you've seen the video to get the idea of how the algorithm works. If you'd prefer a written explanation of the algorithm process, I really like this slideshow by Dr. Emily Riehl of Harvard University.

 The chalkboard after the algorithms were both completed.
The last thing I did in the video was go through the algorithm again, but with the gifts proposing the possible pairings. When we went through this way, the results were totally different. But, it seems that no Mom is in a position where she can reject her offer for a better one. Therefore, the algorithm (which ended after only one round!) is complete, and stable.

As I alluded to in the video, there are a couple extremely interesting results of this problem, which I'll describe as a few theorems and their proofs.

Theorem 1: The algoritm arranges stable pairings.

Proof 1: Each of the kids' gifts that a given woman preferred to her final gift rejected her in favor of a match it preferred.

If a situation arised where a woman preferred a certain gift to one she recieved at the end of the algorithm, we know that she had already been "rejected" by that gift and it went to a mother that the child had ranked higher for that gift. We'll find that whenever the algorithm terminates, we've reached a stable match because nobody can do better than they've already done in this scenario.

Theorem 2: The algorithm assigns every mother their best possible gift.

This means that in this scenario, no woman could have ended up happier than with the arrangement we ended with.

Proof 2: We can use proof by contradiction to describe this. We'll start by assuming that a woman (Mom 1) was not assigned her best possible gift. Mom 1 must have been the first person rejected by a possible gift (Gift X) that she originally wanted, and so is assigned to the Algorithm Gift.

Mom 1 prefers Gift X, but does not recieve it. This means that there was another woman, Mom 2, who requested Gift X who was higher on Gift X's list, meaning that Gift X rejected Mom 1.

This is not an easy proof to understand because of the logic and steps that go into it (remember Cheryl's Birthday?), but with some critical thinking it becomes clear.

Theorem 3: The algorithm assigns every gift with its worst possible mother pairing.