Conclusiones de Teoría de Juegos

El problema general de cómo tomar una decisión en un medio competitivo es bastante común e importante. La contribución fundamental de la teoría de juegos es que propociona un maro conceptual básico para formular y analizar tales problemas en situaciones simples. Sin embargo, existe un gran abismo entre lo que la teoría puede manejar y la complejidad de la mayor parte de las situaciones de competencia que surgen en la práctica. Así, las herramientas conceptuales de la teoría de juegos por lo general desempeñan un papel suplementario cuando se aplican a estas situaciones.

Dada la importancia general del problema, la investigación sobre este tema pretende extender la teoría a casos más complejos, y continúa con algunos éxitos.

Extensiones (III)

Otra extensión más es la que se llama de juegos infinitos, en donde los jugadores cuentan con un número finito de estrategias puras. Estos juegos están diseñados para aquellas situaciones en las que la estrategia seleccionada se puede representar por una variable continua. Por ejemplo, la variable de decisión puede ser el tiempo en el que se lleva a cabo cierta acción, o la proporción de recursos propios que se asignan a cierta actividad, en una situación de competencia. En los últimos años una gran parte de la investigación se ha concentrado en este tipo de juegos.

El análisis que se requiere en estas extensiones del juego finito de dos personas y suma cero, es relativamente complejo y no se profundizará en él.

Extensiones (II)

Otra generalización es el juego de suma no cero, en el que la suma de los pagos a los jugadores no tiene que sumar cero (o ninguna otra constante fija). Este caso refleja el hecho de que muchas situaciones de competencia incluyen aspectos no competitivos que contribuyen a la ventaja o desventaja mutua de los jugadores. Por ejemplo, las estrategias de publicidad para compañias que compiten por un mismo mercado pueden afectar no sólo la división de ese mercado sino también el tamaño total del mercado que comparte sus productos. Como es posible la ganancia mutua, los juegos de suma no cero se subdividen en términos del grado en que se permite que los jugadores cooperen. En un extremo se encuentran el juego no cooperativo, en donde no hay comunicación anterior al juego entre los jugadores. En el otro ejemplo está el juego cooperativo en el que se permiten discusiones y acuerdos antes del juego. Ejemplos que se podrían formular como juegos cooperativos son las situaciones competitivas que engloban leyes de comercio exterior entre países o los acuerdos que se toman entre patrones y obreros. Cuando existen más de dos jugadores, los juegos competitivos permiten también que se formen coaliciones entre algunos o todos los jugadores. 

Extensiones (I)

Aunque en este capítulo se han considerado sólo los juegos de dos personas con suma cero con un número finito de estrategias puras, sería incorrecto concluir que la teoría de juegos se limita a este tipo de juegos. De hecho, se han llevado a cabo investigaciones extensas sobre varios tipos de juegos más complicados, que incluyen los que se resumen en esta sección.

Uno de estos tipos es el juego de n personas, en el que pueden participar más de dos jugadores. Esta generalización es de particular importancia porque en muchos casos de situaciones competitivas, suelen existir más de dos competidores, como en la competencia entre las empresas de negocios, en la diplomacia internacional, etc. Desafortunadamente, la teoría existente para tales juegos es menos satisfactoria que la disponible para juegos de dos personas.

Solución mediante programación lineal (IX)

Como ya se había encontrado la estrategia mixta óptima para el jugador II cuando se resolvió el primer modelo, no era necesario resolver el segundo; en general, siempre se pueden encontrar las estrategias mixtas óptimas para ambos jugadores con sólo elegir uno de los modelos (cualesquiera) y usar el método símplex para obtener tanto la solución óptima como la solución óptima dual.

Los dos modelos suponen que v ≥ 0. Si esta suposición se violara ninguno de los dos modelos tendría soluciones factibles, y el método símplex se detendría rápidamente con el mensaje. Para evitar este riesgo, se pudo haber agregado una constante positiva, como 3 (el valor absoluto del elemento más negativo), a todos los elementos de la tabla 12.6. ESto habría aumentado en 3 todos los coeficientes de x1, x2, y1, y2 y y3 en las restricciones de los dos modelos.

Solución mediante programación lineal (VIII)

