Estrategias puras y mixtas. Método para calcular estrategias óptimas.

Teoría de juegos de estrategia mixta.

Estrategias mixtas

Si un juego matricial no tiene un punto de silla en estrategias puras, entonces se encuentran los precios superior e inferior del juego. Muestran que el jugador 1 no recibirá un pago mayor que el precio máximo del juego, y que al jugador 1 se le garantiza un pago que no es menor que el precio mínimo del juego.

La estrategia mixta de un jugador es un conjunto completo de sus estrategias puras cuando el juego se repite muchas veces en las mismas condiciones con probabilidades dadas. Resumamos lo dicho y enumeremos las condiciones para utilizar estrategias mixtas:

• * juego sin punto de silla;
• * los jugadores usan una mezcla aleatoria de estrategias puras con probabilidades determinadas;
• * el juego se repite muchas veces en condiciones similares;
• * durante cada movimiento, ningún jugador es informado sobre la elección de estrategia por parte del otro jugador;
• * Se permite promediar los resultados del juego.

Se utilizan las siguientes designaciones para estrategias mixtas.

Para el jugador 1, una estrategia mixta consiste en utilizar estrategias puras A 1, A 2, ..., A t con las correspondientes probabilidades p 1, p 2, ..., p t.

Para el jugador 2

q j es la probabilidad de utilizar la estrategia pura B j .

En el caso en que p i = 1, para el jugador 1 tenemos una estrategia pura

Las estrategias puras del jugador son los únicos eventos posibles incompatibles. En un juego de matrices, conociendo la matriz A (se aplica tanto al jugador 1 como al jugador 2), podemos determinar cuándo dados vectores y el pago promedio (expectativa matemática del efecto) del jugador 1:

donde y son vectores;

p i y q i son componentes de vectores.

Al aplicar sus estrategias mixtas, el jugador 1 busca maximizar su pago promedio y el jugador 2 busca reducir este efecto al mínimo valor posible. El jugador 1 se esfuerza por alcanzar

El jugador 2 se asegura de que se cumpla la condición.

Denotemos también los vectores correspondientes a las estrategias mixtas óptimas de los jugadores 1 y 2, es decir dichos vectores y para los cuales se cumplirá la igualdad

El costo del juego es el pago promedio del jugador 1 cuando ambos jugadores usan estrategias mixtas. Por tanto, la solución del juego de matrices es:

• - estrategia mixta óptima del jugador 1;
• - estrategia mixta óptima para el jugador 2;

Precio del juego.

Las estrategias mixtas serán óptimas (y) si forman un punto de silla para la función, es decir,

Existe un teorema fundamental para los juegos matemáticos.

Para un juego de matrices con cualquier matriz A de magnitud

existen y son iguales entre sí: = = .

Cabe señalar que a la hora de elegir estrategias optimas Al jugador 1 siempre se le garantizará una ganancia promedio, no menor que el precio del juego, para cualquier estrategia fija jugador 2 (y viceversa para el jugador 2). Las estrategias activas de los jugadores 1 y 2 son estrategias que forman parte de las estrategias mixtas óptimas de los jugadores correspondientes con probabilidades distintas de cero. Esto significa que las estrategias mixtas óptimas de los jugadores pueden no incluir todas sus estrategias dadas a priori.

Resolver un juego significa encontrar el precio del juego y las estrategias óptimas. Comencemos nuestra consideración de los métodos para encontrar estrategias mixtas óptimas para juegos matriciales con el juego mas simple, descrito en la matriz 22. Los juegos con punto de silla no se considerarán específicamente. Si se obtiene un punto de silla, esto significa que hay estrategias no rentables que deberían abandonarse. En ausencia de un punto de silla, se pueden obtener dos estrategias mixtas óptimas. Como ya se señaló, estas estrategias mixtas se escriben de la siguiente manera:

Esto significa que hay una matriz de pago.

un 11 p 1 + un 21 p 2 = ; (1.16)

