Historia de la Teoría de Juegos
La teoria de juegos como tal fue creada por el matematico hungaro John Von Neumann (1903-1957) y por Oskar Morgenstern (1902-1976) en 1944 gracias a la publicacion de su libro habian anticipado ya ciertas ideas, a las que se sumaron otras posteriores de los matematicos Borel y Zermelo que en uno de sus trabajos (1913) muestra que juegos como el ajedrez son resolubles. Sin embargo, no fue hasta la aparicion del libro de Von Neumann y Morgenstern cuando se comprendio la importancia de la teoria de juegos para estudiar las relaciones humanas.
Von Neumann y Morgenstern investigaron dos planteamientos distintos de la Teoria de Juegos.
El primero de ellos el planteamiento estrategico o no cooperativo. Este planteamiento requiere especificar detalladamente lo que los jugadores pueden y no pueden hacer durante el juego, y despues buscar cada jugador una estrategia optima.
En la segunda parte de su libro, Von Neumann y Morgenstern desarrollaron el planteamiento coalicional o cooperativo, en el que buscaron describir la conducta optima en juegos con muchos jugadores. Puesto que este es un problema mucho mas dificil, sus resultados fueran mucho menos precisos que los alcanzados para el caso de suma cero y dos jugadores.
JOHN VON NEUMANN
OSKAR MORGENSTERN
Teoría de Juegos
La teoría de los juegos es una rama de la matemática con aplicaciones a la economía, sociología, biología y psicología, que analiza las interacciones entre individuos que toman decisiones en una marco de incentivos formalizados (juegos). En un juego, varios agentes buscan maximizar su utilidad eligiendo determinados cursos de acción. La utilidad final obtenida por cada individuo depende de los cursos de acción escogidos por el resto de los individuos.
La teoría de juegos es una herramienta que ayuda a analizar problemas de optimización interactiva. La teoría de juegos tiene muchas aplicaciones en las ciencias sociales. La mayoría de las situaciones estudiadas por la teoría de juegos implican conflictos de intereses, estrategias y trampas. De particular interés son las situaciones en las que se puede obtener un resultado mejor cuando los agentes cooperan entre sí, que cuando los agentes intentan maximizar sólo su utilidad.
La teoría de juegos fue ideada en primer lugar por John von Neumann. Luego, John Nash, A.W. Tucker y otros hicieron grandes contribuciones a la teoría de juegos.
Juegos
Se denomina juego a la situación interactiva especificada por el conjunto de participantes, los posibles cursos de acción que puede seguir cada participante, y el conjunto de utilidades.
Estrategia
Cuando un jugador tiene en cuenta las reacciones de otros jugadores para realizar su elección, se dice que el jugador tiene una estrategia. Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega el juego. Se explicita antes de que comience el juego, y prescribe cada decisión que los agentes deben tomar durante el transcurso del juego, dada la información disponible para el agente. La estrategia puede incluir movimientos aleatorios.
Resultados de los juegos
El resultado de un juego es una cierta asignación de utilidades finales. Se denomina resultado de equilibrio si ningún jugador puede mejorar su utilidad unilateralmente dado que los otros jugadores se mantienen en sus estrategias. Un equilibrio estratégico es aquel que se obtiene cuando, dado que cada jugador se mantiene en su estrategia, ningún jugador puede mejorar su utilidad cambiando de estrategia. Alternativamente, un perfil de estrategias conforma un equilibrio si las estrategias conforman la mejor respuesta a las otras.
Forma normal versus forma extensiva de los juegos
En juegos de forma normal, los jugadores mueven simultáneamente. Si el conjunto de estrategias es discreto y finito, el juego puede ser representado por una matriz NxM (ver abajo). Un juego en forma extensiva especifica el orden completo de movimientos a través de la dirección del juego, generalmente en un árbol de juego.
Juegos NxM
Una forma de juegos de dos jugadores, en la cual un jugador tiene N acciones posibles y el otro tiene M acciones posibles. En un juego así, los pares de utilidades o pagos pueden ser representados en una matriz y el juego es fácilmente analizable. Los juegos NxM dan una idea de cómo puede verse la estructura de un juego mas complejo.
Matriz de resultados de un juego
La matriz de resultados de un juego representa el resultado del juego en una matriz. Supongamos que dos personas, A y B, están jugando un sencillo juego. El juego consiste en lo siguiente: la persona A tiene la posibilidad de elegir “arriba” o “abajo”, mientras que B puede elegir “izquierda” o “derecha”. Los resultados del juego se representan en la matriz de resultados:
| Izquierda | Derecha | |
| Arriba | (50 , 100) | (0 , 50) |
| Abajo | (100 , 50) | (50 , 0) |
Estrategia dominante
Una estrategia dominante es aquella elección que realiza el jugador independientemente de lo que haga el otro. En el juego representado en la matriz de arriba, la estrategia dominante para A es elegir “abajo”, mientras que la estrategia dominante para B es elegir “izquierda”. Estas estrategias dominantes dan como resultado el equilibrio de estrategias dominantes del juego. Si cada jugador tiene una estrategia dominante se puede predecir el resultado del juego.
A continuación veremos los tipos de juegos que podemos encontrar y algunos conceptos relevantes que se tienen en cuenta cuando se hace un análisis de un juego.
Estrategia mixta, Valor esperado
suponga el jugador de renglón usa la estrategia mixta
Entonces el valor esperado del juego es
A continuación veremos los tipos de juegos que podemos encontrar y algunos conceptos relevantes que se tienen en cuenta cuando se hace un análisis de un juego.
Juegos bipersonales de suma cero
En un juego bipersonal de suma cero, cada uno de dos jugadores tiene que escoger entre unas acciones dictadas a cada turno, y la pérdida de cada jugador es igual al beneficio del su contrincante.
La matriz de pagos de un juego bipersonal de suma cero tiene reglones etiquetados por las acciones del "jugador renglón" y columnas etiquetadas por las acciones del su contrincante, el "jugador columna." La entrada ij de la matriz es el pago que gana el jugador renglón en caso de que el jugador renglón usa acción i y el jugador columna usa acción j.
Ejemplo
Piedra, papel, tijera
Piedra vence a las tijeras rompiéndolas, las tijeras vencen al papel cortándolo, y el papel vence a la piedra envolviéndola.
Cada entrada +1 indica una ganancia para el jugador renglón, -1 indica una pérdida, y 0 indica un empate.
Piedra vence a las tijeras rompiéndolas, las tijeras vencen al papel cortándolo, y el papel vence a la piedra envolviéndola.
Cada entrada +1 indica una ganancia para el jugador renglón, -1 indica una pérdida, y 0 indica un empate.
Estrategia mixta, Valor esperado
Un jugador usa una estrategia pura si usa la misma acción a cada turno del juego. El jugador usa una estrategia mixta si a cada turno escoge al azar un acción para que cada acción se está usado una fracción determinada del tiempo.
Representamos una estrategia mixta (o pura) del jugador reglón por una matriz con un solo renglón (vector probabilidad):
R = [a b c . . . ]
con lo mismo número de entradas que renglones, y en cual cada entrada representa la fracción de tiempo que está usada la correspondiente acción (o la probabilidad de usar aquel acción) y donde a + b + . . . = 1.
Una estrategia mixta para el jugador renglón se represente por un vector probabilidad similar, pero en forma de columna C. Para ambos jugadores, estrategias puras son representadas por vectores probabilidad con un solo 1 y el resto de las entradas 0.
El valor esperado del juego con matriz de pagos Pque resulta por las estrategias mixtas R y C es dado por
e = RPC
El valor esperado del juego es el pago promedio por turno si cada jugador usa su estrategia mixta especificado por R y C después de un gran número de turnos.
Ejemplo
Aquí es una variante de "piedra, papel, tijera" en la que "papel/papel" y "piedra/piedra" ya no está un empate.
suponga el jugador de renglón usa la estrategia mixta
R = [0.75 0 0.25]
(juega papel 75% del tiempo, tijeras 0% del tiempo y piedra 25% del tiempo) y el jugador columna juega tijeras y piedra 50% del tiempo cada uno;
Entonces el valor esperado del juego es
e | = RPC | |
Criterio minimax, Principios fundamentales de la teoría de juegos
Un jugador quien usa el criterio minimax escoge una estrategia que, entre todas las estrategias posibles, minimiza el daño de la mejor contra-estrategia del otro jugador. Es decir, una estrategia óptima según el criterio minimax es una que minimiza el daño máximo que puede hacer el contrincante.
Un jugador quien usa el criterio minimax escoge una estrategia que, entre todas las estrategias posibles, minimiza el daño de la mejor contra-estrategia del otro jugador. Es decir, una estrategia óptima según el criterio minimax es una que minimiza el daño máximo que puede hacer el contrincante.
Encontrar la estrategia se llama solucionar el juego. La tercera parte del tutorial para esta tema muestra un método gráficamente para solucionar juegos 2×2. Para juegos general, se puede usar el método simplex (vea siguiente tema). Sin embargo, se puede frecuentemente simplificar un juego y a veces solucionarlo por "reducir por predominio" y/o comprobar si es "estrictamente determinado" (vea más abajo).
Principios fundamentales de la teoría de juegos Cuando analizamos cualquier juego, hacemos los siguientes supuestos acerca de los dos jugadores:
- Cada jugador hace la acción mejor posible.
- Cada jugador sabe que su contrincante está también haciendo la acción mejor posible.
Ejemplo
Considere el siguiente juego:
Si el jugador renglón sigue Principio 1, nunca debería jugar Acción 1 pues Acción 2 da mejor pagos sin tener en cuenta cual acción escoja el jugador columna. (Los pagos en renglón 2 son por lo menos tan altos que los pagos correspondientes en renglón 1.)
Además, siguiendo Principio 2, el jugador renglón espera que el jugador columna nunca jugaría Acción A, pues Acción B da mejor pagos desde el punto de vista del jugador columna. (Los pagos en columna B son por lo menos tan bajos que los pagos correspondientes en columna A.)
Reducir por predominio
Una acción domina a otra si todos sus pagos son por lo menos tan provechoso al jugador que los pagos correspondientes de la otra. En términos de la matriz de pagos, podemos decirlo como sigue:
- Renglón r en la matriz de pagos domina a renglón s si cada pago en renglón r ≥ el pago correspondiente en renglón s.
- Columna r en la matriz de pagos domina a columna s si cada pago en columna r ≤ el pago correspondiente en columna s.
Observe que si dos renglones o columnas son iguales, cada uno domina al otro. Un renglón o columna domina estrictamente a un otro si el uno domina al otro y son desiguales.
Siguiendo el primero principios de la teoría de juegos, la acción que corresponde a un renglón o columna estrictamente dominado nunca será jugado, y ambos jugadores son conscientes de esto por el segundo principio. Entonces cada jugador quien sigue los principios de la teoría de juegos eliminará repetidamente renglones y columnas dominadas como podría ser el caso. (En el caso que son iguales dos renglones o columnas, no hay razón para elegir uno sobre el otro, entonces cualquiera de los dos puede ser eliminado.) Este proceso se llama reducción por predominio.
Ejemplo
Considere otra vez el siguiente juego.
Pues las entradas de Renglón 2 son ≥ las entradas correspondientes en Renglón 1, entonces Renglón 2 domina a Renglón 1.
Pues las entradas de Columna B son ≤ las entradas correspondientes en Columna A, Columna B domina a Columna A.
Reducir el juego más arriba por predominio
Pues Renglón 2 domina a Renglón 1, eliminamos Renglón 1 para obtener
Pues Columna B ahora domina a ambas Columnas A y C, eliminamos las dos Columnas A y C para obtener
Pues el primero renglón domina ahora al último renglón, eliminamos el último renglón, y estamos reducidos a la siguiente matriz 1×1
En este caso, hemos solucionado el juego por reducción por predominio: El jugador renglón debe siempre jugar 2 y el jugador de columna debe siempre jugar B. Pues el pago correspondiente es 0, decimos que el juego esjusto (ninguno jugador tiene ventaja sobre el otro).
Observe que tuvimos suerte aquí: No todos los juegos pueden ser reducido a un juego 1×1 por predominio.
Punto de silla, juego estrictamente determinado
Un punto de silla es un pago que es simultáneamente un mínimo de su renglón y un máximo de su columna. Para encontrar puntos de silla, Encierre en círculo los mínimos de todos los renglones y meta en caja los máximas de todas las columnas. Los puntos de silla son aquellas entradas que son simultáneamente en círculo y en caja.
Un juego es estrictamente determinado si tiene por lo menos uno punto de silla. Las siguientes declaraciones se aplican a los juegos estrictamente determinados:
- Todos los puntos de silla en un juego tienen los mismos valores de pago.
- Elegir el renglón y la columna que pasan por cualquier punto de silla de estrategias minimax para ambos jugadores. Es decir, el juego es solucionado por el uso de estas estrategias puras.
El valor de un juego estrictamente determinado es el valor del punto de silla. Un juego justo tiene un valor igual a cero, si no, es injusto o parcial.
Ejemplo
En el juego más arriba, hay dos puntos de silla, mostrados en color.
Pues son cero los puntos de silla, es un juego justo.
Se puede usar la herramienta teoría de juegos para comprobar cualquier juego (de hasta 5×5) para puntos de silla, solo es cuestion de experimentarlo
