Wednesday, June 11, 2008

The prisoners dilemma

A few weeks ago Taso (new fancy homepage), Tony and I organised the Sydney Theory Day. Among the invited speakers were Peter Bro Miltersen who gave a talk on "Names in boxes". The abstract of the talk can be found here. The short version is:

"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"

If each prisoner examines a random set of 50 boxes, their probability of survival is close to zero. It turns out that there is a very simple schedule that gives the prisoners a 30% chance of surviving. It sounds almost impossible but there's a simple proof that anyone can understand in "7 Puzzles You Think You Must Not Have Heard Correctly" by Peter Winkler.

This semester I've been teaching computational geometry at USyd and I find it hard to get them to properly understand the beauty of expected running times. However, this year I started the lecture by discussing the "Prisoners dilemma" for 20 minutes before I talked about the expected running time of low dimensional LP. And I really believe it had a positive effect. The students seemed to appreciate the simplicity of the arguments a bit more than usual.

Now the challenge is to find a puzzle like this for each lecture. Any tips?

1 comment:

  1. When will CS students start doing a good number of Maths courses ? In an ideal world, they must do at least half a dozen Maths subjects (NOT counting Discrete Maths or Automata Theory)... Some knowledge of Groups, Rings, Fields, Topological Spaces, PDE's is essential... No, continuous stuff such as PDE's or Real Analysis should NOT be ignored... CS theory people must learn and appreciate the continuous stuff too.

    I am working with a theory PhD student now -- this student doesn't even know Linear Programming...

    CS theory should ideally move from CS depts to Maths depts, which is where they actually belong.

    OK, dream over... I am awake now, back to Australia 2008...