Game on a graph

A generalization of a positional game to the case where the graph of position is not tree-like but arbitrary. A special case of a game on a graph is the game of Nim, which is a two-person zero-sum game with complete information, in which for every final position it is known whether the player who moves last wins or loses. In its simplest form, the game of Nim consists of the following: there are some piles of matchsticks, the players in turn remove at least one matchstick, and at each stage the removed matchsticks must be taken from one and the same pile. The player who removes the last matchstick wins. The solution of the game of Nim consists of a description, for each player, of the set of winning positions, that is, positions from which the player can win against any strategy that his opponent adopts. The set of winning positions is just the set of zeros of the Sprague–Grundy function: the function $g$ that associates to every vertex $k$ of a graph $\Gamma$ the number $$ g(k) = \min\{ n : n \ne g(i)\,,\ i \in \Gamma(k) \} \ . $$

It has the properties of internal and external stability, and in this regard it is similar to the concept of a von Neumann–Morgenstern solution in cooperative games.

References

[1]	C. Berge, "Théorie génerale des jeux à $n$ personnes" , Gauthier-Villars (1957)
[2]	B. Kummer, "Spiele auf Graphen" , Birkhäuser (1980)

Comments

Currently games on cyclic graphs and games on partizan graphs (i.e. when not all moves are legal for both players) are of interest.

References

[a1]	C. Berge, "Graphs and hypergraphs" , North-Holland (1977) (Translated from French)
[a2]	J.H. Conway, "On numbers and games" , Acad. Press (1976)
[a3]	E.R. Berlekamp, J.H. Conway, R.K. Guy, "Winning ways for your mathematical plays" , 1–2 , Acad. Press (1982)