un 12 p 1 + un 22 p 2 = ; (1.17)

p 1 + p 2 = 1. (1.18)

a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)

a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)

donde obtenemos los valores óptimos:

Conociendo y, encontramos:

Habiendo calculado, encontramos:

un 11 q 1 + un 12 q 2 = ; q 1 + q 2 = 1; (1.24)

un 11 q 1 + un 12 (1 - q 1) = . (1.25)

a las 11 a 12 . (1.26)

El problema está solucionado, ya que se han encontrado los vectores y el precio del juego. Teniendo la matriz de pagos A, puedes resolver el problema gráficamente. Con este método, el algoritmo de solución es muy sencillo (Fig. 2.1).

• 1. Se traza un segmento de longitud unitaria a lo largo del eje de abscisas.
• 2. El eje y muestra las ganancias de la estrategia A 1.
• 3. En una línea paralela al eje de ordenadas, en el punto 1, se representan las ganancias de la estrategia a 2.
• 4. Los extremos de los segmentos se designan para a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 y se dibujan dos líneas rectas b 11 b 12 y b 21 b 22.
• 5. Se determina la ordenada del punto de intersección con. Ella es igual. La abscisa del punto c es igual a p 2 (p 1 = 1 - p 2).

Arroz. 1.1.

Este método tiene un área de aplicación bastante amplia. Esto se basa en propiedad general juegos TP, que consiste en que en cualquier juego TP cada jugador tiene una estrategia mixta óptima en la que el número de estrategias puras no es mayor que min(m, n). De esta propiedad podemos obtener un corolario bien conocido: en cualquier juego 2n y m2, cada estrategia óptima contiene como máximo dos estrategias activas. Esto significa que cualquier juego 2n y m2 se puede reducir al juego 22. En consecuencia, los juegos 2n y m2 se pueden resolver gráficamente. Si la matriz de juego finita tiene dimensión mn, donde m > 2 y n > 2, entonces se utiliza la programación lineal para determinar las estrategias mixtas óptimas.

En general, V * ≠ V *: no existe un punto de silla. Tampoco existe una solución óptima en estrategias puras. Sin embargo, si ampliamos el concepto de estrategia pura introduciendo el concepto de estrategia mixta, entonces es posible implementar un algoritmo para encontrar la solución óptima a un problema de juego no bien definido. En tal situación, se propone utilizar un enfoque estadístico (probabilístico) para encontrar la solución óptima al juego de suma cero. Para cada jugador, junto con un conjunto determinado de estrategias posibles para él, se introduce un vector desconocido de probabilidades (frecuencias relativas) con el que se debe aplicar una u otra estrategia.

Denotemos el vector de probabilidades (frecuencias relativas) de elegir estrategias dadas del jugador A de la siguiente manera:
P = (p 1, p 2,…, p m),
donde p i ≥ 0, p 1 + p 2 +…+ p m = 1. El valor p i se llama probabilidad (frecuencia relativa) de utilizar la estrategia A i.

De manera similar, para el jugador B, se introduce un vector desconocido de probabilidades (frecuencias relativas) que tiene la forma:
Q = (q 1, q 2,…, q n),
donde q j ≥ 0, q 1 + q 2 +…+ q n = 1. El valor q j se denomina probabilidad (frecuencia relativa) de utilizar la estrategia B j. El conjunto (combinación) de estrategias puras A 1, A 2, …A m y B 1, B 2, …B n en combinación con vectores de probabilidades de elegir cada una de ellas se denominan estrategias mixtas.

El teorema principal de la teoría de los juegos finitos de suma cero es teorema de von Neumann: Todo juego de matrices finitas tiene al menos una solución óptima, posiblemente entre estrategias mixtas..
De este teorema se deduce que un juego no bien definido tiene al menos una solución óptima en estrategias mixtas. En tales juegos, la solución será un par de estrategias mixtas óptimas P * y Q *, de modo que si uno de los jugadores se adhiere a su estrategia óptima, entonces no es rentable para el otro jugador desviarse de su estrategia óptima.
El pago promedio del jugador A está determinado por la expectativa matemática:

