University of California, Los Angeles
Two players, Andy and Dave, move a counter around a three node board. The nodes are arranged in a circle and are labeled +1, +2, and -3. Initially the counter rests on node +1 and Andy starts.
Thereafter, the players alternate moves. There is a one move delay in informing the players of the position of the counter, so that, except for the first move, players make their moves only knowing the node from which the opponent has just moved. A move consists of instructing a referee to move the counter either clockwise or counterclockwise to the next node. One is not allowed to leave the counter where it is. After each move is given to the referee, the referee announces the node that the counter just left, and requires Dave to pay Andy the amount on the label of that node. The problem is for Andy to maximize and for Dave to minimize the limiting average payoff.
This game is a stochastic game with an information lag for both players. No strategy with a bounded memory of past moves can be optimal. Yet using the notion of generalized subgames, we show that there exist optimal strategies of a simple nature based on functions easily approximable by standard methods of computation for stochastic games.