ARTICULOS TEORIA DE JUEGOS BASICOS GLOSARIO CONTACTO


Análisis MINIMAX
de Juegos Suma Cero


En el caso de juegos suma cero modelados por matrices debemos buscar la solución punto de silla de montar mediante análisis minimax no estocástico. Si ésta no existe, entonces se requiere usar la técnica minimax estocástica.

Punto de Silla de Montar

Un punto de silla de montar es uno que es máximo en un sentido y mínimo en el otro. Por ejemplo, en una fila de una matriz de pagos puede encontrarse (desde la perspectiva del jugador A) un punto local de mínimo rendimiento (un valle) siempre que la celda candidata a mínimo tenga un pago superior a la izquierda y otro pago superior a la derecha. La excepción para este criterio consiste en las columnas extrema izquierda y derecha, casos en los cuales la celda candidata a mínimo simplemente debe ser menor en valor que la celda adyacente de la fila.

En una columna de una matriz de pagos, un punto de máximo rendimiento (una cresta) será (según la perspectiva del jugador A) aquel que tenga un pago inferior por encima y un pago inferior por debajo. La excepción se da cuando la celda candidata a máximo local esta ubicada en la fila superior o en la fila inferior, en este caso la celda candidata debe ser mayor en valor que la celda adyacente de la columna.

Un punto de silla sera aquel que sea mínimo local en la fila y a la vez máximo local en la columna. La importancia que tiene un punto de silla es que ni el jugador A ni el jugador B tendrán interés en cambiar sus estratgias por las estrategias adyacentes, pues si A se cambia la fila elegida por una superior o inferior, el valor de su pago se reduce, mientras que si B cambia su estrategia por una columna a la izquierda o a la derecha, el pago para A aumenta (y en un juego suma cero esto es la perdida de valor para B).

B1B2B3
A1718570
A2806569
A39010020


Así pues, el punto silla es atractivo por su significado en elección de alternativas. En una matriz de juego suma cero puede ubicarse un punto MINIMAX. El punto MINIMAX indica la solución del juego seg un un criterio de aversión al riesgo.

Estrategia MINIMAX

Se trata de una estrategia conservadora que sirve para determinar los peores escenarios posibles (los peores resultados posibles) de un juego. usted considera que el oponente distribuye sus ataques de manera uniforme, es decir que puede elegir cualquier estrategia de las que tiene a su disposición sin ningún tipo de discriminación.

Descripción de la técnica MINIMAX no estocástica

lo primero que usted debe hacer es estudiar cada estrategia posible de su oponente. luego de ello determine el peor de los estados del juego para usted derivado de una sola estrategia de su oponente, repita esto para analizar el peor caso asociado a cada estrategia del oponente. finalmente, como usted considera que se trata de escenarios igualmente probables, entonces notará que el juego tiene un máximo valor para usted, y tal es el máximo de los mínimos.

Ahora estudie el juego de su oponente. determine el peor de los estados para él (o sea el mejor para usted) derivado de una sola estrategia de usted. repita esto para analizar el mejor caso asociado a cada estrategia de usted. después de ello, dado que su oponente creerá que usted elige sus estrategias sin ninguna discriminación, entonces encuentre el menor valor del juego para usted de acuerdo a los máximos de asociados a cada estrategia. entonces notara que el juego tiene un valor mínimo para el opnente, y tal sera el mínimo de los máximos.

Ahora compare ambos puntos. Si el máximo de sus mínimos es igual al mínimo de los máximos del oponente, usted ha encontrado un punto silla de montar y puede entonces decir que el juego ya tiene un valor, y es éste valor que es el máximo de sus mínimos e igual al mínimo de los máximos del oponente. ese es el valor minimax.

Ejemplo de solución del problema mediante uso de minimax

Primero veamos la lógica del jugador 1 (aquel que tiene el conjunto de estrategias horizontales). El tiene que computar los valores mínimos obtenibles en cada estrategia. Estos son: 70, 65, 20. El máximo de estos mínimos es 70, y corresponde a la celda A1B3.

Ahora veamos la lógica del jugador 2 (aquel que tiene el conjunto de estrategias verticales). Los valores máximos obtenidos de cada columna son: 90, 100 y 70. El mínimo de estos máximos es 70, y corresponde a la celda, A1B3.