Si la probabilidad (frecuencia relativa) de utilizar una estrategia es diferente de cero, entonces dicha estrategia se llama activo.

Las estrategias P*, Q* se llaman mixto óptimo estrategias si M A (P, Q*) ≤ M A (P*, Q*) ≤ M A (P*, Q) (1)
En este caso M A (P * , Q *) se llama en la costa juegos y se denota por V (V * ≤ V ≤ V *). La primera de las desigualdades (1) significa que La desviación del jugador A de su estrategia mixta óptima. siempre que el jugador B se ciña a su estrategia mixta óptima, conduce a una disminución en las ganancias promedio jugador A. La segunda de las desigualdades significa que La desviación del jugador B de su estrategia mixta óptima. siempre que el jugador A se ciña a su estrategia mixta óptima, conduce a un aumento en la pérdida promedio del jugador B.

En general, este tipo de problemas se pueden resolver con éxito con esta calculadora.

Ejemplo.

1. Compruebe si la matriz de pago tiene un punto de silla.. En caso afirmativo, escribimos la solución del juego en estrategias puras.

Suponemos que el jugador I elige su estrategia de tal manera que maximice su pago, y que el jugador II elige su estrategia de tal manera que minimice el pago del jugador I.

Encontramos el pago garantizado determinado por el precio más bajo del juego a = max(a i) = 2, lo que indica la estrategia pura máxima A 1 .
El precio superior del juego es b = min(b j) = 7. Lo que indica la ausencia de punto silla, ya que a ≠ b, entonces el precio del juego está dentro del rango 2 ≤ y ≤ 7. Encontramos una solución al juego en estrategias mixtas. Esto se explica por el hecho de que los jugadores no pueden anunciar su estrategias puras: Deberían ocultar sus acciones. El juego se puede resolver permitiendo a los jugadores elegir sus estrategias al azar (mezclando estrategias puras).

2. Verifique la matriz de pago para ver las filas y columnas dominantes..
EN matriz de pago no hay filas dominantes ni columnas dominantes.

3. Encuentra una solución al juego en estrategias mixtas..
Escribamos un sistema de ecuaciones.
Para el jugador I
4p 1 +7p 2 +2p 3 = y
7p 1 +3p 2 +p 3 = y
2p 1 +2p 2 +8p 3 = y
pag 1 + pag 2 + pag 3 = 1

Para el jugador II
4q 1 +7q 2 +2q 3 = y
7q 1 +3q 2 +2q 3 = y
2q 1 +q 2 +8q 3 = y
q 1 + q 2 + q 3 = 1

Resolviendo estos sistemas usando el método de Gauss, encontramos:

y = 4 1/34
p 1 = 29 / 68 (probabilidad de utilizar la 1ª estrategia).
p 2 = 4 / 17 (probabilidad de utilizar la 2da estrategia).
p 3 = 23 / 68 (probabilidad de utilizar la 3ª estrategia).

Estrategia mixta óptima del jugador I: P = (29 / 68; 4 / 17; 23 / 68)
q 1 = 6 / 17 (probabilidad de utilizar la 1ª estrategia).
q 2 = 9 / 34 (probabilidad de utilizar la segunda estrategia).
q 3 = 13 / 34 (probabilidad de utilizar la 3ª estrategia).

Estrategia mixta óptima del jugador II: Q = (6/17; 9/34; 13/34)
Precio del juego: y = 4 1 / 34

Un juego matricial de suma cero para dos jugadores puede considerarse como el siguiente juego abstracto para dos jugadores.

El primer jugador tiene metro estrategias i = 1,2,...,metro, el segundo tiene norte estrategias j= 1,2,...,norte. Cada par de estrategias ( i, j) número coincidente A yo , expresando la ganancia del jugador 1 a expensas del jugador 2 si el primer jugador acepta su i- tu estrategia, y 2 – la suya propia j aésima estrategia.

