Matching games in class

Last week after looking at stochastic games we looked at matching games (corresponding to Chapter 15 of my course). There's an awesome video on +YouTube describing the problem:

I thought about possibly getting 6 students to form two groups (a set of reviewers and a set of suitors); ranking each other and then getting the class to put together a stable matching. I thought twice about this though as I'm sure it's the kind of thing that could get me fired so instead I brought 3 toys along to class with me:

• A tech deck (finger skateboard: http://www.techdeck.com/)
• The best teenage mutant ninja turtle: Donatello

Both of those you can see in this picture:

• The third toy I brought was my favourite nerf gun (the 'Praxis'):

I actually named 'her' Zoe; after my wife (+Zoë Prytherch).

Three students ('A', 'S' and 'R') came down and agreed to put together their ranking of which toy they preferred:

- A: Donatello, Zoe, Deck
- S: Zoe, Donatello, Deck
- R: Donatello, Zoe, Deck

I came up with a pretty random preference for the toys:

- Donatello: R, S, A
- Deck: A, R, S
- Zoe: R, S, A


We then discussed possible matchings and allocations of the toys (if we came to a stable one A, R and S could stick with that toy for the rest of the lesson). Here is one example that's close to what was suggested (I didn't record it and I don't quite remember it):

- A gets Donatello;
- S gets Zoe;
- R gets Deck

The thing with this is that Donatello prefers R and R prefers Donatello to their current match so the above is not stable.

After some more discussion we came up with the following stable matching:

We see that whilst A is with his 'least preferred' option (the Deck): no one prefers A to their current matching so A does not have an incentive to change his current matching.

The entire matching is stable because we can't find any pair that has an incentive to move.

In class we then went over the Gale-Shapley algorithm which is an algorithm that guarantees a stable matching. A cool thing is that this algorithm gives (out of all possible stable matchings) the one that is optimal from the suitors point of view and also the worst possible one from the reviewers point of view.

In our case above the matching found is also the matching found through the Gale-Shapley algorithm so sadly for 'A' there is no stable way of matching him to anything but his worst preferred toy and 'S' gets my wife no matter what.