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.
**

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, x _{1},
x_{2}, x_{3}, x_{4})* for which there is no
algorithm to decide which player has the winning strategy in the game
associated with

*
*

Explicit examples of such polynomials *Q(a, x _{1},
x_{2}, x_{3}, x_{4})* 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.