A manera de ilustración, considérese de nuevo la variación 3 del problema de la campaña política después de eliminar la estrategia denominada 3 para el jugador I. Como existen algunos elementos negativos en la matriz de pagos reducida, no es evidente si el valor del v es no negativo (ocurre que sí lo es). Por el momento, supóngase que v ≥ 0 y procádase sin hacer ninguno de los ajustes mencionados. Para escribir el modelo de programacion lineal que se mostró antes para el jugador I, obsérvese que pij es el elemento del renglón i y la columna j de la tabla 12.16, para i = 1,2 y j = 1,2,3. Empleando maximizar x(m+1) en lugar de la forma equivalente de minimizar (-xm+1) con m=2 y n =3,el modelo que se obtiene es

Solución mediante programación lineal (VII)

Queda un cabo suelto por atar, a saber, cómo proceder si x(m+1) y (yn+1) no están restringidas en signo en sus formulaciones de programación lineal. Si es evidente que v ≥ 0 para que los valores óptimos de x(m+1) y y(n+1) sean no negativos, entonces no hay peligro si se introducen las restricciones de no negatividad sonbre estas variables con el propósito de aplicar el método símplex. No obstante, si v < 0, entonces debe hacerse un ajuste. Una posibilidad es emplear el enfoque descrito en la sección 4.6 en el que se sustituye una variabe no restringida por la diferencia de dos variables no negativas. Otra posibilidad es invertir a los jugadores I y II para que la matriz de pagos se reescriba como el pago al jugador II original, lo que haría que el valor correspondiente de v fuera positivo. Un tercer procedimiento, y el más usado, es agregar una constante fija grande a todos los elementos de la matriz de pagos para que el nuevo valor de juego sea positivo. (Por ejemplo, bastaría con igualar esta constante al valor absoluto del elemento más negativo) Como la misma constante se agrega a todos los elementos, este ajuste no puede alterar de ninguna manera las estrategias mixtas óptimas, y por lo tanto ahora éstas se pueden obtener en forma normal. El valor incluido del juego se aumentará en la cantidad constante, pero se puede reajustar después de obtener la solución.

Solución mediante programación lineal (VI)

Una consecuencia de esto es que proporciona una prueba muy sencilla del teorema minimax.

Solución mediante programación lineal (V)

Obsérvese el importante hecho de que este problema de programación lineal y el obtenido para el jugador I son duales uno del otro en el sentido descrito en las secciones 6.1 y 6.4 (En particular, este problema está en la forma dada para el problema primal y del jugador I es el correspondiente al problema dual). Este hecho tiene varias implicaciones importantes. Una es que se pueden encontrar las estrategias mixtas óptimas para los dos jugadores al resolver sólo uno de los problemas de programación lineal puesto que la solución óptima dual es un producto complementario automático de los cálculos del método símplex para encontrar la solución óptima primal. Una segunda implicación es que esto trae consigo toda la teoría de dualidad (descrita en el capítulo 6) para fundamentar en ella la interpretación y el análisis de los juegos.

Solución mediante programación lineal (IV)

(La función objetivo y la restricción de igualdad se rescribieron en una forma equivalente porque más tarde se aplicarán así.) Nótese que x(m+1) no está restringida a ser no negativa, mientras que el método símplex sólo se puede aplicar una vez que todas las variables tengan la restricción de no negatividad. Este asunto se puede resolver con facilidad como se verá en seguida.

Ahora considérese  al jugador II. Él puede encontrar su estrategia óptima mixta si se reescribe la matriz de pagos como los pagos a sí mismo en lugar de al jugador I y si después se procede justo como se acaba de describir. Sin embargo, resulta ilustrativo resumir su formulación en términos de la matriz de pagos original. Si se sigue un procedimiento análogo al descrito, el jugador II concluiría que su estrategia mixta óptima está dada por la solución óptima del problema de programación lineal:

Solución mediante programación lineal (III)

En consecuencia, el problema de encontrar una estrategia mixta óptima se ha reducido a encontrar una solución factible para un problema de programación líneal, lo que se puede hacer según lo descrito en el capitulo 4. Las dos dificultades que quedan por resolver son: 1) se desconoce v, y 2) el problema de programación lineal no tiene función objetivo. Por fortuna, ambos obstáculos se pueden salvar al mismo tiempo sustituyendo la constante desconocida v por la variable x(m+1) y después maximizando x(m+1), de manera que automáticamente x(m+1) será igual a v (por definición) en la solución óptima del problema de programación lineal.

Para resumir, el jugador 1 encontrará su estrategia mixta óptima empleando el método simplex para resolver el problema de programación lineal.

y xi ≥ 0 para i = 1,2......,m

Solución mediante programación lineal (II)