Cada jugador realiza un movimiento: el jugador 1 elige su iésima estrategia ( i= ), 2– tuyo jésima estrategia ( j=
), después de lo cual el jugador 1 recibe las ganancias A yo a expensas del jugador 2 (si A yo < 0, entonces esto significa que el jugador 1 paga la segunda cantidad | A yo|). Aquí es donde termina el juego.

Estrategia de cada jugador. i=
; j =
A menudo se le llama estrategia pura.

Si consideramos la matriz

A=

luego realizando cada juego de un juego matricial con una matriz A todo se reduce a la elección del jugador 1 iª fila y jugador 2 jª columna y el jugador 1 (a expensas del jugador 2) recibe ganancias a ij .

Lo principal en el estudio de los juegos es el concepto de estrategias óptimas de los jugadores. Este concepto tiene intuitivamente el siguiente significado: la estrategia de un jugador es óptima si el uso de esta estrategia le proporciona la mayor ganancia garantizada para todas las estrategias posibles del otro jugador. Basándose en estas posiciones, el jugador 1 examina la matriz de pagos. A como sigue: para cada valor i (i =
) el valor mínimo de ganancia se determina dependiendo de las estrategias utilizadas por el jugador 2

A yo (i=
)

aquellos. Se determinan las ganancias mínimas para el jugador 1, siempre que acepte su iª estrategia pura, entonces a partir de estos pagos mínimos se encuentra dicha estrategia i = i oh, en el que esta ganancia mínima será máxima, es decir situado

A yo =
=(1)

Definición . Número , definido por la fórmula (1) se llama precio neto más bajo juegos y muestra qué ganancias mínimas puede garantizar el jugador 1 aplicando sus estrategias puras a todas las acciones posibles del jugador 2.

El jugador 2, con su comportamiento óptimo, debe esforzarse, si es posible, a través de sus estrategias, en minimizar la recompensa del jugador 1. Por lo tanto, para el jugador 2, encontramos

A yo

aquellos. Se determina la ganancia máxima del jugador 1, siempre que el jugador 2 use su jª estrategia pura, entonces el jugador 2 busca la suya propia j = j 1 una estrategia en la que el jugador 1 recibirá una ganancia mínima, es decir, encuentra

a yo =
=(2).

Definición . Número , determinado por la fórmula (2), se llama precio máximo neto juegos y muestra qué ganancias máximas puede garantizar el jugador 1 gracias a sus estrategias.

En otras palabras, usando sus estrategias puras, el jugador 1 puede asegurar una victoria no menos de , y el jugador 2, mediante el uso de sus estrategias puras, puede evitar que el jugador 1 gane más de .

Definición . Si en un juego con matriz A =entonces dicen que este juego tiene sillín punto en puras estrategias y Precio neto juegos

 = =.

Punto de silla es un par de estrategias puras (i oh , j oh ) respectivamente, los jugadores 1 y 2, en los que se logra la igualdad =. Este concepto tiene el siguiente significado: si uno de los jugadores sigue la estrategia correspondiente al punto de silla, entonces el otro jugador no puede hacer nada mejor que seguir la estrategia correspondiente al punto de silla. Matemáticamente, esto se puede escribir de otra manera:

Dónde i, j– cualquier estrategia pura de los jugadores 1 y 2, respectivamente; (i oh , j oh ) – estrategias que forman un punto de silla.

Por tanto, basándose en (3), el elemento de silla de montar
es mínimo en la i o -ésima fila y máximo en la j o -ésima columna de la matriz A. Encontrar el punto de silla de la matriz A ocurre de la siguiente manera: en la matriz A secuencialmente en cada línea Encuentre el elemento mínimo y verifique si este elemento es el máximo en su columna. En caso afirmativo, entonces es un elemento silla y el par de estrategias correspondientes forma un punto silla. Un par de estrategias puras (i oh , j oh ) jugadores 1 y 2, formando un punto de silla y un elemento de silla
, llamado solución de juego . Donde i oh Y j oh son llamados limpieza optima estrategias respectivamente los jugadores 1 y 2.

