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).
Two players, Red and Blue take turns marking a single hex on the board with their colour (once a Hex has been marked as a colour the other player cannot mark it their colour). For concreteness say Blue makes the first move. The first player to connect their two sides by a path of only their colour (note that the board above has been marked with blue and red edges) wins. It should be as obvious as the Jordan Curve Theorem that once one player has won, the other player will never be able to form a path connecting their two sides (Maybe more on the Jordan Curve Theorem later).
A completed game looks something like this:
In this picture blue has won and red has lost.
If you haven’t seen this before I encourage you to play a couple of games with someone, it really gives you some of the intuition as to why Brouwer is true and the frustration of trying to show that it is. I asked the students at the workshop the following questions:
- Does a player have a winning strategy – that is, can red or blue guarantee that they win, if they play as smartly as they can, against anything the other player does. Don’t try to prove this (yet).
- Suppose that there is a winning strategy, who has it? Could both players have a winning strategy?
- Let’s suppose that we play to the point where the board is full. Has someone won, or can this end in a draw?
- Did your proof about the draw rely on the number of red and blue tokens being equal? Suppose we randomly place red and blue tokens on the board, does some player win?
- Is there a winning strategy (now try to use the information above)
The hardest question out of these is the question of whether the game can end in a draw. In fact this is the part of the question that is equivalent to Brouwer’s Fixed Point Theorem. Like a lot of the simple proofs of Brouwer’s Fixed Point Theorem this uses Graph Theory (Mental Note: Is this related to Sperner’s Lemma? If so is there a more general form I can derive?).
The Hex Theorem
is a Hex board, when all hexagons are coloured in blue and red, then there is either a red path connecting the red sides or a blue path connecting the blue sides.
This means that when every hex on a board is filled at least one player must have won. As the players take alternate terms and the game is finite (an
board will be filled in moves, this means one player must have completed their path first, and hence won.
Proof of the Hex Theorem
Hex-board, and suppose that every hex is coloured. Then let be a graph, where the vertices are the vertices of the Hex board . The edges in are the edges of , such that the colours of the two hexes or hex and border it abuts are different. One way to think about what we have done is that we have added an extra row of the Hex board on all sides (these function like the borders) and then drawn edges between any interior vertices which abut different colours. This leaves us with something like:
Now we think about this graph. I claim that all the vertices have degree, either 0, 1, or 2, it’s straightforward to see the graph above exhibits all three cases. I encourage you to check that it’s not possible to have a vertex of higher degree. (If you have trouble, draw a vertex with three hexes around it. What colours must they be?) Any graph that has this property is a disjoint union of isolated points (vertices of degree 0), paths and cycles. (You can prove this by induction on the number of vertices.) In addition the only place a 1-vertex may occur is at the corners. To see this suppose we have some vertex of non-zero degree that is not on the corner. Because it has non-zero degree two of the hexes it abuts must have different colours, but now consider the third hex it abuts. This must be either blue or red, and hence is different to one of the original hexes. Thus there must be an edge between that original hex, and this new hex, and hence this vertex has degree two (note that this argument does not apply to the corners because there is not another hex there.) Now follow these paths, these have to give either a blue path connecting the blue sides or a red path connecting the red sides (otherwise they wouldn’t terminate).
Actually we don’t really need to explicitly invoke the degree of the vertices, we can make a convincing argument without this. (This is the way I presented the proof to the students at the workshop) We note that we can always start a path at any of the corners (there is a blue and a red hex there). Now we proceed by induction. Suppose that we have reached a vertex on our path, then there must be some other edge we may leave by. Because we have arrived by some edge that edge must have abutted a red and a blue hex. In particular we must be in the situation below:
So if the white square is red we continue the path by taking the red line, if it is blue we take the blue line. Now we ask where this path could finish. Two candidates suggest themselves. First we could finish at another corner. However another option could be we could loop around. I asked the students to think about why the second option wouldn’t be possible (Hint: if you meet your path, there must be a first time your path met. What must have happened on the previous step?). Then we continue the proof as before. I sort of prefer this argument, because it’s a bit more obvious exactly why we’re using the degree of vertices, but is reasonably handwavy – what did I mean by path, paths meeting, and previous steps. These are obvious, but the best way to define them precisely seems to just be through the degree of the vertex.
Technically I should really have shown this for a -dimensional Hex Board. I had originally planned to do this but realised while working through this it was going to be messy. I feel a little guilty about this, especially as I complained that economics classes often showed the -dimensional theorem without showing anything higher. However I self-righteously justify my hypocrisy on the following grounds a) the proof shown here really does generalise straightforwardly (if messily) to higher dimensions (details in Gale), b) showing the exact details of this is messy and distracts from what is otherwise a highly attractive and intuitive proof, c) I plan to show a very nice proof through Sperner’s Lemma in a little while which covers this case, and d) the blog’s called Vigorous Handwaving, some hand-waving has to be acceptable.
We’re now ready to show Brouwer’s Fixed Point Theorem (in 2-dimensions).
Brouwer’s Fixed Point Theorem
If is a continuous function from the unit square to itself, then there is some point such that .
The first thing to note is that the Hex board may be shifted by a linear transform to be placed on (in such a way as to associate the corners). The explicit transformation is given in Gale’s paper, the essential idea is noting that the Hex board is isomorphic to a Go board, like the one shown below:
We want to show that contains a nearly fixed point for every – that is, for every there exists such that .
Once we have shown this we can then note that because $I$ is compact must have a convergent subsequence, say . Suppose it converges to .
Let . Then we can add and subtract and apply the Triangle Inequality to get:
A bit of thinking shows that by choosing a sufficiently large each of these three terms may be made smaller than , and hence as was arbitrary this means that
Therefore we only need to show that there exists a nearly fixed point for every .
Because $f$ is continuous on a compact subset of it is uniformly continuous. Therefore there is some such that if then . W.o.l.o.g. suppose that . Now we create a Hex board . Then we create the following four regions:
Intuitively we interpret these sets as the points that are mapped by at least an epsilon right, left, up, or down respectively. Now we use these sections to make a colouring of the Hex board . The basic idea is that if the center of a hexagon, once we’ve mapped it to the square, is in or then we colour it blue, if it is in or then we colour it red. This isn’t quite well-defined though as an and set may not necessarily be separate. Therefore if a hexagon is in both an and a set (it should be clear why a vertex can’t be in two or two sets at the same time) colour it blue (you can use any rule to colour points which are in more than one set, as long as the hexes end up coloured some colour and the proof below will work.
Now, by the Hex Theorem, if all hexes are coloured, then there must be a path. W.o.l.o.g. suppose that it is a blue path. Then there must be a blue hex on the right edge and on the left edge. But because maps into , no centre of a hex on the right edge can be mapped more than epsilon to the right, hence this hex which is coloured blue, must have been mapped to the left (and be in ). Likewise the blue hex on the left edge must be in (it’s centre must have been mapped to the right). Note that we don’t really care about what colour exactly gets assigned to a point in and because IF a path exists, then the hex must have come from the relevant component of or . Therefore the blue path we have supposed exists contains elements from and . However we will now show that and are not connected. Because the hexes have diameter less than , if (i.e. ) and (i.e. ) , then:
Now if and were adjacent hexes we would have that and hence:
But this would contradict the uniform continuity of , as we would have exhibited two points and , such that (i.e. adjacent) but such that . Hence and cannot be connected, and hence there cannot be a blue path. Likewise an identical (mutatis mutandis) argument on and shows that there can be no red path. Therefore by the Hex Theorem, the board cannot be completely filled, there must be at least one non-coloured hex. The centre of this Hex is an almost fixed point for – that is , and we have completed the proof.
So that’s the proof. I really like this particular proof, because it gives you intuition as to why Brouwer’s Fixed Point Theorem holds (the Hex theorem is painstakingly obvious if you’ve spent a bit of time thinking about it, although it’s hard to prove), and also gets a result about continuous functions through an entirely discrete argument, which is sort of cool. I’ll try to write up some other proofs (there’s a particularly nice one using Sperner’s Lemma) and might write something about Kakutani later.