The axiomatic set-up of game theory has some similarity with the setup in statistical mechanics. Due to the shear size of the configuration space one refers to probabilistic set-ups. Getting from the micro-canonical description to the macro-canonical framework is necessary if one can not oversee the full configuration space. A similar taxonomy is used in the form of micro economics and macro economics. In the later, the individual players do not matter very much. One looks at expectations.
This semester, we looked at a project in graph theory that intersects with game theory and combinatorial group theory. The most iconic quantity there is a measure of complexity. It is called the god number. For a finitely presented group, the god number is the diameter of the Cayley graph, for a finite directed or undirected graph it is the maximal distance between any two points where one is reachable from the other. These are maximin problems and are problems for puzzles or 1-player games.
For two player games, we look at a bipartie graph (V + W, E), the god number requires to solve a minimax problem: given an initial condition v of the game and a set A called win solutions, we can for every subgraph containing H look at the length of the maximal game event in the graph. The god number is the minimum of that over all strategies = subgraphs containing v. A game event is a finite simple path in the graph starting at v. The intuition is very clear to anybody who has played games like chess: a strategy of the first player V limits its own moves in the game graph. Assume the game is winnable for V, the opponent W tries to maximize the game length in order to survive as long as possible.
This graph geometric frame work produces a handy, small and intuitive axiom system which in principle covers every two player game where players play sequentially and where we have a zero sum game which is encoded that the solution space is partitioned into a part in W and a part in V. The axiom system can be generalized readily to n-player games. What makes 2-player games special is that we do not have to worry about collusions. Mathematically this is reflected by Zermelo’s theorem in game theory. In this game theoretical frame work, this theorem directly follows from the definition. In some sense ,this result is now of the same “triviality class” like Bayes theorem in probability, which is also not really a theorem because it just is a reformulation of the definition of conditional expectation. The Zermelo trichotomy is a direct logical consequence of the set-up. There are four logical possibilities Win-Win, Win-Lose,Lose-Win and Lose-Lose. The assumption imply that Win-Win is not possible. Lose-Lose is defined to be “draw”.
This Math 91r project was both CS (2 students) and Math (3 students) based and actually computing god numbers was an important part of the project. We used Mathematica, GAP, Python and C (some C programs were obtained machine generated from original code). Here is a write-up of some collaboratively written notes this semester (56 pages PDF). We plan to proof read this a bit in the next couple of days. To the right, we see the game graph of the tower of hanoi with 4 pegs and 4 disks (a Reeves puzzle). The graph diameter is now smaller and not known for large n. To the left the usual Hanoi tower game graph. The tower of Hanoi appears in any programming course, usually in a chapter about recursion, which then features first factorial, then Fibonacci numbers then tower of hanoi then fractals. It is almost Kitsch. What I would probably do when teaching (because the standard hanoi tower is too generic) is to look at the tower of hanoi with 4 pegs which is a much more interesting transport problem as one can now work more effectively using two “storage pegs”. In the case of 4 disks on 4 pegs the graph distance is 9, whle for 4 disks on a 3 peg Hanoi problem, we have radius 15 already. The game graph obviously has a S4 symmetry which renders the game graph win a tetrahedral symmetry when plotted in three dimensional space.