Ejemplo 1

El punto silla es el par ( i oh = 3;j oh= 1), en el cual = == 2.

Tenga en cuenta que aunque el pago en la situación (3;3) también es igual a 2 = =, no es un punto de silla, porque esta ganancia no es la máxima entre las ganancias de la tercera columna.

Ejemplo 2

Del análisis de la matriz de pagos se desprende claramente que
, es decir. esta matriz no tiene punto de silla. Si el jugador 1 elige su estrategia maximin pura i = 2, luego el jugador 2, eligiendo su minimax j= 2, solo perderán 20. En este caso, es rentable para el jugador 1 elegir la estrategia i = 1, es decir. desviarse de su estrategia maximin pura y ganar 30. Entonces será rentable para el jugador 2 elegir la estrategia j = 1, es decir desviarse de su estrategia minimax pura y perder 10. A su vez, el jugador 1 debe elegir su segunda estrategia para ganar 40, y el jugador 2 responderá eligiendo su segunda estrategia, etc.

Veamos un ejemplo. Sea la matriz del juego (4):

Necesitamos encontrar el precio más bajo del juego α, el precio más alto del juego β y las estrategias minimax y comprobar si son estables. Solución. Del análisis de la columna y fila adicionales obtenemos: α = 5, β = 5. ¡Maximin es igual a minimax! Este es un caso especial. ¿Qué se sigue de esto? Tomemos un par de estrategias minimax: K 2 y C 3. Si ambos siguen estas estrategias, entonces el pago será 5. Ahora, digamos que hemos aprendido sobre el comportamiento del enemigo. qué hacemos? ¡Nada! Seguiremos adhiriéndose a la estrategia K2, porque cualquier desviación de ella no nos resulta rentable. Ya sea que sepamos o no el comportamiento del enemigo, ¡aún así seguiremos con la estrategia K 2! Lo mismo se aplica a los "azules": no tiene sentido que cambien su estrategia C 3. EN en este ejemplo el par de estrategias K 2 y C 3 es estable, es decir, representa una posición de equilibrio y proporciona una solución al juego. ¿Por qué pasó esto? Porque hay un elemento especial 5 en la matriz; es mínimo en su fila y al mismo tiempo máximo en su columna. Tal elemento se llama punto de silla. Si la matriz tiene un punto silla (es decir, el precio inferior del juego es igual al superior), entonces el juego tiene una solución en estrategias puras: es un par de estrategias que se cruzan en el punto silla. El punto de silla en sí da el precio del juego; en nuestro ejemplo es igual a 5. La clase de juegos que tienen un punto de silla es de gran importancia en la teoría de juegos. En particular, se ha demostrado que si, según las reglas del juego, cada jugador conoce el resultado de todos los movimientos anteriores, tanto propios como de su oponente (el llamado juego con información completa), entonces el juego tiene un punto de silla y, por lo tanto, tiene una solución en estrategias puras. Ejemplos de juegos con información completa incluyen: ajedrez, damas, tres en raya, etc. Pongamos un ejemplo de un juego con información completa, cuya solución es fácil de encontrar. Dos jugadores, K y C, colocan alternativamente monedas idénticas en la mesa redonda. La posición de cada moneda se elige de forma arbitraria, siempre que no se superponga con otras. El último jugador en colocar una moneda gana (cuando no queda espacio para otros). Vale la pena pensar un poco para asegurarse de que el resultado de este juego sea siempre una conclusión inevitable y que exista una estrategia bien definida que garantice una victoria para el jugador que ponga la moneda primero (sea K). Es decir, K debe colocar la primera moneda en el centro de la mesa, y luego, para cada movimiento, C debe responder con un movimiento exactamente simétrico con respecto al centro de la mesa. El pobre S puede comportarse como quiera, pero todavía no tiene escapatoria... Obviamente, un juego así sólo tiene sentido para aquellos que no conocen la solución. Es curioso que la situación sea exactamente la misma con tales juego popular¡como el ajedrez! Este juego sólo tiene sentido hasta que se encuentre una solución. Se ha demostrado teóricamente que existe una solución y que el resultado de una partida de ajedrez está esencialmente predeterminado: si cada lado utiliza su propia estrategia óptima, entonces la partida terminará siempre con una victoria para las blancas o siempre con una victoria para las negras. ¡o siempre en empate! ¿Pero qué exactamente? Esto aún no lo sabemos, ya que el número de estrategias posibles es demasiado grande para poder construir una matriz de un juego de ajedrez y encontrar en ella un punto de silla... Probablemente, los aficionados al ajedrez estén interesados ​​en el hecho de que el ajedrez El juego no se resolverá pronto. Para concluir, observemos que no puede haber uno, sino varios puntos silla en la matriz; entonces hay tantas soluciones al juego en estrategias puras como puntos silla. Cada uno de ellos otorga una ganancia igual al precio del juego.

