Graphs Groups and Games

Graphs Groups and Games

The work of John von Neumann and Oskar Morgensten from 1944 is usually considered the start of mathematical game theory. It builds on earlier work, especially of von Neumann in particular the elegant mini-max theorem of Neumann: let P^m be the space of probability vectors in $mathbb R^m$ and let f(x,y) be a bilinear form f(x,y) = x \cdot A y, where A is a m \times n matrix. Then \max_{x \in P^m} \min_{y \in P^n} f(x,y) = \min_{y \in P^n} \max_{x \in P^m}  f(x,y). John Nash used the Brouwer fixed point theorem to prove it by defining a continuous map on the compact contractible set $mathbb P^n \times P^m$. Game theory has become rich in the hands of von Neumann but there is a prize to be payed. The axiom systems one can find in the book of 1944 is complicated. It is seen to the right.

It turns out that if one wants to study single player puzzles like the 15 puzzle or the Rubik cube or two player games that are commonly known like checkers or chess, one can go much earlier than 1944. It was Zermelo who first formulated a result that is now known as Zermelo’s theorem. It was done in 1913. (see picture to the left).

The theorem needed some clarifications to be solid but unlike von Neumann, the axiomatic setting is a bit vague.

In a project of Math 91r this semester we looked at a more geometric and more elementary approach.

For Combinatorial games, a graph theoretical axiomatic foundation makes sense as everything is finite. Both in one person as well as two person games, we can look at finite simple directed graphs in such a way that for two player games the Theorem of Zermelo is almost a tautology. We were mostly interested in god numbers for such games. In the case of single player games this is a maximin problem, in the case of a two player game it is a minimax problem. But these minimax and maximin problems are finite and have little to do with the theorem of von Neumann mentioned above. The maximin variational problem is a fancy way to call the diameter of the graph: it is the maximum over all minimal distances between two points in the graph. In the two player game, it is the minimum over all maxima of strategies. A strategy is a subgraph. The definition is done in such a way that a “chess in 3 moves” means “god number=3”. In our project Math 91r, we computed various god numbers.