¿Hay algún juego que no pueda ser representado por un árbol de juegos?

Question

¿Existe un juego finito que no pueda ser representado por un forma extensa o un árbol de juegos?

Sé que muchos juegos son demasiado largos y complejos para ser representados por un árbol de un tamaño razonable, pero eso no es lo que busco porque es en parte una limitación computacional.

En cambio, me pregunto si hay algo sencillo por ahí que simplemente no encaja en un formulario extenso. Todos los libros que he leído dicen algo así como

Varios juegos pueden ser representados por árboles

Pero no he visto la afirmación "todos los juegos" en ningún sitio. ¿Hay alguna excepción conocida?

Answer 1

Bien, para ello hay que definir qué es un "juego finito". La manera habitual de hacerlo es definirlo como un juego de forma extensiva, lo que hace que toda la cuestión sea circular. Pero hay diferentes maneras de modelar los juegos de forma extensiva en diferentes niveles de generalidad. Por ejemplo, la primera definición debida a John von Neumann y Oskar Morgenstern establecía una serie de fuertes restricciones de tiempo que parecen algo arcaicas desde la perspectiva actual. La definición posterior de Harold Kuhn generalizó significativamente la clase de posibles juegos de forma extensiva. Una restricción implícita en la forma en que Kuhn definió los juegos de forma extensiva fue que no se permite que ningún jugador se mueva dos veces por el mismo conjunto de información, una suposición debilitada en la tesis doctoral de John Isbell. Así que hay varias nociones de juegos de forma extensiva en varios niveles de generalidad, incluyendo versiones que permiten juegos infinitos.

Answer 2

Una idea interesante...

Supongo que los juegos recursivos, en los que un resultado depende de jugar el mismo juego, en un recuento dinámico de veces, no pueden representarse en un formulario o una matriz

Un caso más común es el de los juegos simultáneos multijugador, cuando tiene 2 jugadores requiere una matriz 2d, cada nuevo jugador añadirá una dimensión a la matriz, más de 3 no podrá tener una representación gráfica, sino sólo un esquema tipo base de datos