Entre los juegos finitos de importancia práctica, los juegos con punto de silla son relativamente raros; Un caso más típico es cuando el precio superior e inferior del juego son diferentes. Analizando las matrices de tales juegos, llegamos a la conclusión de que si a cada jugador se le da la opción

una sola estrategia. Entonces, contando con un enemigo que actúa racionalmente, esta elección debe estar determinada por el principio minimax. Al seguir nuestra estrategia maximin, independientemente del comportamiento del enemigo, obviamente nos garantizamos una victoria igual al precio más bajo del juego a. Surge una pregunta natural: ¿es posible garantizar un pago promedio mayor que a si se utiliza no solo una estrategia “pura”, sino que se alternan aleatoriamente varias estrategias?

Estas estrategias combinadas, que consisten en el uso de varias estrategias puras, alternadas según una ley aleatoria con una determinada relación de frecuencia, se denominan estrategias mixtas en teoría de juegos.

Obviamente, cada estrategia pura es un caso especial de una mixta, en la que todas las estrategias excepto una se aplican con frecuencia cero, y ésta con frecuencia 1.

Resulta que, utilizando no sólo estrategias puras, sino también mixtas, es posible para cada juego finito obtener una solución, es decir, un par de estrategias (en el caso general mixtas) tales que cuando ambos jugadores las usan, el El pago será igual al precio del juego, y cuando cualquier desviación unilateral de la estrategia óptima sólo puede cambiar el pago en una dirección desfavorable para el desviado.

La afirmación expuesta constituye el contenido del llamado teorema fundamental de la teoría de juegos. Este teorema fue demostrado por primera vez por von Neumann en 1928. Las demostraciones conocidas del teorema son relativamente complejas; Por tanto, daremos únicamente su formulación.

Todo juego finito tiene al menos una solución (posiblemente en el ámbito de las estrategias mixtas).

La recompensa resultante de la decisión se llama costo del juego. Del teorema principal se deduce que todo juego finito tiene un precio. Obviamente, el precio del juego v siempre se encuentra entre el precio más bajo del juego a y precio superior juegos :

De hecho, existe una ganancia máxima garantizada que podemos asegurarnos utilizando sólo nuestras estrategias puras. Dado que las estrategias mixtas incluyen, como caso especial, todas las puras, entonces, además de las puras, también se permiten las mixtas.

estrategia, nosotros, en cualquier caso, no empeoramos nuestras capacidades; por eso,

De manera similar, considerando las capacidades del enemigo, mostraremos que

de donde se sigue la desigualdad requerida (3.1).

Introduzcamos una notación especial para estrategias mixtas. Si por ejemplo nuestra estrategia mixta consiste en utilizar estrategias AL, con frecuencias y denotaremos esta estrategia

De manera similar, denotaremos la estrategia mixta del enemigo:

