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 preffered Gift X, but is assigned to 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.

Mom 2 is assigned to Gift X instead of Mom 1

In order for her to not have her best possible gift, there must have been a stable pairing possible that gave Mom 1 Gift X. We already know that Gift X has a priority to be with Mom 2 over Mom 1. A stable pairing between Mom 1 and Gift X is only possible if Mom 2 (Gift X's more ideal pair) is already partnered with another gift. This means that there must be a Gift Y that Mom 2 prefers even to Gift X. But that means that Mom 2 would have already requested Gift Y, who has already rejected her. This is where the contradiction lies. We stated that Mom 1 must have been the first woman rejected by a possible gift match.

Mom 2 MUST have already been rejected by Gift Y, thus proving the theorem by contradiction

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.

This proof I'll leave as an exercise to our readers, though I know solutions exist on the internet. Please leave a comment with your process for Theorem 3! Or, as always, please leave a comment if you have any questions or concerns about the post. I think the most important thing that I've learned from creating this video is that a group of moms might end up a lot happier with a Mother's Day gift if they're allowed input on a group of gifts!