Return to list of publications of J.P. Jones.

J.P. Jones, Some undecidable determined games, International Journal of Game Theory, 11 (1982), 63-70. MR 84b:90107.

Abstract

A classical theorem of von Neumann 1928 and Zermelo 1912 (see also von Neumann and Morgenstern 1953) states that every finite length, two-person, win-lose game with perfect information is determined. That is, there exists a winning strategy for one player or the other. The length of a game is the number of moves. Finite length means a finite number of moves. Win-lose means no draws are possible. Perfect information means no randomness is involved, that each player informs the other of his choices.

Even though such games are determined, there is no algorithm to decide which player, I or II, has the winning strategy. This is illustrated in this paper by the construction of a polynomial Q(a, x1, x2, x3, x4) for which there is no algorithm to decide which player has the winning strategy in the game associated with a:

I picks x1,
I picks x2,
I picks x3,
I picks x4,

I wins iff Q(a, x1, x2, x3, x4) = 0.

Explicit examples of such polynomials Q(a, x1, x2, x3, x4) are constructed in the paper.

Another theorem of the paper is the construction of a polynomial game G of length 19 with the property that neither player I nor II has a computable winning strategy in G.

Return to list of publications of J.P. Jones.