¿Dónde están las frecuencias en las que se mezclan las estrategias?

Supongamos que hemos encontrado una solución al juego que consta de dos estrategias mixtas óptimas S, S. En el caso general, no todas las estrategias puras disponibles para un jugador determinado están incluidas en su estrategia mixta óptima, sino solo algunas. A las estrategias incluidas en la estrategia mixta óptima de un jugador las llamaremos estrategias “útiles”.

Resulta que la solución del juego tiene otra propiedad notable: si uno de los jugadores sigue su estrategia mixta óptima 5 (5). entonces el pago permanece sin cambios e igual al precio del juego v, independientemente de lo que haga el otro jugador, si él. simplemente no va más allá de sus estrategias “útiles”. Por ejemplo, puede utilizar cualquiera de sus estrategias "útiles" en forma pura, y también puedes mezclarlos en cualquier proporción.

Probemos esta afirmación. Que haya una solución al juego. Para ser específicos, asumiremos que la estrategia mixta óptima consiste en una combinación de tres

En consecuencia, las estrategias "útiles" consisten en una combinación de tres estrategias "útiles"

Además, se afirma que si nos adherimos a la estrategia S, entonces el oponente puede usar estrategias en cualquier proporción, y la recompensa permanecerá sin cambios y seguirá siendo igual al costo del juego.

Si en un juego cada uno de los oponentes usa la misma estrategia, entonces se dice que este juego se juega en estrategias puras, y las estrategias de los jugadores A y B se llamarán estrategias puras.En un juego de suma cero, un par de estrategias se llama equilibrio(estable) si a alguno de los jugadores no le resulta rentable retirarse de sus estrategias. Tiene sentido utilizar estrategias puras si los jugadores son conscientes de las acciones del oponente. Si este no es el caso, entonces se viola la idea de equilibrio y el juego se puede jugar como resulta. Las estrategias A1 B1 son estables con respecto a la información sobre el comportamiento del oponente. Un signo de la estabilidad de un par de estrategias es la igualdad de los precios superior e inferior del juego. Y el caso A1 B1 será

ν = α = β. ν > 0, entonces el jugador A ganará si ν< 0, то в выигрыше игрок В. Если ν = 0, в этом случае игра справедлива для обоих игроков. Не все матричные игры имеют седловые точки.

Teorema: todo juego con información completa tiene un punto de silla y por lo tanto se resuelve con estrategias puras, es decir hay un par de estrategias estables que dan un pago estable igual a ν. Si la matriz no tiene un punto de silla, entonces el costo del juego es α<ν<β. Это означает, что первый игрок, используя максиминный принцип, обеспечит себе выигрыш не менее, чем α. А второй игрок придерживаясь минимаксного подхода обеспечит себе проигрыш не больше верхней цены игры. Игра будет оптимальна, если оба игрока будут применять смешанные стратегии.Случайная величина, значениями которой являются чистые стратегии, называется смешанной стратегией для этого игрока.

Especificar una estrategia mixta significa especificar las probabilidades con las que se utilizan estrategias puras.

S A = || pág. 1, pág. 2…. p m || ,SB = || q1, q2…. q metro || , A: ∑ pi = 1 , B: ∑ qi = 1

El juego se puede repetir varias veces, pero en cada juego el jugador sigue una estrategia mixta, donde las estrategias puras se adhieren a las probabilidades p i y q j.

El modelo de estrategia mixta se diferencia del modelo de estrategia pura. En el caso de estrategias mixtas, las tácticas de los jugadores serán más flexibles, porque Los jugadores saben de antemano qué estrategia pura utilizarán.

Supongamos que tanto el jugador A como el jugador B tienen una estrategia mixta. Es necesario determinar A: ∑∑ a ij p i q j

Para el jugador B, la pérdida esperada es igual a la ganancia esperada del jugador A. Las ganancias del primer jugador y la pérdida promedio del segundo jugador son iguales entre sí.

18.Métodos para resolver un juego finito de dos personas de orden m*n.

