Possible Generalizations of Zermelo-Kuhn-Gale Theorem

Endre Boros and Vladimir Gurvich

In 1912, at the 5^th Congress of Mathematicians in Cambridge, Zermelo gave his seminal talk:

On Applications of Set Theory to Game of Chess in which he proved that Chess has a saddle point in PURE POSITIONAL (stationary) strategies. In the very beginning, he mentioned that, in fact, his results hold not only for Chess but for every two-person zero-sum positional game with perfect information.

In 1951, Nash introduced a concept of an equilibrium (so-called Nash equilibrium) which is a generalization of the saddle-points for the zero-sum two-person games to the general $n$-person case.

Soon, in 1950s, Kuhn and Gale extended the Zermelo Theorem and proved Nash-solvability in pure stationary strategies for the ACYCLIC positional $n$-PERSON games with perfect information. Their proofs are constructive, the corresponding algorithm is known as the so-called backward induction.

Yet, already the game of Chess is NOT acyclic. A position $v$ can be repeated. Moreover, since we restrict ourselves to only stationary strategies, $v$ will be repeated infinitely whenever it appears twice. In this case the game is a draw, by the definition. Thus, cycles are allowed but they all are equivalent, that is, they all form one outcome of the game. Somewhat surprisingly, under these very simple and natural assumptions, the Nash-solvability remains a conjecture; perhaps, the most challenging in the whole positional game theory.

 

It was proven for the $2$-person case and, very recently, for the case of at most three terminal (and one cyclic) outcomes under the following extra assumption:

(*) for each player, any cycle is worse than any terminal outcome.

In this talk we explain the above two results, as well as some related conjectures. Since they all are quite elementary (although difficult) we hope that RUTCOR students could prove or disprove some of them, or, at least, get some partial results.