&8 What we saw in Part A is that for every mixed strategy one player selects, the other player can respond with an appropriate pure counterstrategy in order to maximize its gain. So, for every mixed strategy you try, your opponent (call him Darth) has an optimal pure counter-strategy. If you take a "paranoid" position and assume that, no matter what mixed strategy you use, Darth will use his optimal counterstrategy to harm you the most, it is obviously in your interest to select a mixed strategy that minimizes the effect of Darth's optimal counterstrategy. This is called the minimax criterion. Finding each player's optimal mixed strategy using the minimax criterion is also called solving the game. Lo que vimos en Parte A es que para cada estrategia mixta que escoge un jugador, el otro jugador puede responder con una apropiada estrategia pura para maximizar su ganacia. Así, para cada estrategia mixta que pruebas, tiene tu contrincante (lo llamemos Darth) tiene una contraestrategia óptima pura. Si tomas el punto de vista "paranoico" y suponer que, sea cual estrategia uses tú, Darth va a usará su contraestrategia mejor para hacerte lo más daño, y entonces es en tu interés excoger una estrategia mixtra que minimiza el efecto de la estrategia óptima de Darth. Esto se llama el criterio minimax. Hallar la estrategia óptima mixta por usar el criterio minimax se llama también solucionar el juego.
Minimax criterion
Criterio minimax
A player using the minimax criterion chooses a (mixed) strategy that, among all possible strategies, minimizes the negative effect of the other player's best counterstrategy. That is, an optimal (best) strategy according to the minimax criterion is one that minimizes the maximum damage the opponent can cause.
This criterion assumes that your opponent is determined to win. More precisely, it assumes the following:
Un jugador quien usa el criterio minimax escoge una estrategia (mixta) que, entre todas las estrategias posibles, minimiza el efecto negativo de la contraestrategia mejor del otro jugador. Es decir, una estrategia óptima según el criterio minimax es aquella que minimza el daño máximo que puede hacer el contrincante.
Este criterio presupone que tu contrincante está decidido a ganar. Más precisamente, presupone el siguiente:
Fundamental principle of game theory
Principios fundamentale de la teoría de juegos
|
Reducing a game by dominance Reducir un juego por predominio
In some cases we use the fundamental principle to reduce a given game to one with a smaller payoff matrix, and sometimes even solve it that way. Reducing a game to one with a smaller payoff matrix is called reduction by dominance. To best understand how reduction by dominance works, let us go back to the football scenario we studied in Part A:You are the head football coach of the &9, and are attempting to come up with a strategy to deal with your rivals, the Betas. The &9 are on offense, and the Betas on defense. You have five preferred plays, and you know that the Betas usually employ one of three defensive plays. Over the years, you have recorded the yardage gained by your team for each combination of plays used, and have come up with the following payoff matrix (negative numbers denote yardage lost): (Note: The payoffs here are different from those in the preceding tutorial.) En algunos casos, usamos el principio fundamental para reducir un juego a uno con una matriz de pagos más pequeña, y a veces solucionarlo así. Reducir un juego a uno con una matriz de pagos más pequeña se llama reducir por predominio. Para entender lo mejor como funcione reducción por predominio, volvamos al escenario que estudiamos en Parte A:
Eres el entrenador en jefe del equipo futbol americano, los &9, y estás intentando desarrollar una estrategia para usar contra tus contrincantes, los Betas. Los &9 están al ataque y los Betas a la defensa. Tienes cinco jugadas ofensivas preferidas, y sabes que los Betas suelen escoger entre tres jugadas defensivas. A lo largo de loa años, has recordado el yardaje (número de yardas) ganado por tu equipo con cada combincación de jugadas usadas, y has construido la siguiente matriz de pagos (números negativos denotan yardas perdidas): (Nota: Los pagos son distintos aquí de los del tutorial anterior.)
If you, as the &9 coach, compare offensive plays O1 and O2, then why in your right mind would you ever use play O1? No matter what defensive play the Betas use, the payoff for the &9 is always as high or higher if you use O2: Si, como entrenador de los &9, comparas jugadas ofensivas O1 y O2, entonces ¿porqué en tu cabales sentidos, se te ocurriría jugar O1? Sin importar cual jugada usa los Betas, el pago para tu equipo si usas O2 es siempre mayor o igual a lo de O1:
Why? Because:
- If the Betas play D1, then 7 yards beats 6 yards.
- If the Betas play D2, then a loss of 3 yards beats a loss of 5 yards.
- If the Betas play D3, there is no difference.
¿Por qué? Porque:
- Si juegan los Betas D1, entonces 7 yardas vence 6 yardas.
- Si juegan los Betas D2, una perdida de 3 yardas vence una perdida de 5 yardas
- Si juegan los Betas D3, no hay diferencia.
|
→ |
Reduction by dominance
Reducción por predominio
One row dominates another if each of its entries is greater than or equal to the corresponding entry in the other row. Put another way, one row dominates another if it is always at least as good for the row player.
One column dominates another if e each of its entries is less than or equal to the corresponding entry in the latter. Put another way, one column dominates another if it is always at least as good for the column player.
Procedure for reducing by dominance:
|
Here again is the (reduced) payoff matrix we are working with: Aquí de nuevo es la matriz (reducida) con la que estamos trabajando:
It follows from the principle of game theory that, as the &9' coach, you must eliminate any additional dominated rows, meaning that you are reduced to the following smaller game: Sigue por el principio del teoría de juegos que, como entrenador de los &9, debes eliminar cada adicional renglón dominado. Esto significa que te queda el siguiente juego más pequeño:
→ |
-
The reduced payoff matrix will not appear until you have correctly answered the preceding question.
La matriz reducida de pagos no aparecerá hasta que has contestado correctamente la pregunta anterior.
→ |
-
The reduced payoff matrix will not appear until you have correctly answered all the preceding questions.
La matriz reducida de pagos no aparecerá hasta que has contestado correctamente todas las preguntas anteriores.
&8 Wrong. Remember that you know that the Betas coach will be eliminating that defense play (by the principle of game theory) so now both of you are dealing with this same 2×2 payoff matrix shown above. If you look at this last matrix, you may notice that one row now dominates the other. Incorrecto. Recuerda que sabes que el entrenador de los Betas está eliminando aquella jugada defensiva (por el principio del teoría de juegos) así que ustedes dos están tratando con la misma 2×2 matriz de pagos mostrada más arriba. Si miras esta matriz, tal vez de darás cuenta de que un renglón domina a una otra, So now we are left with the following even smaller payoff matrix: Así nos queda la siguienta matriz aun más pequeño de pagos:
The reduced payoff matrix will not appear until you have correctly answered all the preceding questions.
La matriz reducida de pagos no aparecerá hasta que has contestado correctamente todas las preguntas anteriores.
The reduced payoff matrix will not appear until you have correctly answered all the preceding questions.
La matriz reducida de pagos no aparecerá hasta que has contestado correctamente todas las preguntas anteriores.
&8 Wrong. Not every game reduces by dominance to a 1×1 game; you may reach a point where there are no longer any dominated rows or columns to eliminate. For example, the rock, paper, scissors game does not reduce at all: Incorrecto. No todos los juegos se reducen por dominio a un juego 1×1; puedes llegar a un punto cuando no quedan ningúnos renglones o columnas dominadas para eliminar. Por ejemplo, el juego piedra, papel, tijeras no se reduce en absoluto:
$P = $ | ||||||
Saddle points and strictly determined games Puntos de silla y juegos estrictamente determinados
When a game does not reduce by dominance to a 1×1 game, solving the game (finding the optimal row and column strategies) may require considerable additional work; see part C of this tutorial. However, there are special kinds of game that can be solved very easily: The so-called strictly determined games. Cuando un juego no se reduce por dominio a un juego 1×1, solucionarlo (es decir, hallar las estrategias óptimas para los dos jugadores) puede necesita bastante trabajo adicional. Sin embargo, hay específicos tipos de juego que se puede solucionar fácilmente: Los así llamados juegos estrictamente determinados.Saddle point; strictly determined game Punto de silla; juego estrictamente determinado A saddle point is a payoff that is simultaneously the lowest entry in its row (row minimum) and the greatest entry in its column (column maximum). If a game has at least one saddle point, the corresponding pure row and column strategies are the optimal ones, and we say that the game is strictly determined. Un punto de silla es un pago que es simultáneamente la menor entrada de su renglón (un mímimo de renglón) y la mayor entrada de su columna (un máximo de columna). Un juego es estrictamente determinado si tiene por lo menos uno punto de silla, y las estrategias puras correspondientes son los estrategias óptimas para los dos jugadores. |
&2
Suppose that a game has payoff matrix
Supongamos que un juego tiene matriz de pagos
$P = \mat[4]{\[2 , -2 , -5 , 1\]!4, -2, -3, -3!0 , -1 , 2, 3}. $
First, we highlight the minimum payoff(s) in each row:
Primero, marcamos el pago mínimo (o los pagos mínimos) de cada renglón:
$ \mat[4]{\[2 , -2 , -5 , 1\]!4, -2 , -3 , -3 !0 , -1 , 2, 3}. $
Next, we box the highest payoff(s) in each column:
Luego, ponemos en caja el pago máximo (o los pagos máximos) de cada columna:
$ \mat[4]{\[2 , -2 , -5 , 1\]! 4 , -2 , -3 , -3 !0 , -1 , 2 , 3 }. $
Any payoff that is both highlighted and boxed is a saddle point. In this case, the (only) saddle point is the (3, 2) entry −1, meaning that the optimal strategy for the row player is move #3, and the optimal strategy for the column player is move #2, giving a payoff of −1, called the value of the game. If you are one of the players and use a strategy that includes other moves, then there is a counterstrategy your opponent can use to worsen the outcome for you.
Because the value of the game is −1, we say that the game is biased in favor of the column player. (Had the value of the game been zero, we would have said that the game is fair.) Cualquier pago que está marcado y también en caja es entonces un punto de silla. En este caso, el (único) punto de silla es la entrada (3, 2) −1, que significa que la óptima estrategia para el jugador renglón es acción #3, y la óptima estrategia para el jugador columna es acción #2, resultando en un pago esperado de −1, llamado el valor del juego. Si eres uno de los jugadores y utilices un estrategia que incluya otras acciones, entonces hay una contraestrategia que se puede utilizar tu contrincante para empero el resultado para ti. Ya que el valor del juego es −1, decimos que el juego es parcial a favor del jugador columna. (Si hubiera sido cero el valor del juego, hubiéramos dicho que el juego es justo.) |