Ambos jugadores coinciden en que, después de minimizar sus máximas pérdidas, el escenario resultante es el A1B3.

Minimax sugiere que usted juegue la estrategia asociada al valor minimax del juego, sobre la base de que el oponente tambien elegirá ese mismo valor minimax. si esto se da, entonces ambos jugadores ya conocen el valor del juego por anticipado y pueden ahorrarse el procedimiento del juego simplemente acordando sobre el escenario minimax.

Si existe un valor minimax, se supone que el oponente debe elegir ese valor para minimizar el valor del juego y que usted debe elegir ese valor para maximizar el valor del juego.

MINIMAX estocástico

En el siguiente juego no hay un punto MINIMAX:

B1B2B3
A1243
A27210
A31132


La formulación y solución de este problema hace uso de la programación lineal. se verá que ya no se buscara la estrategia que minimice el riesgo del jugador A, sino que esta vez elegirá una distribución de probabilidades para la elección de la estrategia. A esto le llamamos una estrategia mixta. Esta estrategia mixta produce un valor ex ante V.

El jugador A posee una distribución de probabilidades para sus opciones igual a:

{p1, p2,..., pn}

El jugador B posee una distribución de probabilidades para sus opciones igual a:

{q1, q2,..., qm}

La idea subyacente al MINIMAX estocástico es encontrar la combinación óptima, aquella que no podra ser vencida (desde un punto de vista 'esperado', pero no cierto, o seguro o determinado). Esta combinación óptima indica que estadísticamente el juego asociado a la estrategia MINIMAX alcanzará el valor esperado V.

Si A elige una estrategia mixta como {pi} entonvcees el valor esperado del juego sera único, e independiente de lo que B pueda querer hacer.

Si B elige una estrategia mixta como {qi} entonces el valor esperado del juego será único, e independiente de lo que A pueda querer hacer.

La estrategia MINIMAX se apoya en la demostración de Von Neumann de Teorema de MINIMAX.

Por ello, MINIMAX es la estrategia de minimización de riesgo. La forma en que se resuelve un MINIMAX estocástico es mediante el uso de programación lineal. A continuación, la forma de realizar el cálculo de la solución MINIMAX:

max V
s.a. (con sujeción a las siguientes restricciones):
V=(p1 + p2 +...+ pn)
a11p1 + a21p2 +...+ an1pn >= V
a12p1 + a22p2 +...+ an2pn >= V
.
.
.
a1np1 + a2np2 +...+ anmqn >= V
p1 + p2 +...+ pm = 1

Usando la transformación ri = pi/V(juego), este planteamiento puede reformularse, tomando la siguiente forma:

min (r1 + r2 +...+ rn)
s.a. (con sujeción a las siguientes restricciones):
a11r1 + a21r2 +...+ an1rn >= 1
a12r1 + a22r2 +...+ an2rn >= 1
.
.
.
a1mr1 + am2r2 +...+ amnrn >= 1

Una vez resuelto este problema de Programación Lineal, se obtendrá m valores ri. Puede calcularse el valor de cada pi mediante las fórmulas:

pi = ri*V

donde:

V = valor(juego) = (r1 + r2 +...+ rn)



Usando esta técnica de cálculos podemos resolver un problema en que no hubiera una solución minimax no estocástica. Por ejemplo, el problema expuesto a continuación puede ser resuelto mediante la técnica MINIMAX estocástica.

Dejamos a usted la tarea de resolver el siguiente juego:

B1B2B3
A1243
A17210
A11132


Ejemplo minimax estocástico para matriz suma cero 2x2

Aquí veremos el tratamiento de un sencilo problema de 2x2. En este caso, la forma de cálculo no requerirá el uso de un programa de optimización por programación lineal, sino que con simple aplicación algebraica encontraremos la solución de problema.

Problema: A y B tienen busca cada uno obtener máximo bienestar, y la interacción de sus decisiones crea un espacio de resultados como el descrito en la matriz siguiente:

acción B1 acción B2
acción A1 0 2
acción A2 3 0


