2.2: Estrategias Dominadas
- Page ID
- 107925
Recordemos que en un juego de suma cero, sabemos que la victoria de un jugador es la pérdida del otro jugador. Además, sabemos que podemos reescribir cualquier juego de suma cero para que las ganancias del jugador estén en la forma\((a, -a)\text{.}\) Nota, esto funciona aunque\(a\) sea negativo; en cuyo caso,\(-a\) es positivo.
Considera el juego de suma cero con matriz de pago en la Tabla\(2.2.1\). Tenga en cuenta que para simplificar nuestra matriz de pago contiene solo los premios y no los nombres de la estrategia; pero el Jugador 1 todavía elige una fila y el Jugador 2 aún elige una columna.
| Tabla\(2.2.1\): La matriz de pago por ejemplo\(2.2.1\) | ||
|---|---|---|
| \ (2.2.1\): La matriz de pago por ejemplo\(2.2.1\) “> | Jugador 2 | |
| \ (2.2.1\): La matriz de pago por ejemplo\(2.2.1\) "rowspan="2">Jugador 1 | \((1, -1)\) | \((-0, 0)\) |
| \((-1, 1)\) | \((-2, 2)\) | |
Si sabemos que estamos jugando un juego de suma cero, entonces el uso de pares ordenados parece algo redundante: Si el Jugador 1 gana\(1\), entonces sabemos que el Jugador 2 debe perder\(1\) (ganar\(-1\)). Así, si SABEMOS que estamos jugando un juego de suma cero, podemos simplificar nuestra notación simplemente usando los beneficios del Jugador 1. La matriz anterior en Tabla\(2.2.2\) puede simplificarse como en Tabla\(2.2.2\).
| Tabla\(2.2.2\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 1. | ||
|---|---|---|
| \ (2.2.2\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 1. “> | Jugador 2 | |
| \ (2.2.2\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 1.” rowspan="2">Jugador 1 | \(1\) | \(0\) |
| \(-1\) | \(-2\) | |
Al simplificar, tenga en cuenta algunas cosas:
- DEBES saber que el juego es de suma cero.
- Si no se especifica lo contrario, los beneficios representan los beneficios del Jugador 1.
- Siempre puedes dar una matriz similar que represente los beneficios del Jugador 2. No obstante, debido a (2), debes indicar que la matriz es para el Jugador 2. Por ejemplo, la matriz de pago del Jugador 2 estaría dada por Table\(2.2.3\).
Tabla\(2.2.3\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 2. \ (2.2.3\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 2. “> Jugador 2 \ (2.2.3\): La matriz de pago por ejemplo\(2.2.1\) usando solo los beneficios del jugador 2.” rowspan="2">Jugador 1 \(-1\) \(0\) \(1\) \(2\) - Ambos jugadores pueden tomar decisiones de estrategia considerando solo la matriz de pago del Jugador 1. (¿Por qué?) Solo para probar esto, al mirar solo la matriz en la Tabla 2.2.3 determinar qué estrategia debe elegir cada jugador.
Tabla\(2.2.4\): Los beneficios del jugador 1 en el Ejemplo\(2.2.1\). \ (2.2.4\): Los beneficios del jugador 1 en el Ejemplo\(2.2.1\). “> Jugador 2 \ (2.2.4\): Los beneficios del jugador 1 en el ejemplo\(2.2.1\).” rowspan="2">Jugador 1 \(1\) \(0\) \(-1\) \(-2\)
En este último ejemplo, debería quedar claro que el Jugador 1 está buscando filas que le den la mayor rentabilidad. Esto no es nada nuevo. Sin embargo, el Jugador 2 ahora está buscando columnas que le den al Jugador 1 la recompensa MÁS PEQUEÑA. (¿Por qué?)
Ahora que hemos simplificado nuestra notación para juegos de suma cero, intentemos encontrar la manera de determinar la mejor estrategia para cada jugador.
Considera el juego de suma cero dado en la Tabla\(2.2.5\).
| Tabla\(2.2.5\): Matriz de pago por ejemplo\(2.2.2\). | |||
|---|---|---|---|
| \ (2.2.5\): Matriz de pago por ejemplo\(2.2.2\). “> | Jugador 2 | ||
| \ (2.2.5\): Matriz de pago por ejemplo\(2.2.2\).” rowspan="2">Jugador 1 | \(1\) | \(0\) | \(2\) |
| \(-1\) | \(-2\) | \(2\) | |
Determina qué fila debe elegir el Jugador 1. ¿Hay alguna situación en la que el Jugador 1 elegiría la otra fila?
Considera el juego de suma cero dado en la Tabla\(2.2.6\).
| Tabla\(2.2.6\): Matriz de pago por ejemplo\(2.2.3\). | |||
|---|---|---|---|
| \ (2.2.6\): Matriz de pago por ejemplo\(2.2.3\). “> | Jugador 2 | ||
| \ (2.2.6\): Matriz de pago por ejemplo\(2.2.3\).” rowspan="2">Jugador 1 | \(1\) | \(0\) | \(2\) |
| \(-1\) | \(-2\) | \(3\) | |
Determina qué fila debe elegir el Jugador 1. ¿Hay alguna situación en la que el Jugador 1 elegiría la otra fila?
En Ejemplo\(2.2.2\), no importa lo que haga el Jugador 2, el Jugador 1 siempre elegiría la Fila 1, ya que cada pago en la Fila 1 es mayor o igual que el pago correspondiente en la Fila 2 (\(1\ge -1\text{,}\)\(0\ge -2\text{,}\)\(2\ge 2\)). En Ejemplo\(2.2.3\), este no es el caso: si el Jugador 2 eligiera la Columna 3, entonces el Jugador 1 preferiría la Fila 2. En Ejemplo\(2.2.2\) diríamos que la Fila 1 domina la Fila 2.
Una estrategia\(X\) domina una estrategia\(Y\) si cada entrada para\(X\) es mayor o igual a la entrada correspondiente para\(Y\text{.}\) En este caso, decimos que\(Y\) está dominada por\(X\text{.}\)
Si la estrategia\(X\) domina la estrategia\(Y\text{,}\) podemos escribir\(X\succ Y\text{.}\)
En notación matemática, deja\(a_{ik}\) ser el valor en la\(i^{ \text{th}}\) fila y\(k^{ \text{th}}\) columna. Del mismo modo,\(a_{jk}\) es el valor en la\(j^{ \text{th}}\) fila y\(k^{ th}\) columna. La\(i^{ \text{th}}\) fila domina la\(j^{ \text{th}}\) fila si\(a_{ik}\ge a_{jk}\) para todos\(k\text{,}\) y\(a_{ik}> a_{jk}\) para al menos una\(k\text{.}\)
Esta definición también se puede utilizar para el Jugador 2: consideramos columnas en lugar de filas. Si estamos viendo los beneficios del Jugador 1, entonces el Jugador 2 prefiere los beneficios más pequeños. Así, una columna\(X\) domina otra columna\(Y\) si todas las entradas en\(X\) son menores o iguales a las entradas correspondientes en\(Y\text{.}\)
Aquí está lo genial: ¡siempre podemos eliminar estrategias dominadas! (¿Por qué?) Así, en Ejemplo\(2.2.2\), podemos eliminar la Fila 2, como en la Figura\(2.2.1\).
Ahora es fácil ver qué debe hacer el Jugador 2.
En Ejemplo\(2.2.3\), no podemos eliminar la Fila 2 ya que no está dominada por la Fila 1. No obstante, debe quedar claro que la Columna 2 domina la Columna 3 (recuerde, el Jugador 2 prefiere valores MENORES). Así podemos eliminar la Columna 3 como en la Figura\(2.2.2\).
DESPUÉS de eliminar Columna 3, la Fila 1 domina la Fila 2. Ahora, en Figura\(2.2.3\) podemos eliminar la Fila 2.
Nuevamente, ahora es fácil determinar qué debe hacer cada jugador.
Comprobar que los pares de estrategia que determinamos en Ejemplo\(2.2.2\) y Ejemplo\(2.2.3\) son, de hecho, pares de equilibrio.
Ahora, mire hacia atrás a los ejemplos electorales de la Sección 2.1.1 y aplique el proceso de eliminación de estrategias dominadas.
Usa la idea de eliminar estrategias dominadas para determinar qué debe hacer cada jugador en los ejemplos de Arnold/Bainbridge en Tabla\(2.1.4\)\(2.1.5\), Tabla y Tabla\(2.1.6\). ¿Obtienes los mismos pares de estrategia que determinaste en los ejercicios relacionados (Ejercicio\(2.1.1\), Ejercicio\(2.1.2\), Ejercicio\(2.1.3\))?
Los siguientes tres ejercicios proporcionan más práctica en el uso de estrategias dominadas para encontrar pares de equilibrio.
Usa la idea de eliminar estrategias dominadas para determinar cualquier par de equilibrio en el juego de suma cero dado en la Tabla\(2.2.7\). Tenga en cuenta que como es un juego de suma cero solo necesitamos mostrar los beneficios del Jugador 1. Explica todos los pasos en tu solución. Si no puedes encontrar un par de equilibrio, explica qué sale mal.
| Tabla\(2.2.7\): Matriz de pago para ejercicio\(2.2.3\). | |||||
|---|---|---|---|---|---|
| \ (2.2.7\): Matriz de pago para ejercicio\(2.2.3\). “> | Jugador 2 | ||||
| \ (2.2.7\): Matriz de pago para ejercicio\(2.2.3\).” rowspan="5">Jugador 1 | W | X | Y | Z | |
| A | \(1\) | \(0\) | \(0\) | \(10\) | |
| B | \(-1\) | \(0\) | \(-2\) | \(9\) | |
| C | \(1\) | \(1\) | \(1\) | \(8\) | |
| D | \(-2\) | \(0\) | \(0\) | \(7\) | |
Determinar cualquier par de equilibrio en el juego de suma cero dado en la Tabla\(2.2.8\). Explica todos los pasos en tu solución. Si no puedes encontrar un par de equilibrio, explica qué sale mal.
| Tabla\(2.2.8\): Matriz de pago para ejercicio\(2.2.4\). | |||||
|---|---|---|---|---|---|
| \ (2.2.8\): Matriz de pago para ejercicio\(2.2.4\). “> | Jugador 2 | ||||
| \ (2.2.8\): Matriz de pago para ejercicio\(2.2.4\).” rowspan="5">Jugador 1 | W | X | Y | Z | |
| A | \(1\) | \(2\) | \(3\) | \(4\) | |
| B | \(0\) | \(-1\) | \(-0\) | \(5\) | |
| C | \(-1\) | \(3\) | \(2\) | \(4\) | |
| D | \(0\) | \(1\) | \(-1\) | \(1\) | |
Determinar cualquier par de equilibrio en el juego de suma cero dado en la Tabla\(2.2.9\). Explica todos los pasos en tu solución. Si no puedes encontrar un par de equilibrio, explica qué sale mal.
| Tabla\(2.2.9\): Matriz de pago para ejercicio\(2.2.5\). | |||||
|---|---|---|---|---|---|
| \ (2.2.9\): Matriz de pago para ejercicio\(2.2.5\). “> | Jugador 2 | ||||
| \ (2.2.9\): Matriz de pago para ejercicio\(2.2.5\).” rowspan="5">Jugador 1 | W | X | Y | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| B | \(1\) | \(-2\) | \(-3\) | \(0\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(15\) | |
Determinar cualquier par de equilibrio en el juego de suma cero dado en la Tabla\(2.2.10\). Explica todos los pasos en tu solución. Si no puedes encontrar un par de equilibrio, explica qué sale mal.
| Tabla\(2.2.10\): Matriz de pago para ejercicio\(2.2.6\). | |||||
|---|---|---|---|---|---|
| \ (2.2.10\): Matriz de pago para ejercicio\(2.2.6\). “> | Jugador 2 | ||||
| \ (2.2.10\): Matriz de pago para ejercicio\(2.2.6\).” rowspan="5">Jugador 1 | W | X | Y | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| B | \(1\) | \(-2\) | \(-5\) | \(-3\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(8\) | |
Lo más probable es que hayas tenido problemas para determinar un par de equilibrio para el juego en Ejercicio\(2.2.10\). ¿Significa esto que no hay un par de equilibrio? No necesariamente, pero estamos estancados si tratamos de utilizar sólo la idea de eliminar estrategias dominadas. Entonces necesitamos un nuevo método.
Podríamos pensar en nuestro siguiente método como el “peor de los casos”, o “juego extremadamente defensivo”. La idea es que queramos asumir que nuestro oponente es el mejor jugador que jamás haya vivido. De hecho, podríamos suponer que nuestro oponente es telepático. Entonces no importa lo que hagamos, nuestro oponente siempre adivinará qué vamos a elegir.
Asume que eres el Jugador 1, y estás jugando contra este Jugador 2 “infinitamente inteligente”. Considera el juego en la Mesa\(2.2.7\). Si eliges la fila A, ¿qué hará el Jugador 2? El jugador 2 elegirá la columna X o Y. Prueba esto para cada una de las filas. ¿Cuál fila es tu mejor opción? Si eliges A, obtendrás\(0\text{;}\) si eliges B, obtendrás\(-2\text{;}\) si eliges C, obtendrás\(1\text{;}\) y si eliges D obtendrás\(-2\text{.}\) Así, tu mejor opción es elegir C y obtener\(1\text{.}\) Ahora asume que eres Jugador 2, y el Jugador 1 es “infinitamente inteligente”. ¿Cuál columna es tu mejor opción? Si eliges W, el Jugador 1 obtendrá\(1\) (obtendrás\(-1\)); si eliges X, el Jugador 1 obtendrá\(1\text{;}\) si eliges Y, el Jugador 1 obtendrá\(1\text{;}\) y si eliges Z, obtendrás\(10\text{.}\) Así, puedes elegir W, X o Y (ya que quieres que el Jugador 1 gane menos) y obtener\(-1\text{.}\)
Usando el método descrito en Ejemplo\(2.2.4\), determinar qué debe hacer cada jugador en el juego en la Tabla\(2.2.8\).
Usando el método descrito en Ejemplo\(2.2.4\), determinar qué debe hacer cada jugador en el juego en la Tabla\(2.2.9\).
Después de trabajar a través de algunos ejemplos ¿se puede describir de manera más general el proceso utilizado en Ejemplo\(2.2.4\)? ¿Qué busca el Jugador 1 en cada fila? Entonces, ¿cómo elige qué fila jugar? ¿Qué busca el Jugador 2 en cada columna? ¿Cómo elige qué columna tocar?
Generalizar el método descrito en Ejemplo\(2.2.4\). Es decir, dar una regla general sobre cómo el Jugador 1 debe determinar su mejor jugada. Haz lo mismo para el Jugador 2.
¿Qué notas sobre el uso de este método en los juegos de Mesas\(2.2.7\)\(2.2.8\), Mesa y Mesa\(2.2.9\)? ¿La solución es un par de equilibrio?
Ahora pruebe este método en la elusiva matriz de pago en Table\(2.2.10\). ¿Qué debe hacer cada jugador? ¿Crees que conseguimos un par de equilibrio? Explique.
Las estrategias que encontramos usando el método anterior tienen un nombre más oficial. La estrategia del jugador 1 se llama la estrategia maximin. El jugador 1 está maximizando los valores mínimos de cada fila. La estrategia del jugador 2 se llama la estrategia minimax. El jugador 2 está minimizando los valores máximos de cada columna. Observe, podemos encontrar las estrategias maximin y minimax para cualquier juego de suma cero. Pero, ¿nuestros jugadores siempre quieren usar estas estrategias? ¿Siempre resultarán en un par de equilibrio? Los siguientes cinco ejercicios exploran estas preguntas.
Consideremos otra matriz de juego, dada en Tabla\(2.2.11\). Explica por qué no puedes usar estrategias dominadas para encontrar un par de equilibrio. ¿Crees que hay un par de equilibrio para este juego (por qué o por qué no)?
| Tabla\(2.2.11\): Matriz de pago para ejercicio\(2.2.12\). | |||||
|---|---|---|---|---|---|
| \ (2.2.11\): Matriz de pago para ejercicio\(2.2.12\). “> | Jugador 2 | ||||
| \ (2.2.11\): Matriz de pago para ejercicio\(2.2.12\).” rowspan="5">Jugador 1 | W | X | Y | Z | |
| A | \(-2\) | \(0\) | \(3\) | \(20\) | |
| B | \(1\) | \(2\) | \(-3\) | \(0\) | |
| C | \(10\) | \(-10\) | \(-1\) | \(1\) | |
| D | \(0\) | \(0\) | \(10\) | \(15\) | |
Si ambos jugadores utilizan la estrategia maximin/minimax, ¿cuál es el resultado del juego en Table\(2.2.11\)?
En el juego de la Mesa\(2.2.11\), si el oponente del Jugador 1 puede adivinar que el Jugador 1 elegirá usar una estrategia maximin, ¿es mejor que el Jugador 1 no use la estrategia maximin?
Supongamos que ambos jugadores deciden inicialmente utilizar la estrategia minimax/maximin en el juego en Table\(2.2.11\). ¿Es mejor que el Jugador 1 elija una estrategia diferente? Si el Jugador 2 adivina un cambio, ¿es mejor que el Jugador 2 cambie de estrategia? Continuar esta línea de razonamiento para varias iteraciones. ¿Qué estrategias elige cada uno de los jugadores? ¿Al menos un jugador siempre está mejor cambiando estrategias? ¿Podemos concluir que la estrategia máximo/ minimax no conduce a un par de equilibrio?
Compara tus respuestas en Ejercicio\(2.2.15\) con lo que sucede en Ejercicio\(2.2.3\)\(2.2.4\), Ejercicio y Ejercicio\(2.2.5\). ¿Puedes identificar alguna diferencia clave entre los juegos de Ejercicio\(2.2.15\) y Ejercicio\(2.2.3\)\(2.2.4\), Ejercicio y Ejercicio\(2.2.5\)?
Dado un juego de matriz de suma cero, podemos encontrar pares de equilibrio (si existen) por el método “guess and check”, eliminando estrategias dominadas y buscando las estrategias mínimo/maximin. Deberías poder aplicar los tres métodos y pensar qué método podría ser el más apropiado para un juego de matriz dado. Por ejemplo, aunque “adivinar y verificar” siempre debe encontrar un punto de equilibrio si existe, puede ser muy tedioso aplicarlo a una matriz realmente grande. El método máximo/minimax podría ser mucho más rápido.