The Talking Stick Blog

News, Updates, Program Recaps, and Homeschooling Information

The Stable Marriage Problem (Gale Shapley Algorithm)

(October 2, 2017) I discovered this problem and was so excited – my students would love it, it directly tied in to the topic of our course, and it was a good example of a mathematical algorithm that all of the students would have sufficient math background to work. I wanted to do it right away, so I discarded my original plans for today, crammed to learn the problem (read 2 short articles and watched 2 short videos), and came to class with my puppets in hand. I presented it in a similar way that Emily Riehl did in her Numberphile videos.

I was right; the class was captivated by the problem. But it turned out that the problem was much deeper than I was prepared for. (I shouldn’t have been surprised by this, since I knew that this algorithm eventually led to a Nobel prize for one of its creators.)

Does the algorithm give the same result if you start with the men? S said yes, M said no. Several students tried to work it out in their heads with our current example and quickly agreed with S (that the answer is yes). M wasn’t so sure. She was adamant that we actually do it out. So we did. And it turned out that with our specific example, we got the same result. It looked like S was right. Until I told them that the algorithm can favor the person who proposes. “Why did our example work out the same?” The prevailing student conjecture was that it was something specific about the order of our lists. They were all too much alike. Another conjecture was that our sample group was too small. I admitted to the students that I don’t know the math behind this problem well enough to answer (I only learned it a week ago), but told them I’d try to find out. My plan is not to just give them the answer to this question next time, but to give them more scenarios so they can discover it for themselves.

We got into the math (theorems and proofs) behind the algorithm. I got confused in one of the proofs (a proof by contradiction); I wasn’t sure whether we were doing it right. It is a short but confusing proof. Some students were following, some had no interest. Sometimes the younger students just check out mentally when the mathematics gets too abstract. The older students wanted to figure it out for themselves but the younger ones had gotten off the bus so to speak. I was glad to notice that we were out of time. We had been working on this problem intensely for 75 minutes without even a quick bathroom break. Had we more time, I would have given a break right then. But it was time to leave. So I promised everyone that we’d start with it first thing next time. This would give me time to learn the proof better.

On the one hand, it might seem that this was not a successful math circle considering that I couldn’t answer all of the questions and got confused in a proof. But I posit that seeing me struggle with math was very good for the students. Students can expect their leaders to be walking Googles, and that creates a distance. It can make it hard for students to see themselves as mathematicians or even problem solvers. So when they get to see how everyone struggles with some things in math, it can give them hope. No students were annoyed with me for not knowing the things I didn’t know. I think it motivated some of them to try to figure it out for themselves.

The students did enjoy using the puppets. This is my first time using them with teens and I was happy that they enabled the students to go deeper into the mathematics than they may have otherwise. There were a few times when the mathematical struggle was a little intense, and then someone broke the tension by making their puppet say something funny.

By the way, I didn’t write a full recap of session 3, so here’s an overview. We finished work on the Google Page Rank algorithm. Students were exposed to some new mathematics – probability distribution – and had a lot of questions and a lot of fun. Then students then developed their own college admissions algorithms for hypothetical colleges of their own design:

  • Kale University (“for really smart people”)
  • Collegiate University of Redundancy
  • Universal University
  • Monster University
  • Redundant School of Redundancy
  • TSU/Top Secret University (“This is not its name; no one knows its name.”)
  • University of the Underworld (“only for people who are dead”)
  • Prison College (“an online school for people serving life sentences”)

Just from the list of schools here, students could already see the dangers of using a single algorithm on a large scale.

To be continued in another session.

Oh, one more thing I wanted to tell you: I’ve been showing students pictures of the mathematicians behind the problems we’ve been working on in this course. It is exciting for them to see so many diverse faces (age, race, gender, and even formality – Emily Riehl’s faculty page shows her playing the guitar in a T-shirt!).

Leave a Reply