Juegos en forma extensiva
Un juego en forma extensiva es una especificación de un juego en la teoría de juegos, que permite la representación explícita de una serie de aspectos importantes, como el orden de los movimientos posibles de los jugadores, sus decisiones en cada punto de decisión, la información (tal vez imperfecta) que cada jugador tiene del contrario cuando toma una decisión, y sus ganancias en todos los resultados posibles del juego. Los juegos en forma extensiva también permiten representar información incompleta de sucesos del azar modelados como "movimientos de la naturaleza".
Juegos finitos en forma extensiva
[editar]Algunos autores, especialmente en los textos introductorios, definen el juego inicialmente 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 ejemplar, se presenta lo finito de los juegos en forma extensiva por adelantado, como (en última instancia) son 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 conoce 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á a priori un resultado de forma aleatoria 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". Estos 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 específica:
- Los jugadores de un juego
- Para todos los jugadores de todas las oportunidades que tienen que moverse
- Lo que cada jugador puede hacer en cada uno de sus movimientos
- Lo que cada jugador sabe con cada movimiento
- 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 la 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 solo 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.
Información imperfecta
[editar]Una ventaja de representar el juego de esta manera es que el orden del juego está claro. 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 observa la elección del 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:
- Cada nodo del conjunto pertenece a uno de los jugadores.
- 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 el primer juego sería como sigue: el jugador 1 sabe que si juega U, el jugador 2 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'.
El segundo juego no es tan claro: el jugador 2 no puede observar el movimiento del jugador 1. Jugador 1 quisiera engañar al 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ía 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]- ↑ 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.
- Hart, Sergiu; Hart, Sergiu (1992). «Games in extensive and strategic forms». En Aumann, Robert, ed. Handbook of Game Theory with Economic Applications 1. Elsevier. ISBN 978-0-444-88098-7.
- Binmore, Kenneth (2007). Playing for real: a text on game theory. Oxford University Press US. ISBN 978-0-19-530057-4.
- Dresher M. (1961). The mathematics of games of strategy: theory and applications (Ch4: Games in extensive form, pp74–78). Rand Corp. ISBN 0-486-64216-X
- Fudenberg D and Tirole J. (1991) Game theory (Ch3 Extensive form games, pp67–106). Mit press. ISBN 0-262-06141-4
- Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1.. An 88-page mathematical introduction; see Chapters 4 and 5. Free online Archivado el 15 de agosto de 2000 en Wayback Machine. at many universities.
- Luce R.D. and Raiffa H. (1957). Games and decisions: introduction and critical survey. (Ch3: Extensive and Normal Forms, pp39–55). Wiley New York. ISBN 0-486-65943-7
- Osborne MJ and Rubinstein A. 1994. A course in game theory (Ch6 Extensive game with perfect information, pp. 89–115). MIT press. ISBN 0-262-65040-1
- Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7.. A comprehensive reference from a computational perspective; see Chapter 5. Downloadable free online.
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)