Supongamos que todos los elementos de la matriz de pagos son 0≤aij. Entonces α≤ν≤β. Según el teorema fundamental de los juegos matriciales, cualquier juego matricial tiene 2 estrategias mixtas óptimas.

S A = (p 1 , p 2 , … , p norte )

S segundo = (p 1 , p 2 , … , p norte )

Resolvemos el juego para el jugador A, asumiendo que el jugador B usa solo estrategias puras. Entonces

a 11 p 1 + a 21 p 2 + … + a m1 p m ≥ ν: B 1

a 12 p 1 + a 22 p 2 + … + a m2 p m ≥ ν: B 2 (1)

a 1n p 1 + a 2n p 2 + … + a mn p m ≥ ν: B n

X 1 = P 1 /ν, X 2 = P 2 /ν … X m = P m /ν

a 11 X 1 … + a m1 p m ≥ 1

a 1n X 1 … + a m1 p m ≥ 1 (2)

p 1 +p 2 +…+p m =1

X 1 +X 2 +…+X m = 1/ν (3)

L(x) = X 1 +X 2 +…+X m -> mín (4)

Definamos un problema de programación lineal.

ν = 1/(X 1 0 +X 2 0 …X m 0) (5)

P1 = X 1 0 *ν optar

p2 = X 2 0 *ν opt (6)

mín L(x) = ∑x yo

∑a ij: 1≤x i (7) (problema directo)

0≤x i (i=1,2..)

a 11 q 1 + a 21 q 2 + … + a m1 q m< ν: A 1

a 21 q 1 + a 22 q 2 + … + a m2 q m< ν: A 2 (8)

un m1 q 1 + un m2 q 2 + … + un mn q m< ν: A m

Y 1 = q 1 /ν, Y 2 = q 2 /ν ... Y m = q m /ν

q 1 +q 2 +…+q n =1

y 1 +y 2 +…+y norte =1/ν

L(y)=∑y j -> máximo

∑a ij , y i ≤1 (i=1,2…) (9) (problema dual)

y 1 0 +y 2 0 …y m 0 = 1/ν opt

ν opt = 1/∑y m 0

Q1 = y 1 0 *ν optar

q2 = y 2 0 *ν optar

ν=1/∑x i = 1/∑y i = 1/min L(x) = 1/ máx L(y) (11)

1) α = 1, β = 3

2) No hay simplificaciones.

L(x)=x 1 +x 2 +x 3 => mín.

x 1 +3x 2 +x 3 >= 1

2x 1 +x 2 +x 3 >=1

3x 1 +x 2 +x 3 >=1

x 1 = 2/9, x 2 = 2/9, x 3 = 1/9

ν=1/(2/9+2/9+1/9)=9/5

pag 1 =x 1 *ν=2/5

S A =(2/5, 2/5, 1/5)

problema dual

L(y) = y 1 +y 2 +y 3 => máx.

y 1 +2y 2 +3y 3 ≤ 1 y 1 =2/9

3y 1 +y 2 +y 3 ≤1 => y 2 =2/9 máx L(y) = 5/9

y 1 +3y 2 +y 3 ≤1 y 3 =1/9

ν=1/(2/9+2/9+1/9)=9/5

q 1 =y 2 *ν=(2/9)*(9/5)=2/5

q 2 =(2/9)*(9/5)=2/5

q 3 =(1/9)*(9/5)=1/5

SB =(2/5, 2/5, 1/5)

El problema de mxn se reduce a un problema de programación lineal.

Un método aproximado para resolver juegos matriciales mxn (Brown-Robinson).

El jugador A y el jugador B se turnan para utilizar estrategias puras. Cada jugador intenta aumentar sus ganancias utilizando enfoques maximin o minimax. No es la ganancia promedio la que se minimiza (maximiza), sino la acumulada. La teoría muestra que dicho método inevitablemente nos dará ganancias óptimas y estrategias mixtas óptimas.