Details

A terminal game with players is defined by:

• a partition of the nonempty set into nonempty sets ;

• a function (i.e. for every , there is a subset of ) such that ;

• a function (i.e. for every element , there is a vector ); is called the payoff function and each player tries to maximize it.

An arbitrary oriented graph with at least one terminal vertex can represent a Nim-like game that is a particular case of a terminal game on graphs with , , and equal to the set of terminal vertices. It can be verified that can be partitioned into subsets and (i.e. and ) with the properties:

• ,

• .

The vertices in the set are called the "gain" vertices, and those in are called the "loss" vertices, because the player who chooses a vertex from offers only losing vertices to the opponent (from ), and the player who chooses a vertex from offers only winning vertices (from ). Obviously is the graph's kernel. Define to be the set of terminal vertices.

The algorithm is:

1. Set .

2. For every vertex from , we know if belongs to or to

Let , and

Then, and .

3. Let .

only when .

Reference

[1] B. Kummer, Spiele auf Graphen, Berlin 1979.