Si hay varias partes (personas) en conflicto, cada una de las cuales toma una determinada decisión determinada por un conjunto de reglas determinado, y cada una de las personas conoce el estado final de la situación del conflicto con pagos predeterminados para cada una de las partes, entonces se juega un juego. se dice que tiene lugar.
La tarea de la teoría de juegos es elegir una línea de comportamiento para un jugador determinado, cuya desviación sólo puede reducir sus ganancias.
Algunas definiciones del juego
La valoración cuantitativa de los resultados del juego se llama pago.
Dobles (dos personas) se llama juego de suma cero si la suma de los pagos es cero, es decir si la pérdida de un jugador es igual a la ganancia del otro.
Se llama una descripción inequívoca de la elección de un jugador en cada una de las posibles situaciones en las que debe realizar un movimiento personal. estrategia del jugador .
La estrategia de un jugador se llama óptima si, cuando el juego se repite muchas veces, le proporciona al jugador el máximo posible. ganancias promedio(o, lo que es lo mismo, la mínima ganancia media posible).
Juego definido por una matriz. A teniendo metro líneas y norte columnas se llama un juego de dimensiones de pares finitos metro* norte;
Dónde i=
- estrategia del primer jugador con mestrategia;
j=
- estrategia del segundo jugador que tiene n estrategias;
yo– las ganancias del primer jugador i-estrategia cuando es utilizada por el segundo j aésima estrategia (o, lo que es lo mismo, la pérdida de la segunda en su j-ésima estrategia, cuando se usa por primera vez i th);
A = yo– matriz de pagos del juego.
1.1 Jugar con estrategias puras
Precio de juego bajo (para el primer jugador)
= máximo (mín. yo). (1.2)
i j
Precio máximo del juego (para el segundo jugador):
= mín.
(máximo
yo)
. (1.3)
j i
Si = , el juego se llama juego de punto de silla (1.4), o juego de estrategias puras. Donde V = = llamado un juego valioso ( V- precio del juego).
Ejemplo. Se proporciona la matriz de pago del juego A para 2 personas. estrategias optimas para cada jugador y el precio del juego:
(1.4)
máximo 10 9 12 6
i
mín. 6
j
- estrategia del primer jugador (fila).
Estrategia del segundo jugador (columnas).
- precio del juego.
Por tanto, el juego tiene un punto de silla. Estrategia j = 4 – estrategia óptima para el segundo jugador i=2 - para el primero. Tenemos un juego de pura estrategia.
1.2 Juegos con estrategias mixtas
Si la matriz de pago no tiene un punto de silla, es decir 
, y nadie en el juego puede elegir un plan como estrategia óptima, los jugadores cambian a "estrategias mixtas". Además, cada jugador utiliza cada una de sus estrategias varias veces durante el juego.
Un vector, cada uno de cuyos componentes muestra la frecuencia relativa del uso por parte del jugador de la estrategia pura correspondiente, se denomina estrategia mixta de este jugador.
X= (X 1 …X i …X metro) – estrategia mixta del primer jugador.
Ud.= (en 1 ...y j ...y norte) – estrategia mixta del segundo jugador.
Xi , y j– frecuencias relativas (probabilidades) de jugadores que utilizan sus estrategias.
Condiciones de uso de estrategias mixtas.
.
(1.5)
Si X* = (X 1 * ….X i*... X metro*) – estrategia óptima elegida por el primer jugador; Y* = (en 1 * …en j*... en norte*) es la estrategia óptima elegida por el segundo jugador, entonces el número es el coste del juego.
(1.6)
Para que el número V era el precio del juego, y X* Y en* - estrategias óptimas, es necesario y suficiente para satisfacer las desigualdades
(1.7)
Si uno de los jugadores utiliza la estrategia mixta óptima, entonces su pago es igual al coste del juego. V independientemente de la frecuencia con la que el segundo jugador utilizará las estrategias incluidas en la óptima, incluidas las estrategias puras.
Reducir los problemas de teoría de juegos a problemas de programación lineal.
Ejemplo. Encuentre una solución al juego definido por la matriz de pagos. A.
Una = 
(1.8)
y 1 y 2 y 3
Solución:
Creemos un par dual de problemas de programación lineal.
Para el primer jugador
(1.9)
en 1 +en 2 +en 3 = 1 (1.10)
Liberarse de la variable V(precio del juego), divida los lados izquierdo y derecho de las expresiones (1.9), (1.10) en V. habiendo aceptado en j /V para una nueva variable z i, obtenemos nuevo sistema restricciones (1.11) y función objetivo (1.12)
(1.11)
.
(1.12)
De manera similar, obtenemos el modelo de juego para el segundo jugador:
(1.13)
X 1 +X 2 +X 3 = 1 . (1.14)
Reducir el modelo (1.13), (1.14) a una forma sin variable V, obtenemos
(1.15)
,
(1.16)
Dónde 
.
Si necesitamos determinar la estrategia de comportamiento del primer jugador, es decir frecuencia relativa de uso de sus estrategias ( X 1 ….X i …X metro), usaremos el modelo del segundo jugador, porque estas variables están en su modelo de pagos (1.13), (1.14).
Reduzcamos (1.15), (1.16) a la forma canónica
(1.17)
Tarea:
El juego de matrices viene dado por la siguiente matriz de pagos:
| Estrategias "B" | ||||||||
| Estrategias "A" | B 1 | B 2 | ||||||
| un 1 | 3 | 5 | ||||||
| un 2 | 6 |
|
||||||
Encuentre la solución al juego de matrices, a saber:
- encontrar el precio máximo del juego;
- precios má bajo juegos;
- precio neto del juego;
- indicar las estrategias óptimas de los jugadores;
- traer solución gráfica(interpretación geométrica), si es necesario.
Paso 1
Determinemos el precio más bajo del juego - α
Precio de juego más bajoα es la ganancia máxima que podemos garantizarnos en un juego contra un oponente razonable si utilizamos una y sólo una estrategia durante todo el juego (esta estrategia se llama “pura”).Encontremos en cada fila de la matriz de pagos. mínimo elemento y escríbalo en una columna adicional (Seleccionado amarillo ver Tabla 1).
Entonces encontraremos máximo elemento de la columna adicional (marcado con un asterisco), este será el precio más bajo del juego.
tabla 1
| Estrategias "B" | |||||||||||||||
| Estrategias "A" | B 1 | B 2 | Mínimos de fila | ||||||||||||
| un 1 | 3 | 5 | 3 * | ||||||||||||
| un 2 | 6 |
|
|
||||||||||||
En nuestro caso, el precio más bajo del juego es: a = 3, y para garantizar una victoria no peor que 3 debemos ceñirnos a la estrategia A 1
Paso 2
Determinemos el precio superior del juego - β
Precio superior del juegoβ es la pérdida mínima que el jugador B puede garantizarse en un juego contra un oponente razonable si utiliza una y sólo una estrategia a lo largo del juego.Busquemos en cada columna de la matriz de pagos. máximo elemento y escríbalo en una línea adicional a continuación (resaltado en amarillo, consulte la Tabla 2).
Entonces encontraremos mínimo elemento de la línea adicional (marcada con un signo más), este será el precio superior del juego.
Tabla 2
| Estrategias "B" | ||||||||||||
| Estrategias "A" | B 1 | B 2 | Mínimos de fila | |||||||||
| un 1 | 3 | 5 | 3 * | |||||||||
| un 2 | 6 |
| En nuestro caso, el precio superior del juego es: b = 5, y para garantizar una pérdida no peor que 5, el oponente (jugador “B”) debe seguir la estrategia B 2 Paso 3 Estrategia mixta, se trata de estrategias puras que se alternan aleatoriamente, con determinadas probabilidades (frecuencias). Denotaremos la estrategia mixta del jugador “A”
|
|||||||||
donde B 1, B 2 son las estrategias del jugador “B”, y q 1, q 2 son, respectivamente, las probabilidades con las que se aplican estas estrategias, y q 1 + q 2 = 1.
La estrategia mixta óptima para el jugador “A” es la que le proporciona el máximo beneficio. En consecuencia, para “B” existe una pérdida mínima. Estas estrategias están designadas S A* y S B* respectivamente. Un par de estrategias óptimas forman una solución al juego.
EN caso general La estrategia óptima del jugador puede no incluir todas las estrategias iniciales, sino sólo algunas de ellas. Este tipo de estrategias se denominan estrategias activas.
Etapa 4
Dónde: pag 1 , pag 2 - probabilidades (frecuencias) con las que se aplican las estrategias A 1 y A 2, respectivamente
De la teoría de juegos se sabe que si el jugador "A" usa su estrategia óptima y el jugador "B" permanece dentro del marco de sus estrategias activas, entonces el pago promedio permanece sin cambios y es igual al costo del juego. v independientemente de cómo el jugador "B" utilice sus estrategias activas. Y en nuestro caso ambas estrategias están activas, de lo contrario el juego tendría solución en estrategias puras. Por lo tanto, si asumimos que el jugador “B” usará una estrategia pura B 1, entonces el pago promedio v será:
k 11 p 1 + k 21 p 2 = v (1)
Dónde: k ij - elementos de la matriz de pagos.
Por otro lado, si suponemos que el jugador “B” utilizará una estrategia pura B 2, entonces el pago promedio será:
k 12 p 1 + k 22 p 2 = v (2)
Igualando los lados izquierdos de las ecuaciones (1) y (2) obtenemos:
k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2
Y teniendo en cuenta el hecho de que pag 1 + pag 2 = 1 tenemos:
k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )
Donde es fácil encontrar la frecuencia óptima de la estrategia A 1:
| pag 1 = |
| (3) |
En esta tarea:
| pag 1 = |
| = |
|
Probabilidad R 2 encontrar por resta R 1 de la unidad:
| pag 2 = 1 - pag 1 = | 1 | - |
| = | + | 6 | · |
Dónde: q 1 , q 2 - probabilidades (frecuencias) con las que se aplican las estrategias B 1 y B 2, respectivamente
Por la teoría de juegos se sabe que si el jugador "B" utiliza su estrategia óptima y el jugador "A" permanece dentro del marco de sus estrategias activas, entonces el pago promedio permanece sin cambios y es igual al costo del juego. v independientemente de cómo el jugador A utilice sus estrategias activas. Por lo tanto, si asumimos que el jugador “A” utilizará una estrategia pura A 1, entonces el pago promedio v será:
k 11 q 1 + k 12 q 2 = v (4)
Desde el precio del juego. v ya lo sabemos y considerando que q 1 + q 2 = 1 , entonces la frecuencia óptima de la estrategia B 1 se puede encontrar como:
| q 1 = |
| (5) |
En esta tarea:
| q 1 = |
| = |
|
Probabilidad q 2 encontrar por resta q 1 de la unidad:
| q 2 = 1 - q 1 = | 1 | - |
| = |
|
Respuesta:
| Precio más bajo del juego: | α = | 3 | |||
| Precio superior del juego: | β = | 5 | |||
| Precio del juego: | v = |
|
| La estrategia óptima del jugador A: |
|
|||||||||||||||
| Estrategia óptima para el jugador "B": |
|
Interpretación geométrica (solución gráfica):
Demos una interpretación geométrica al juego considerado. Tome una sección del eje de abscisas de longitud unitaria y dibuje líneas rectas verticales a través de sus extremos. a 1 Y a 2 correspondiente a nuestras estrategias A 1 y A 2 . Supongamos ahora que el jugador "B" utilizará la estrategia B 1 en forma pura. Entonces, si nosotros (el jugador “A”) usamos una estrategia pura A 1, entonces nuestro pago será 3. Marquemos el punto correspondiente en el eje. a 1 .Si utilizamos la estrategia pura A 2, entonces nuestro pago será 6. Marquemos el punto correspondiente en el eje a 2
(ver figura 1). Obviamente, si aplicamos mezclando las estrategias A 1 y A 2 en diferentes proporciones, nuestras ganancias cambiarán a lo largo de una línea recta que pasa por puntos con coordenadas (0, 3) y (1, 6), llamémosla línea de estrategia B. 1 (en la Fig. 1 se muestra en rojo). La abscisa de cualquier punto de una recta dada es igual a la probabilidad pag 2 (frecuencia) con la que aplicamos la estrategia A 2, y la ordenada - la ganancia resultante k (ver figura 1).
Foto 1.
Gráfico de pagos k
de frecuencia página 2
, cuando el enemigo usa la estrategia B 1.
Supongamos ahora que el jugador “B” utilizará la estrategia B 2 en su forma pura. Entonces, si nosotros (el jugador “A”) usamos la estrategia pura A 1, entonces nuestro pago será 5. Si usamos la estrategia pura A 2, entonces nuestro pago será 3/2 (ver Fig. 2). De manera similar, si mezclamos las estrategias A 1 y A 2 en diferentes proporciones, nuestras ganancias cambiarán a lo largo de una línea recta que pasa por los puntos con coordenadas (0, 5) y (1, 3/2), llamémosla línea de estrategia. B2. Como en el caso anterior, la abscisa de cualquier punto de esta recta es igual a la probabilidad con la que aplicamos la estrategia A 2, y la ordenada es la ganancia resultante, pero solo para la estrategia B 2 (ver Fig. 2).
Figura 2.
v
y frecuencia óptima página 2
para el jugador "A".
En un juego real, cuando un jugador razonable "B" usa todas sus estrategias, nuestras ganancias cambiarán a lo largo de la línea discontinua que se muestra en la Fig. 2 en rojo. Esta línea define la llamada límite inferior de ganancias. Obviamente lo mas punto álgido esta línea discontinua corresponde a nuestra estrategia óptima. EN en este caso, este es el punto de intersección de las líneas de las estrategias B 1 y B 2. Tenga en cuenta que si selecciona una frecuencia pag 2 igual a su abscisa, entonces nuestra ganancia permanecerá sin cambios e igual v para cualquier estrategia del jugador “B”, además, será lo máximo que podamos garantizarnos. Frecuencia (probabilidad) pag 2 , en este caso, es la frecuencia correspondiente de nuestra estrategia mixta óptima. Por cierto, en la Figura 2 puedes ver la frecuencia. pag 1 , nuestra estrategia mixta óptima, es la longitud del segmento [ pag 2 ; 1] en el eje de abscisas. (Eso es porque pag 1 + pag 2 = 1 )
Utilizando un razonamiento completamente similar, podemos encontrar las frecuencias de la estrategia óptima para el jugador "B", que se ilustra en la Figura 3.
Figura 3.
Determinación gráfica del precio del juego. v
y frecuencia óptima q 2
para el jugador "EN".
Sólo para él debería el llamado limite superior perdiendo(línea roja discontinua) y busque el punto más bajo, porque para el jugador "B" el objetivo es minimizar las pérdidas. Mismo valor de frecuencia q 1 , esta es la longitud del segmento [ q 2 ; 1] en el eje x.
Contenido 1 información general 2 1.1 Juegos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Movimientos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Estrategias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Juego de matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Punto del sendero. Estrategias puras 7 2.1 Ejemplos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Ejemplo 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Ejemplo 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Estrategias mixtas 9 3.1 Juego 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Ejemplos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Ejemplo 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Ejemplo 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Interpretación geométrica. . . . . . . . . . . . . . . . . . . . 12 3.2 Juegos 2×n y m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Ejemplo 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Información general de la teoría de juegos 1.1. Juegos La teoría de juegos es una teoría matemática de situaciones de conflicto, es decir. Situaciones en las que chocan los intereses de dos o más partes que persiguen objetivos diferentes. Un juego es una situación de conflicto regulada por determinadas reglas, que deben indicar: posibles opciones para las acciones de los participantes el resultado cuantitativo del juego o pago (ganar, perder) al que conduce un determinado conjunto de movimientos; de cada lado sobre el comportamiento del otro. Un juego de dobles es un juego en el que sólo participan dos equipos (dos jugadores). Un juego emparejado de suma cero es un juego emparejado en el que la suma de los pagos es cero, es decir La pérdida de un jugador es igual a la ganancia del segundo. Dependiendo de la actitud de cada jugador hacia el valor de la función de pago, los juegos emparejados se subdividen: Juego emparejado de suma cero (antagonístico): un juego emparejado en el que la cantidad de pagos es igual a cero, es decir La pérdida de un jugador es igual a la ganancia del segundo. Un juego no antagónico es un juego de parejas en el que los jugadores persiguen objetivos diferentes, pero no directamente opuestos. 2 1.2. Movimientos Movimiento: elección de una de las acciones previstas por las reglas del juego; implementación de esta elección Los movimientos son de dos tipos: Movimiento personal - + elección consciente de una de las acciones previstas por las reglas del juego + implementación. de esta elección Movimiento aleatorio: un movimiento aleatorio es una elección entre varias posibilidades, no realizada por decisión del jugador, sino por algún mecanismo de selección aleatoria. A continuación consideramos juegos emparejados de suma cero que contienen sólo movimientos personales. Cada lado carece de información sobre el comportamiento del otro. 3 1.3. Estrategias La estrategia de un jugador es un conjunto de reglas que determinan la elección de acciones para cada movimiento personal de este jugador, dependiendo de la situación que surge durante el juego. Dependiendo del número de estrategias posibles, los juegos se dividen en finitos e infinitos. Un juego infinito es un juego en el que al menos uno de los jugadores tiene número infinito estrategias. Un juego finito es un juego en el que cada jugador tiene sólo un número finito de estrategias. El número de movimientos consecutivos de cualquier jugador determina la división de las partidas en de un solo movimiento y de múltiples movimientos, o posicionales. + En un juego de un turno, cada jugador elige solo una de las opciones posibles y luego determina el resultado del juego. + El juego de múltiples movimientos o posicional se desarrolla con el tiempo y representa una serie. etapas sucesivas, cada uno de los cuales ocurre después del movimiento de uno de los jugadores y el correspondiente cambio en la situación. En un juego de un turno, cada jugador hace sólo una elección entre opciones posibles y luego determina el resultado del juego. La estrategia óptima de un jugador es aquella que, cuando el juego se repite muchas veces, proporciona a este jugador la máxima ganancia media posible (o, lo que es lo mismo, la mínima pérdida media posible). En la teoría de juegos, todas las recomendaciones se basan en el supuesto de un comportamiento razonable de los jugadores. Los errores de cálculo y los errores de los jugadores, inevitables en toda situación de conflicto, así como los elementos de excitación y riesgo, no se tienen en cuenta en la teoría de juegos. 4 1.4. Juego de matrices Un juego de matrices es un juego finito de suma cero de un movimiento. Un juego de matrices es un juego teórico. modelo de juego Situación de conflicto en la que los oponentes, para lograr objetivos diametralmente opuestos, toman una decisión (movimiento) entre un número finito. formas posibles acciones.De acuerdo con los métodos de acción elegidos (estrategias), se determina el resultado obtenido. Veamos un ejemplo. Sean dos jugadores A y B, uno de los cuales puede elegir i-ésima estrategia de m de sus posibles estrategias A1, A2, ...Am, y el segundo elige la j-ésima estrategia de sus posibles estrategias B1, B2, ...Bm. Como resultado, el primer jugador gana el valor aij y el segundo jugador pierde este valor. A partir de los números aij, creamos una matriz a11 a11 · · · a1n a21 a22 · · · a2n A = (aij) = .. .. .. . . . . am1 am2 · · · amn La matriz A = (aij), i = 1, m, j = 1, n se llama matriz de pagos o matriz de juego m × n. En esta matriz, las filas son siempre para las estrategias del jugador ganador (maximizador) A, es decir, el jugador que se esfuerza por maximizar sus ganancias. Las columnas están asignadas para las estrategias del jugador perdedor B, es decir, el jugador que se esfuerza por minimizar el criterio de eficiencia. La normalización de un juego es el proceso de reducir un juego posicional a un juego matricial. Un juego en forma normal es un juego posicional reducido a un juego matricial. Recordemos que un juego posicional de múltiples movimientos es un modelo teórico de juego. Situación de conflicto en la que los oponentes realizan secuencialmente una elección (movimiento) entre un número finito de posibles cursos de acción en cada etapa del desarrollo de esta situación. La solución del juego es encontrar las estrategias óptimas de ambos jugadores y determinar el precio del juego. El precio del juego es la ganancia (pérdida) esperada de los jugadores. La solución al juego se puede encontrar en estrategias puras, cuando el jugador debe seguir una sola estrategia, o en estrategias mixtas, cuando el jugador debe utilizar dos o más estrategias puras con ciertas probabilidades. Estos últimos en este caso se denominan activos. 5 La estrategia mixta de un jugador es un vector, cada componente del cual muestra la frecuencia de uso por parte del jugador de la estrategia pura correspondiente. Maximin o precio más bajo del juego - número α = max min aij i j Estrategia Maximin (línea) - la estrategia que el jugador eligió para maximizar sus ganancias mínimas. Obviamente, al elegir la estrategia maximin más cautelosa, el jugador A se asegura (independientemente del comportamiento del oponente) un pago garantizado de al menos α. Maximin o precio superior del juego - número β = min max aij j i Estrategia Minimax (columna) - la estrategia que el jugador eligió para minimizar su pérdida máxima. Obviamente, al elegir la estrategia minimax más cautelosa, el jugador B no permite, bajo ninguna circunstancia, que el jugador A gane más que β. El precio más bajo del juego no siempre excede el precio superior del juego α = max min aij 6 min max aij = β i j j i Teorema 1 (el teorema principal de la teoría de los juegos matriciales). Todo juego finito tiene al menos una solución, posiblemente en el ámbito de las estrategias mixtas. 6 2. Juegos con punto de silla. Solución en estrategias puras Un juego con punto silla es un juego en el que α = max min aij = min max aij = β i j j i Para juegos con punto silla, encontrar una solución consiste en elegir las estrategias maximin y minimax que sean óptimas. Costo puro del juego - significado general Precios inferior y superior del juego α=β=ν 2.1. Ejemplos Ejemplo 1 Encontrar una solución en estrategias puras del juego dada por la matriz 8 4 7 A= 6 5 9 7 7 8 Solución: determinar el precio superior e inferior del juego. Para hacer esto, encontramos el mínimo de los números aij en i-ésima línea αi = min aij j y el máximo de los números aij en la j-ésima columna βj = max aij i Escribiremos los números αi (mínimos de fila) junto a la matriz de pago a la derecha en forma de una columna adicional. Escribimos los números βi (columna máxima) debajo de la matriz en forma de una línea adicional: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Encuentra el máximo de los números αi α = max αi = 7 i y el mínimo de los números βj β = min βj = 7 j α = β - el juego tiene un punto de silla. La estrategia óptima para el jugador es la estrategia A3, y para el jugador B es la estrategia B2, precio neto del juego ν = 7 Ejemplo 2 La matriz de pagos está dada: 2 2 1 1 2 0 1 1 1 1 A= 1 1 1 1 2 1 2 1 1 2 Encuentra una solución al juego en estrategias puras. Solución: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. El juego tiene seis puntos silla. Las estrategias óptimas serán: A1 y B3 o B4 A3 y B3 o B4 A4 y B3 o B4 8 3. Solución del juego en estrategias mixtas Cuando α = β. En el caso de que, a la hora de elegir sus estrategias, ambos jugadores no tengan información sobre la elección del otro, el juego tiene solución en estrategias mixtas. SA = (p1, p2, ..., pm) - estrategia mixta del jugador A, en la que las estrategias A1, A2, ..., Am se aplican con probabilidades ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - estrategia mixta del jugador B, en la que las estrategias B1, B2, ..., Bm se aplican con probabilidades ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Si: SA∗ es la estrategia óptima del jugador A, SB∗ es la estrategia óptima del jugador B, entonces El costo del juego es ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 El siguiente teorema responde a la pregunta de cómo encontrar una solución para los juegos 2 × 2, 2 × n, m × 2 Teorema 2 (cómo encontrar una solución para los juegos 2 × 2, 2 × n, m × 2). Si uno de los jugadores usa una estrategia mixta óptima, entonces su pago es igual al costo del juego ν, independientemente de las probabilidades con las que el segundo jugador usará las estrategias incluidas en la óptima (incluidas las estrategias puras). 9 3.1. Juego 2 × 2 Considere un juego 2 × 2 con la matriz: () a11 a21 a21 a22 Dejemos que el juego no tenga solución en estrategias puras. Encontremos las estrategias óptimas SA∗ y SB∗. Primero, definimos la estrategia SA∗ = (p∗1, p∗2). Según el teorema, si el partido A sigue la estrategia ν, independientemente del curso de acción del partido B, el beneficio seguirá siendo igual al coste de jugar ν. En consecuencia, si el lado A se adhiere a la estrategia óptima SA∗ = (p∗1, p∗2), entonces el lado B puede aplicar cualquiera de sus estrategias sin cambiar su pago. Entonces, cuando el jugador B usa la estrategia pura B1 o B2, el jugador recibirá un pago promedio igual al costo del juego: a11 p∗1 + a21 p∗2 = ν ← para la estrategia B1 a12 p∗1 + a22 p∗ 2 = ν ← para la estrategia B2 Teniendo en cuenta tenga en cuenta que p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Precio del juego: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 La estrategia óptima del jugador B se encuentra de manera similar: SB∗ = (q1∗ , q2∗). Teniendo en cuenta que q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Ejemplos Ejemplo 3 Encuentra una solución al juego con matriz () −1 1 A= 1 −1 10 Solución: el juego no tiene punto silla, ya que α= -1, β = 1, α ̸= β. Buscamos una solución en estrategias mixtas. Usando las fórmulas para p∗ y q∗, obtenemos p∗1 = p∗2 = 0.5 y q1∗ = q2∗ = 0.5, ν = 0 Por lo tanto, SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5 ) Ejemplo 4 Encuentra una solución al juego con matriz () 2 5 A= 6 4 Solución: el juego no tiene punto silla, ya que α= 4, β = 5, α ̸= β. Buscamos una solución en estrategias mixtas. Usando las fórmulas para p∗ y q∗, obtenemos p∗1 = 0.4, p∗2 = 0.6 y q1∗ = 0.2 q2∗ = 0.8, ν = 4.4 Por lo tanto, SA∗ = (0.4, 0.6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Interpretación geométrica Al juego 2 × 2 se le puede dar una interpretación geométrica sencilla. Tomemos una sola sección del eje de abscisas, cada punto del cual asociamos con alguna estrategia mixta S = (p1, p2) = (p1, 1 − p1) y la probabilidad p1 de la estrategia A1 será igual a la distancia desde punto SA al extremo derecho de la sección, y la probabilidad p2, estrategia A2 - la distancia al extremo izquierdo. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ En particular, el extremo izquierdo de la sección (punto con abscisas = 0) corresponde a la estrategia A1, extremo derecho del segmento (x = 1) - estrategia A2 En los extremos del segmento, se restablecen dos perpendiculares al eje x: eje I − I - se pospone el pago de la estrategia A1, eje II −; II - se pospone el pago de la estrategia A2. Deje que el jugador B aplique la estrategia B1; da en los ejes I - I y II - II, respectivamente, puntos con ordenadas a11 y a21. Trazamos una recta B1 − B1′ que pasa por estos puntos. Para cualquier estrategia mixta SA = (p1, p2), el pago del jugador está determinado por el punto N en la línea recta B1 − B1′, correspondiente al punto SA en el eje x que divide el segmento en la relación p2: p1. Obviamente, la línea recta B2 − B2′, que determina el resultado de la estrategia B2, se puede construir exactamente de la misma manera. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Es necesario encontrar la estrategia óptima SA∗ , es decir de modo que el pago mínimo del jugador A (dado el peor comportamiento del jugador B) se convertiría en un máximo. Para hacer esto, construya un límite inferior para el pago del jugador A para las estrategias B1, B2, es decir línea discontinua B1 N B2′;. En este límite estará el pago mínimo del jugador A para cualquiera de sus estrategias mixtas, punto N, en el que este pago alcanza un máximo y determina la decisión y el precio del juego. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗S. 1∗ P La ordenada del punto N no es más que el costo del juego ν, su abscisa es igual a ∗2 y la distancia al extremo derecho del segmento es igual a ∗1, es decir la distancia desde el punto SA∗ hasta los extremos del segmento son iguales a las probabilidades ∗2 y ∗1 de las estrategias A2 y A1 de la estrategia mixta óptima del jugador A. en este caso, la solución del juego estuvo determinada por la punto de intersección de las estrategias B1 y B2. A continuación se muestra un caso en el que la estrategia óptima del jugador es la estrategia pura A2. Aquí la estrategia A2 (para cualquier estrategia enemiga) es más rentable que la estrategia A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1 ′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .yo . .X. 2∗P. A∗S = A2. 2∗P. A∗ S = A2 A la derecha se muestra el caso en el que el jugador B tiene una estrategia obviamente no rentable. La interpretación geométrica también permite visualizar el precio inferior del juego α y el precio superior β .y .I .I I .B2. .B1′ .N .B1 . B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗S. 1∗ P En el mismo gráfico, también podemos dar una interpretación geométrica de las estrategias óptimas del jugador B. Es fácil verificar que la proporción q1∗ de la estrategia B1 de la estrategia mixta óptima SB∗ = (q1∗, q2∗) es igual a la relación entre la longitud del segmento KB2 y la suma de las longitudes de los segmentos KB1. y KB2 en el eje I − I: .y .I .I I .B2 .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗S. 1∗ P 14 KB2 q1∗ = KB2 + KB1 o LB2′ q1∗ = LB2′ + LB1′ La estrategia óptima SB∗ = (q1∗ , q2∗) se puede encontrar de otra forma, si intercambiamos jugadores B y B, y en lugar del máximo del límite inferior de ganancias, considere el mínimo del límite superior. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Juegos de 2 × n y m × 2 La solución de los juegos de 2 × n y m × 2 se basa en el siguiente teorema. Teorema 3. Cualquier juego finito m × n tiene una solución en la que el número de estrategias activas de cada lado no excede el menor de los números my n. Según este teorema, un juego 2 × n siempre tiene una solución en la que cada jugador tiene como máximo dos estrategias activas. Una vez encontradas estas estrategias, el juego 2×n se convierte en un juego 2×2, que se puede resolver de forma elemental. La búsqueda de estrategias activas se puede hacer gráficamente: 1) se construye una interpretación gráfica; 2) se determina el límite inferior de ganancias; 3) se identifican dos estrategias del segundo jugador en el límite inferior del pago, que corresponden a dos líneas que se cruzan en el punto con la ordenada máxima (si se cruzan más de dos líneas en este punto, se toma cualquier par): estas estrategias representan las estrategias activas del jugador B. Así, el juego 2 × n se reduce al juego 2 × 2. El juego m × 2 también se puede resolver, con la diferencia de que no es el límite inferior, sino el superior, del pago. construye, y no el máximo, sino que en él se busca el mínimo. Ejemplo 5 Encuentra una solución al juego () 7 9 8 A= 10 6 9 Solución: usando el método geométrico, seleccionamos estrategias activas. Las líneas directas B1 − B1′, B2 − B2′ y B3 − B3′ corresponden a las estrategias B1, B2, B3. La línea discontinua B1 N B2 es el límite inferior de las ganancias del jugador. El juego tiene solución S∗A = (23, 31); S∗B = (0,5; 0,5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X. 2∗P. A∗S. 1∗ P 17 Juego índice, 2 movimiento, 3 2 × 2, 10 personal, 3 2 × 2, 9 aleatorio, 3 geometría, 12 precio neto del juego, 7 ejemplos, 10 2 × n, 9, 16 m × 2, 9 , 16 infinito, 4 en forma normal, 5 finito, 4 de movimiento múltiple, 4 de un movimiento, 4 matricial, 5 emparejado, 2 de suma cero, 2 antagónicos, 2 no antagonistas, 2 de solución, 5 en estrategias mixtas, 5 , 9 en estrategias puras, 5 con punto de silla, 7 precio, 5 superior, 6 inferior, 6 puro, 7 maximin, 6 matriz de juego, 5 pago, 5 minimax, 6 normalización de juego, 5 estrategia, 4 maximin, 6 minimax, 6 óptimo, 4 mixto, 5 teoría de juegos, 2 18
Del popular blog estadounidense Cracked.
La teoría de juegos consiste en estudiar formas de hacer el mejor movimiento y, como resultado, obtener la mayor parte posible del pastel ganador cortándole parte a otros jugadores. Te enseña a analizar muchos factores y sacar conclusiones lógicamente equilibradas. Creo que debería estudiarse después de los números y antes del alfabeto. Simplemente porque demasiadas personas toman decisiones importantes basándose en la intuición, profecías secretas, la ubicación de las estrellas y cosas por el estilo. He estudiado a fondo la teoría de juegos y ahora quiero contarles sus conceptos básicos. Quizás esto agregue algo de sentido común a su vida.
1. El dilema del prisionero
Berto y Robert fueron arrestados por robo a un banco después de no utilizar correctamente un coche robado para escapar. La policía no puede demostrar que fueron ellos quienes robaron el banco, pero los pillaron con las manos en la masa en un coche robado. Los llevaron a diferentes habitaciones y a cada uno le ofrecieron un trato: entregar a un cómplice y enviarlo a prisión por 10 años, y él mismo quedar en libertad. Pero si ambos se traicionan, cada uno recibirá 7 años. Si nadie dice nada, ambos irán a prisión durante 2 años sólo por robo de coche.
Resulta que si Berto permanece en silencio, pero Robert lo entrega, Berto irá a prisión por 10 años y Robert quedará libre. Cada prisionero es un jugador, y el beneficio de cada uno puede expresarse como una "fórmula" (lo que obtienen ambos, lo que obtiene el otro). Por ejemplo, si te golpeo, mi patrón ganador se vería así (obtengo una victoria grosera, tú sufres dolor severo). Como cada prisionero tiene dos opciones, podemos presentar los resultados en una tabla.
Aplicación práctica: identificación de sociópatas
Aquí vemos la principal aplicación de la teoría de juegos: Identificar sociópatas que sólo piensan en sí mismos. La verdadera teoría de juegos es una poderosa herramienta analítica, y el amateurismo a menudo sirve como una señal de alerta que alerta a alguien que no tiene sentido del honor. Las personas que hacen cálculos intuitivos creen que es mejor hacer algo feo porque resultará en una sentencia de prisión más corta independientemente de lo que haga el otro jugador. Técnicamente esto es correcto, pero sólo si eres una persona miope que pone los números más altos. vidas humanas. Por eso la teoría de juegos es tan popular en las finanzas.
El verdadero problema del dilema del prisionero es que ignora los datos. Por ejemplo, no considera la posibilidad de que te reúnas con amigos, familiares o incluso acreedores de la persona a la que enviaste a prisión durante 10 años.
La peor parte es que todos los involucrados en el Dilema del Prisionero actúan como si nunca hubieran oído hablar de él.
Y lo mejor es guardar silencio y, después de dos años, junto con un buen amigo, utilizar el mismo dinero.
2. Estrategia dominante
Esta es una situación en la que tus acciones dan mayor victoria, independientemente de las acciones del oponente. Pase lo que pase, hiciste todo bien. Es por eso que muchas personas con el dilema del prisionero creen que la traición conduce al "mejor" resultado independientemente de lo que haga la otra persona, y la ignorancia de la realidad inherente a este método hace que parezca súper fácil.
La mayoría de los juegos que jugamos no tienen estrategias estrictamente dominantes porque, de lo contrario, serían terribles. Imagínate si siempre hicieras lo mismo. No existe una estrategia dominante en el juego de piedra, papel o tijera. Pero si estuvieras jugando con una persona que tuviera guantes de cocina y solo pudiera mostrar piedra o papel, tendrías una estrategia dominante: el papel. Tu papel envolverá su piedra o resultará en un empate, y no puedes perder porque tu oponente no puede mostrar las tijeras. Ahora que tienes una estrategia dominante, serías un tonto si intentaras algo diferente.
3. Batalla de sexos
Los juegos son más interesantes cuando no tienen una estrategia estrictamente dominante. Por ejemplo, la batalla de los sexos. Anjali y Borislav tienen una cita, pero no pueden elegir entre ballet y boxeo. A Anjali le encanta el boxeo porque le gusta ver fluir la sangre para el deleite de una multitud de espectadores que gritan y se consideran civilizados sólo porque pagaron para que le rompieran la cabeza a alguien.
Borislav quiere ver ballet porque entiende por lo que pasan las bailarinas. gran cantidad lesiones y los entrenamientos más duros, sabiendo que una lesión puede acabar con todo. Bailarines de ballet - mejores atletas en el piso. Una bailarina puede darte una patada en la cabeza, pero nunca lo hará, porque su pierna vale mucho más que tu cara.
Cada uno de ellos quiere ir a su evento favorito, pero no quiere disfrutarlo solo, así que así es como ganan: valor más alto- hacer lo que quieran, valor más pequeño- simplemente estar con otra persona y cero - estar solo.
Algunas personas sugieren una actitud terca y arriesgada: si haces lo que quieres pase lo que pase, la otra persona debe conformarse con tu elección o perderlo todo. Como ya dije, La teoría de juegos simplificada es excelente para identificar tontos.
Aplicación práctica: Evite las esquinas afiladas
Por supuesto, esta estrategia también tiene sus importantes inconvenientes. En primer lugar, si tratas tus citas como una "batalla de sexos", no funcionará. Sepárense para que cada uno pueda encontrar a alguien que le guste. Y el segundo problema es que en esta situación los participantes están tan inseguros de sí mismos que no pueden hacerlo.
La estrategia verdaderamente ganadora para todos es hacer lo que quieran. y después, o al día siguiente, cuando estén libres, vayan juntos a un café. O alternar entre el boxeo y el ballet hasta que se produce una revolución en el mundo del espectáculo y se inventa el ballet de boxeo.
4. Equilibrio de Nash
Un equilibrio de Nash es un conjunto de movimientos en los que nadie quiere hacer nada diferente después del hecho. Y si podemos hacer que funcione, la teoría de juegos reemplazará todo el sistema filosófico, religioso y financiero del planeta, porque la "voluntad de no arruinarse" se ha vuelto más poderosa para la humanidad. fuerza motriz que el fuego.
Dividamos rápidamente $100. Tú y yo decidimos cuántos de los cientos necesitamos y al mismo tiempo anunciamos las cantidades. Si nuestro cantidad total menos de cien, todos obtienen lo que querían. Si total más de cien, el que pidió menos cantidad obtiene la cantidad deseada, y el más codicioso se queda con lo que queda. Si pedimos la misma cantidad, todos recibirán $50. ¿Cuánto pedirás? ¿Cómo dividirás el dinero? Sólo hay un movimiento ganador.
Reclamando $51 obtendrás cantidad máxima no importa lo que elija tu oponente. Si pide más, recibirás $51. Si te pide $50 o $51, recibirás $50. Y si te pide menos de $50, recibirás $51. De cualquier manera, no hay otra opción que le permita ganar más dinero que ésta. Equilibrio de Nash: situación en la que ambos elegimos 51 dólares.
Aplicación práctica: pensar primero
Este es el objetivo de la teoría de juegos. No tienes que ganar, y mucho menos dañar a otros jugadores, pero sí tienes que hacer el mejor movimiento para ti, independientemente de lo que te tengan reservado los que te rodean. Y es aún mejor si este movimiento resulta beneficioso para otros jugadores. Este es el tipo de matemáticas que podrían cambiar la sociedad.
Una variación interesante de esta idea es la bebida, que puede denominarse equilibrio de Nash dependiente del tiempo. Cuando bebes lo suficiente, no te importan las acciones de otras personas sin importar lo que hagan, pero al día siguiente realmente te arrepientes de no haber hecho algo diferente.
5. Juego de lanzamiento
El sorteo se juega entre el jugador 1 y el jugador 2. Cada jugador elige simultáneamente cara o cruz. Si adivinan correctamente, el jugador 1 recibe el centavo del jugador 2. Si no, el jugador 2 recibe la moneda del jugador 1.
La matriz ganadora es simple...
...estrategia óptima: jugar completamente al azar. Es más difícil de lo que piensas porque la selección tiene que ser completamente aleatoria. Si tienes preferencia por cara o cruz, tu oponente puede usarlo para tomar tu dinero.
Por supuesto, el verdadero problema aquí es que sería mucho mejor si se tiraran un centavo el uno al otro. Como resultado, sus ganancias serían las mismas y el trauma resultante podría ayudar a estas desafortunadas personas a sentir algo más que un terrible aburrimiento. Despues de todo esto peor juego siempre existente. Y este es el modelo ideal para una tanda de penaltis.
Aplicación práctica: Penalización
En el fútbol, el hockey y muchos otros juegos, la prórroga es una tanda de penaltis. Y serían más interesantes si se basaran en cuántas veces los jugadores forma completa Sería capaz de hacer una voltereta porque al menos sería una indicación de su capacidad física y sería divertido de ver. Los porteros no pueden determinar claramente el movimiento de una pelota o un disco desde el comienzo de su movimiento porque, desafortunadamente, los robots todavía no participan en nuestras competiciones deportivas. El portero debe elegir la dirección izquierda o derecha y esperar que su elección coincida con la elección del oponente que dispara a portería. Esto tiene algo en común con jugar con monedas.
Sin embargo, tenga en cuenta que este no es un ejemplo perfecto de la similitud con el juego de cara y cruz, porque incluso si tomando la decisión correcta dirección, el portero no podrá atrapar el balón y el atacante no podrá golpear la portería.
Entonces, ¿cuál es nuestra conclusión según la teoría de juegos? Los juegos de pelota deben terminar en una forma de "bolas múltiples", donde cada minuto a los jugadores uno a uno se les da una pelota/disco adicional hasta que un lado logre un resultado determinado, lo cual es una indicación de la verdadera habilidad de los jugadores, y No es una coincidencia aleatoria espectacular.
Al fin y al cabo, la teoría de juegos debería utilizarse para hacer que el juego sea más inteligente. Lo que significa que es mejor.
Teoría de juego Como rama de la investigación de operaciones, es la teoría de modelos matemáticos para la toma de decisiones óptimas en condiciones de incertidumbre o conflicto de varias partes con diferentes intereses. La teoría de juegos estudia las estrategias óptimas en situaciones de juego. Estos incluyen situaciones relacionadas con la elección de las soluciones de producción más rentables para un sistema de experimentos científicos y económicos, la organización control estadístico, relaciones económicas entre empresas industriales y otros sectores. Formalizando situaciones de conflicto matemáticamente se pueden representar como un juego de dos, tres, etc. jugadores, cada uno de los cuales persigue el objetivo de maximizar su beneficio, sus ganancias a expensas del otro.La sección "Teoría de juegos" está representada por tres calculadoras en línea:
- Estrategias óptimas para el jugador. En tales problemas, se especifica una matriz de pago. Se requiere encontrar estrategias puras o mixtas de los jugadores y, precio del juego. Para resolver, debes especificar la dimensión de la matriz y el método de solución. El servicio implementa siguientes métodos Soluciones para un juego de dos jugadores:
- Minimáx. Si necesita encontrar la estrategia pura de los jugadores o responder una pregunta sobre el punto de partida de un juego, elija este método de solución.
- Método simplex. Se utiliza para resolver juegos de estrategia mixta utilizando métodos de programación lineal.
- Método gráfico. Se utiliza para resolver juegos de estrategia mixta. Si hay un punto de silla, la solución se detiene. Ejemplo: para una matriz de pago determinada, encuentre las estrategias mixtas óptimas de los jugadores y el precio del juego usando método gráfico soluciones de juego.
- Método iterativo de Brown-Robinson. El método iterativo se utiliza cuando el método gráfico no es aplicable y cuando los métodos algebraico y métodos matriciales. Este método proporciona un valor aproximado del precio del juego y el valor real se puede obtener con cualquier grado de precisión deseado. Este método no es suficiente para encontrar estrategias óptimas, pero permite seguir la dinámica de un juego por turnos y determinar el coste del juego para cada jugador en cada paso.
Todos los métodos utilizan una verificación de filas y columnas dominantes. - Juego bimatriz. Por lo general, en un juego de este tipo se especifican dos matrices del mismo tamaño de pagos del primer y segundo jugador. Las filas de estas matrices corresponden a las estrategias del primer jugador y las columnas de las matrices corresponden a las estrategias del segundo jugador. En este caso, la primera matriz representa las ganancias del primer jugador y la segunda matriz representa las ganancias del segundo.
- Juegos con la naturaleza. Se utiliza cuando es necesario seleccionar decisión de gestión según los criterios de Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
Para el criterio de Bayes, también será necesario ingresar las probabilidades de que ocurran los eventos. Si no se especifican, dejar los valores predeterminados (habrá eventos equivalentes).
Para el criterio de Hurwitz, indique el nivel de optimismo λ. Si este parámetro no está especificado en las condiciones, puede utilizar los valores 0, 0,5 y 1.
Muchos problemas requieren encontrar soluciones utilizando computadoras. Los servicios y funciones anteriores son una de las herramientas.
