About a month ago I ran a workshop on Game Theory for Mathematicians. A group of people in the Maths Society were discussing how the best way to learn mathematics is to have someone sit down with you (or stand by a whiteboard) and explain it. I think a large part of that is that you can let them know when you don’t follow something they say (and if you start to look too confused, they pick up on that and slow down). Anyway, we decided that it would be a good idea to run a workshop, aimed primarily at second and third year students, where we would try to teach them some basic advanced ideas (e.g. groups, topology, graph theory) as Socratically as possible. I ended up volunteering to run a workshop on Game Theory, which worked well because it’s a great mathematical area, that isn’t really covered much by undergraduate courses. We had three hours planned and I broke these up into three (roughly equal) segments, Hackenbush, Strategic Game Theory, and Hex. The Hex segment was by far my favourite and I suspect the students’ favourite as well. We didn’t end up proving the main result I wanted to get to, but we had some great discussions about game theoretic ideas. I enjoyed the proof though, and I thought I’d write it down here so I don’t forget it. It’s an interesting game in its own right, and gives a very cool, and relatively easy to understand, proof of Brouwer’s Fixed Point Theorem. (This also lets us prove the Jordan Curve Theorem, which I’ll try to get to in another post).

Brouwer’s Fixed Point Theorem

Brouwer’s Fixed Point Theorem is a handy little thing that pops up all over economics and mathematics. In fact two Nobel Prizes have essentially been awarded to economists for just applying a generalisation of the theorem (Kakutani’s Fixed Point Theorem) to economic problems (Arrow in 1972 and Nash in 1994). (My tongue’s reasonably far in my cheek here, the prize was really awarded for the economic ideas that lay behind this work, the fixed point theorem was just the method by which they proved it). I’ll talk in another post (probably) about why I’m frustrated with how economics treats the theorem (they use it but don’t prove it), and give a very cute (and quick) little proof of it using Sperner’s Lemma, but today I want to show the most intuitive proof I know.

The proof I’m showing here was first shown by David Gale in the paper:

Gale, David. “The game of Hex and the Brouwer fixed-point theorem.” The American Mathematical Monthly 86, no. 10 (1979): 818-827.

I was first introduced to it at the end of a course in higher dimensional real analysis at Auckland Uni. It was the last lecture of term and we were told it would be unassessed (the unassessed stuff always seems more fun). We spent the first quarter of an hour or so just playing Hex (as I remember I was consistently beaten), and then looked at the proof of the Brouwer Fixed Point Theorem. The next year I looked a little bit into topological games (following a very neat seminar by the same lecturer who had run the higher dimensional analysis course) and refound the proof. So when I decided to run a course for mathematicians looking at game theory, it was an obvious choice and a good excuse to force myself to understand the proof.

It all begins by looking at the game of Hex, which is played on a board, much like the one below:

Source http://commons.wikimedia.org/wiki/File:Hex11.PNG, licensed under the Creative Commons Attribution-Share Alike 3.0 Unported

It can be played on various sized boards – John Nash, the inventor, supposedly recommended a 14 by 14 board as the optimal game size. (I’ve wondered whether Nash, who would use Brouwer’s fixed point theorem in his Nobel prize winning work, had noticed the connexion between the two). Continue reading →