A verá a B como una especie de "clima". Supondrá que dicho clima tomará el camino B1 con una probabilidad q1 y que tomará el camino B2 con una probabilidad q2. El valor del juego para A será:

0.q1 + 2.q2


si A decide optar por A1, y

3.q1 + 0.q2


si A decide optar por A2. En resumen, si A opta por A1, el juego tendrá un valor probable de 2q2

y, si A opta por A2, el el juego tendrá un valor probable de 3q1. Como se ve, son dos los valores probables que arroja el análisis realizado por A.

B también debe realizar dicha adivinanza. Tomando en cuenta ahora el valor negativo del juego para B (ya que bajo la perspectiva de B toda ganancia de A es una pérdida para él) obtenemos:

0.p1 + 3.p2


si B opta por B1 y

2.p1 + 0.p2


si B opta por B2. En resumen, el juego tendrá un valor probable de 3p2 si B opta por B1 y uno de 2p1 si B opta por B2. También B encuentra dos valores probables asociados al análisis probabilístico del juego.

Surge una pregunta importante. Luego de estudiar el aspecto probabilístico del problema, ¿qué decisión tomarán A y B? Tanto A como B deben escoger la opción que maximice el valor del juego para ellos. Por ejemplo, si A calcula que 2q2>3q1 tomará la opción A1. Si B calcula que 2p1>3p2 tomará la opción B2. La solución del juego sería A1-B2. Se llegó a esta solución como resultado de buscar el mayor valor esperado del juego.

El proceso de búsqueda fue efectuado por cada uno de los dos jugadores, A y B. Notemos, no obstante, que se necesitó conocer las probabilidades corespondientes a la tma de decisiones de cada uno: A requirió conocer la distribución de probabilidades de las decisiones de B y B requirió conocer la distribución de probabilidades de las decisiones de A.

Un gran problema surge cuando ni A ni B conocen el valor de las probabilidades contrarias. ¿Existe algún modo de estimar las probabilidades del contrario?

En estos casos, se efectúa análisis minimax.

A conoce los pagos del juego que puede recibir B y comprende que una reducción del riesgo de B es equivalente a plantar que, cualquiera que sea la decisión que éste tome, el valor del juego sea el mismo. Por ello, se afirmará que 3p2 = 2p1. A comprende que a B se le facilitaría su decisión su supusiese que las probabilidades de decisión de A son p1 = 60% y p2 = 40%. Si B realiza el cálculo análogo, deduce que las probabilidades suyas, osea las probabilidades de B que convienen a A son q1 = 40% y q2 = 60%. Un acuerdo o convención tácitos resultarían en un valor mínimo del riesgo relativo al juego. El valor mixto ex ante del juego será 1.20, y será, dadas las condiciones implicadas en el método del riesgo mínimo, la misma para cada uno de los jugadores.

El valor ex post del juego no está determinado. A y B pueden recurrir a una ruleta u otro mecanismo de generación de valores aleatorios para decidir la opción que tomará cada uno. El valor del juego puede ser cualquiera de los que sigue:
  • A cobrando a B 3 unidades al 16%
  • A cobrando a B 2 unidades al 36%
  • A no recibiendo nada ni pagando nada a B al 48%
Esta ruleta sería construida de la manera que sigue: 4 celdas con el número '3', 9 celdas con el número '2' y 12 celdas con el número '0'. Si el juego se jugase 100 veces, se esperaría que la ganancia total de A fuera 120, asociada a su ganancia esperada por juego de 1.2. Esto se daríá de la manera siguiente: 16 veces ganaría 3, totalizando 48; 36 veces ganaría 2, totalizando 72, y 48 veces no ganaría nada, totalizan do 0. El gran total sería de 120 para los 100 juegos y de 1.2 como valor promedio.

Pero si se jugase una sola vez, el resultado puede ser una ganancia para A (y pérdida para B) de 0, 2 o 3 de acuerdo a la distribución indicada líneas arriba. En todo caso, la probabilidad acumulada de ganar un valor que fuese 2 o 3 es de 52%, frente a 48% de probabilidad de no ganar ni perder nada.





AugustoRufasto

AugustoRufasto
Freelance analysis
Standard problem solving starting from US$15.00
Hourly fee US$100.00


+51-1-97213492


rufasto2000@gmail.com