The Talking Stick Blog

News, Updates, Program Recaps, and Homeschooling Information

Stable Marriage, part 2

(October 5, 2017) We continued work on the Stable Marriage Problem today. After a discussion of the field of mathematics known as game theory, I put on the board the Jane Austen example that Emily Rhiel used in her Numberphile video. Six students used this example to teach the Gale Shapley algorithm to two students who had not been in attendance last week. Several students were familiar with the characters from Pride and Prejudice and were intrigued by Dr. Rhiel's set up of the problem. I suggested they find her online and email her. Everyone had a lot of questions about how the algorithm supposedly favors one side. They wanted to run the algorithm in different orders to test their conjectures, so we did.

Unlike last week, today I came well prepared for these questions, thanks to Ted Alper of the Stanford Math Circle. I had reached out to the 1001 Circles Facebook group for help with this problem, and Ted came to my rescue with another example that better illustrates this characteristic of the algorithm.* The students did the new example, saw what was going on, and then we moved into another discussion of the practical applications of this theoretical model. Last week talked about matching doctors to hospitals. This week we discussed an article (by the Royal Swedish Academy of Sciences) that further explained why this algorithm was Nobel worthy and what others did with the algorithm to extend it.

One thing that we talked about doing last week was continuing the proofs behind this algorithm. We ended up running out of time. I suggested that the students watch Dr. Rhiel's second Numberphile video ("the math bit") to see the proofs, just in case we run out of time in the course. I hope to return to these next week, but I also hope an interested student or two might want to watch the videos and lead a discussion of the proofs with the group.

In our final 15 minutes, we revisited our project of creating individual college-admissions algorithms. I told the students that my goal is to put their algorithms into an excel spreadsheet so that we can run various hypothetical students through it. “Cool!” was the biggest reply.

Finally, I invited students to let me know after class if they wanted to present any of their own algorithms, or those they’re interested in, or proofs of algorithms (see above, hint, hint!) in our final session in a few weeks. I hope some do!

Rodi

*Ted Alper and Benjamin Leis both responded to my post in 1001 Circles and gave me help. I just love that the math circle community is so supportive. Ted recommends that interested teens read the original article by Gale and Shapley,  “College Admissions and the Stability of Marriage.” I've read it and would encourage this too. During each class session, I talk with the students about what I've posted in these online reports. Often students want to read more about the things we talk about, so please forward them these reports so they have the links. Thanks, parents!