Ya que la implicación va en ambas direcciones, se concluye que imponer este conjunto de n desigualdades lineales es equivalente a requerir que la desigualdad original se cumpla para todas las estrategias (y1,y2,.......yn). Pero estas n desigualdades son restricciones válidas en programación lineal, como lo son las restricciones adicionales.

x1 + x2 + ...........+ xm  =1
                              xi    ≥ 0, para i =1,2,......,m


que se necesitan para asegurar que las x1 sean probabilidades. Por esta razón, cualquier solución (x1,x2,........xm) que satisfaga este conjunto completo de restricciones de programación lineal es la estrategia mixta óptima deseada.

Solución mediante programación lineal (I)

Cualquier juego de estrategias mixtas se puede resolver en forma muy sencilla transformándolo en un problema de programación lineal. Como se verá, esta transformación requiere apenas un poco más que la aplicación del teorema minimax y el uso de la definición de valor maximin v y valor minimax v.

Primero, considérese cómo se encuentra la estrategia mixta del jugador 1. Comos e indicó en la sección 12.3

Procedimiento de solución gráfica (VII)

Si en algún otro problema, ocurre que más de dos líneas pasan por el punto maximin, de manera que más de dos líneas y*j pueden ser mayores que cero, habría muchos empates para la estrategia mixta óptima del jugador II. Una de estas estrategias se puede identificar al igualar arbitrariamente todas menos dos de estas yj* a cero y resolver las dos restantes como se acaba de describir.

Si bien este procedimiento gráfico se ejemplificó para un problema en particular, se puede usar esencialmente el mismo razonamiento para resolver cualquier juego con estrategias mixtas que tenga sólo dos estrategias puras no dominadas para uno de los jugadores.

Procedimiento de solución gráfica (VI)

Pero y*2 y y*3 son números y entonces el lado derecho es la ecuación de una línea recta lo cual es un peso ponderado fijo de las dos líneas "de abajo" de la gráfica. Como la ordenada de esta línea debe ser igual a 2/11 en el punto x1 = 7/11 y como nunca debe exceder 2/11, la línea necesariamente es horizontal. (esta conclusión siempre es valida a menos que el valor óptimo de x1 sea cero o 1, en cuyo caso el jugador II también debe usar una sola estrategia pura.) como resultado.

Procedimiento de solución gráfica (V)

En consecuencia, y1* = 0, ya que y1* > 0 violaría la penúltima ecuación; es decir, en la gráfica, el pago esperado en el punto x1= 7/11 estaría por encima del punto maximin.(en general, a cualquier línea que no pasa por el punto maximin se le debe asignar un peso de cero para evitar un aumento en el pago esperado más allá de este punto.)

Entonces,

Procedimiento de solución gráfica (IV)

Para encontrar la estrategia mixta óptima correspondiente para el jugador II, el razonamiento es el siguiente. De acuerdo con la definición de valor minimax v y el teorema minimax, el pago esperado que resulta de esta estrategia (y1, y2, y3) =(y1*, y2*, y3*) tendrá que satisfacer la condición.

Procedimiento de solución gráfica (III)

Así, dado x1, el pago esperado mínimo está dado por el punto correspondiente en la "parte anterior" de la recta. De acuerdo al criterio minimax (o maximin), el jugador I debe elegir el valor de x1 que da el mayor pago esperado mínimo, de modo que

Procedimiento de solución gráfica (II)

Ahora se grafican estas rectas del pago esperado, como se muestra en la figura 12.1. Para cualquier valor dado de x1 y de (y1, y2, y3), el pago esperado será el promedio ponderado apropiado de los puntos correspondientes a estas tres rectas. En particular.

Procedimiento de solución gráfica (I)

Considérese cualquier juego con estrategias mixtas tal que después de eliminar las estrategias dominadas, uno de los jugadores tiene sólo dos estrategias puras. Para ser específico, sea éste el jugador I. Como sus estrategias mixtas son (x1, x2) y x2 = 1-x1, nada más debe obtener el valor óptimo de x1. Es directo y sencillo hacer la gráfica del pago esperado como una función de x1, para ada una de las estrategias de su oponente. ESta gráfica se puede usar para identificar el punto que maximiza el mínimo pago esperado. También es posible identificar en ella la estrategia mixta minimax del oponente.

Para ilustrar este procedimiento, considérese la variación 3 del problema de la campaña política. Nótese que la tercera estrategia pura del jugador I está dominada por la segunda, por lo que la matriz de pagos se puede reducir a la forma dada en la tabla 12.6. Entonces, para cada estrategia pura de que dispone el jugador II, el pago esperado para el jugador I será: