Juegos en forma extensiva

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Un juego en forma extensiva es una especificación de un juego en la teoría de juegos, que permite (como su nombre sugiere) la representación explícita de una serie de aspectos importantes, como la secuencia de movimientos posibles de los jugadores, sus elecciones en cada punto de decisión, lo imperfecto de la información que cada jugador tiene en algunos movimientos del otro jugador cuando él toma una decisión, y sus ganancias para todos los resultados posibles del juego. Juegos en forma extensiva también permitir la representación de la información incompleta en forma de casualidades codificados como " se mueve por naturaleza".

Juegos finitos en forma extensiva[editar]

Algunos autores, especialmente en los textos introductorios, inicialmente al definir el juego en forma extensiva como un Árbol de juego con ganancias (sin información imperfecta o incompleta), y van añadiendo otros elementos en los capítulos posteriores como refinamientos. Mientras que el resto de este artículo sigue este enfoque con la motivación ejemplos, se presentan por adelantado lo finito en forma extensiva juegos como (en última instancia) construidos aquí. Esta definición general fue presentado por Harold W. Kuhn en 1953, que extendió una definición anterior de von Neumann de 1928. Después de la presentación de Sergiu Hart (1992)[1] , un juego de N-jugadores en forma extensiva consiste en lo siguiente:

  • Un conjunto finito de n jugadores (racionales)
  • Un árbol con raíz, llamado el árbol de juego
  • Cada terminal (hoja) nodo del árbol de juego tiene una n-tupla de pagos, es decir, hay una ganancia para cada jugador al final de cada juego posible
  • Una partición de los nodos no terminales del árbol de juego en n +1 subconjuntos, uno para cada jugador (racional), y con un subconjunto especial para un jugador ficticio llamado Chance (o la naturaleza). Cada jugador subconjunto de nodos que se conoce como los "nodos" del jugador. (Un juego de información completa por lo tanto tiene un conjunto vacío de nodos de azar.)
  • Cada nodo aleatorio de un jugador tiene una distribución de probabilidad sobre los resultados salientes.

Un juego es por lo tanto un camino a través del árbol desde la raíz hasta un nodo terminal. En cualquier nodo no terminal dado que pertenece a Chance, una rama que se escoge de acuerdo con la distribución de probabilidad. En el nodo cualquier jugador racional, el jugador debe elegir una de las clases de equivalencia para los bordes, lo que determina precisamente un borde saliente excepto (en general) el jugador no sabe que se está siguiendo. (Un observador externo conocer las opciones de los demás jugadores hasta ese punto, y la realización de movimientos de la naturaleza, se puede determinar el límite exacto.) Una estrategia pura para un jugador consiste, pues, de una selección , eligiendo precisamente una clase de bordes salientes para cada información establecido (de él). En un juego de información perfecta, los conjuntos de información son únicos . Es menos evidente cómo los pagos deben ser interpretados en juegos con nodos de azar. Se supone que cada jugador tiene una von Neumann-Morgenstern función de utilidad definida para cada resultado del juego; este supuesto implica que cada jugador racional evaluará un a priori resultado aleatorio por su esperada utilidad.

La presentación anterior, mientras que la definición precisa de la estructura matemática sobre la que se juega el juego, elude sin embargo, la discusión más técnica de la formalización de declaraciones acerca de cómo se juega el juego como "un jugador no puede distinguir entre los nodos del conjunto de información misma hora de tomar una decisión". Éstos se pueden hacer preciso utilizando la lógica modal epistémico , ver Shoham y Leyton-Brown (2009 , cap 13.) para más detalles.

Información perfecta y completa[editar]

Una completa representación en forma extensiva especifica:

  1. Los jugadores de un juego
  2. Para todos los jugadores de todas las oportunidades que tienen que moverse
  3. Lo que cada jugador puede hacer en cada uno de sus movimientos
  4. Lo que cada jugador sabe con cada movimiento
  5. Los pagos recibidos por cada jugador para cada combinación posible de movimientos

El juego de la derecha tiene dos jugadores: 1 y 2. Los números de cada nodo no terminal son para indicar a qué jugador le pertenece la decisión de jugar. Los números de cada nodo terminal representan los pagos a los jugadores (por ejemplo, 2,1 representa un pago de 2 al 1 jugador y un pago de 1 al jugador 2). Las etiquetas de cada borde de la gráfica son el nombre de la acción que representa ese borde.

El nodo inicial pertenece al jugador 1, lo que indica que el jugador 1 mueve primero. El juego según el árbol es el siguiente: El jugador 1 elige entre U y D; el jugador 2 observa elección del jugador 1 y luego elige entre U 'y D'. Los beneficios son los especificados en el árbol. Hay cuatro resultados representados por los cuatro nodos terminales del árbol: (U, U '), (U, D'), (D, U ') y (D, D'). Los pagos asociados con cada resultado, respectivamente, son como sigue (0,0), (2,1), (1,2) y (3,1).

Si el jugador 1 juega D, el jugador 2 jugará U' para maximizar su rentabilidad y por lo tanto el jugador 1 sólo recibirá 1. Sin embargo, si el jugador 1 juega U, el jugador 2 maximiza su recompensa por jugar D 'y el jugador 1 recibe 2. El jugador 1 prefiere 2 a 1 y así jugará U y el jugador 2 jugará D'. Este es un equilibrio perfecto en subjuegos .

Un juego representado en forma extensiva

Información imperfecta[editar]

Una ventaja de representar el juego de esta manera es que está claro lo que el orden del juego. El árbol muestra claramente que el jugador 1 mueve primero y el jugador 2 observa este movimiento. Sin embargo, en algunos juegos del juego no ocurre así. Un jugador no siempre observar la elección de otro (por ejemplo, movimientos pueden ser simultáneos o un movimiento puede estar oculto). Un conjunto de información es un conjunto de nodos de decisión de tal manera que:

  1. Cada nodo del conjunto pertenece a uno de los jugadores.
  2. Cuando el juego llegue al conjunto de información, el jugador con el movimiento no puede diferenciar entre los nodos del conjunto de información, es decir, si el conjunto de datos contiene más de un nodo, el jugador al que pertenece ese grupo no sabe qué nodo en el conjunto se ha alcanzado .

En forma extensiva, un conjunto de información se indica mediante una línea de puntos que conecta todos los nodos que en conjunto o, a veces por un bucle dibujado alrededor de todos los nodos en ese conjunto.

Si un juego tiene un conjunto de información con más de un miembro de ese partido se dice que tiene información imperfecta . Un juego con información perfecta es tal que en cualquier momento de la partida, cada jugador sabe exactamente lo que ha ocurrido antes en el juego, es decir, cada conjunto de información es un singleton set. Cualquier juego sin información perfecta tiene información imperfecta.

El juego de la izquierda es el mismo que el juego anterior, excepto que el jugador 2 no sabe lo que el jugador 1 hace cuando viene a jugar. El primer juego descrito tiene información perfecta, el juego de la izquierda no lo hace. Si ambos jugadores son racionales y ambos saben que ambos jugadores son racionales y todo lo que es conocido por cualquier jugador es conocido por ser conocido por todos los jugadores (es decir, el jugador 1 sabe que el jugador 2 sabe que el jugador 1 es racional y el jugador 2 sabe, etc ad infinitum), jugar en el primer juego será el siguiente: el jugador 1 sabe que si juega U, el jugador 2 se juega D '(porque para el jugador 2 es preferible a una ganancia de 0 un pago de 1) y lo que el jugador 1 recibirá 2. Sin embargo, si el jugador 1 juega D, el jugador 2 jugará U '(porque al jugador 2 una rentabilidad del 2 es mejor que un pago de 1), y el jugador 1 recibe 1. Por lo tanto, en el primer juego, el equilibrio será (U, D '), ya que el jugador 1 prefiere recibir 2 a 1 y así se reproducirá U y lo que el jugador 2 jugará D'.

En el segundo juego no está tan claro: el jugador 2 no puede observar movimiento del jugador 1. Jugador 1 quisiera engañar a jugador 2 en el pensamiento de que ha jugado U cuando en realidad ha jugado D para que el jugador 2 jugará D 'y el jugador 1 recibe 3. De hecho, en el segundo juego hay un equilibrio bayesiano perfecto donde el jugador 1 juega D y el jugador 2 juega U 'y el jugador 2 tiene la creencia de que el jugador 1 sin duda jugar D. En este equilibrio, cada estrategia es racional dadas las creencias y todas las creencias son consistentes con las estrategias jugadas. Observe cómo la imperfección de la información cambia el resultado del juego.

Referencias[editar]

  1. Hart, Sergiu (1992). "Games in extensive and strategic forms". In Aumann, Robert; Hart, Sergiu. Handbook of Game Theory with Economic Applications 1. Elsevier. ISBN 978-0-444-88098-7.

Bibliografía Ampliada[editar]

  • Horst Herrlich (2006). Axiom of choice. Springer. ISBN 978-3-540-30989-5. , 6.1, "Disasters in Game Theory" and 7.2 "Measurability (The Axiom of Determinateness)", discusses problems in extending the finite-case definition to infinite number of options (or moves)
  • Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Mathematische Annalen 100: 295–320. doi:10.1007/BF01448847.
  • Harold William Kuhn (2003). Lectures on the theory of games. Princeton University Press. ISBN 978-0-691-02772-2.  contains Kuhn's lectures at Princeton from 1952 (officially unpublished previously, but in circulation as photocopies)