11.3: Reducción por dominancia

A veces una matriz de\(m \times n\) juego se puede reducir a una\(2 \times 2\) matriz eliminando ciertas filas y columnas. Una fila se puede eliminar si existe otra fila que produzca un beneficio de un valor igual o mejor. De igual manera, una columna puede ser eliminada si hay otra columna que producirá una compensación de un valor igual o mejor para el reproductor de columnas. Se dice que la fila o columna que produce un mejor beneficio para su jugador correspondiente domina la fila o columna con el menor beneficio.

Ejemplo\(\PageIndex{1}\)

Para el siguiente juego, determina la estrategia óptima tanto para el jugador de fila como para el jugador de columna, y encuentra el valor del juego.

\ [G=\ left [\ begin {array} {ccc}
-2 & 6 & 4\\
-1 & -2 & -3\\
1 & 2 & 2 & -2
\ end {array}\ derecha]\ nonumber\]

Solución

Primero buscamos un punto de sillín y determinamos que no existe ninguno. A continuación, tratamos de reducir la matriz a una\(2 \times 2\) matriz eliminando la fila dominada.

Dado que cada entrada en la fila 3 es mayor que la entrada correspondiente en la fila 2, la fila 3 domina la fila 2. Por lo tanto, un jugador de fila racional nunca jugará la fila 2, y eliminamos la fila 2. Obtenemos

\ [\ left [\ begin {array} {ccc}
-2 & 6 & 4\\
1 & 2 & -2
\ end {array}\ right]\ nonumber\]

Ahora tratamos de eliminar una columna. Recuerde que la matriz de juego representa los pagos para el jugador de fila y no el jugador de columna; por lo tanto, cuanto mayor sea el número en la columna, menor será el beneficio para el jugador de columna.

El jugador de columna nunca jugará la columna 2, porque está dominada tanto por la columna 1 como por la columna 3. Por lo tanto, eliminamos la columna 2 y obtenemos la matriz modificada, M, a continuación.

\ [\ mathrm {M} =\ left [\ begin {array} {cc}
-2 & 4\\
1 & -2
\ end {array}\ right]\ nonumber\]

Para encontrar la estrategia óptima tanto para el jugador de fila como para el jugador de columna, utilizamos el método aprendido en la Sección 11.2.

Deje que la estrategia del jugador de fila sea\ (\ mathrm {R} =\ left [\ begin {array} {ll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {array}\ right]\), y la estrategia be del jugador de columna sea\ (C=\ left [\ begin {array} {c}
c\\
1-c
\ end {array}\ right]\)

Para encontrar la estrategia óptima para el jugador de fila, nosotros, primero, encontramos el producto RM de la siguiente manera.

\ [\ left [\ begin {array} {lll}
\ mathrm {r} & 1-\ mathrm {r}
\ end {array}\ right]\ left [\ begin {array} {cc}
-2 & 4\\
1 & -2
\ end {array}\ right] =\ left [\ begin {array} {ll}
-3 r+1 & 6 r-2
\ end {array}\ right]\ nonumber\]

Al establecer las entradas iguales, obtenemos

\[-3r + 1 = 6r - 2 \nonumber \]

o

\[r = 1/3 \nonumber. \nonumber \]

Por lo tanto, la estrategia óptima para el jugador de fila es\ (\ left [\ begin {array} {ll}
1/ 3 & 2/3
\ end {array}\ right]\), pero relativo a la matriz original del juego es\ (\ left [\ begin {array} {lll}
1/3 & 0 & 2/3
\ end {array}\ right]\).

Para encontrar la estrategia óptima para el reproductor de columna nosotros, primero, encontramos el siguiente producto.

\ [\ left [\ begin {array} {cc}
-2 & 4\\
1 & -2
\ end {array}\ right]\ left [\ begin {array} {c}
c\\
1-c
\ end {array}\ right] =\ left [\ begin {array} {c}
-6 c+4\\
3 c-2
\ end {array}\ right]\ nonumber\]

Establecemos las entradas en la matriz del producto iguales entre sí, y obtenemos,

\[-6c + 4 = 3c - 2 \nonumber \]

o

\[c = 2/3 \nonumber. \nonumber \]

Por lo tanto, la estrategia óptima para el jugador de columna es\ (\ left [\ begin {array} {l}
2/3\\
1/3
\ end {array}\ right]\), pero relativa a la matriz original del juego, la estrategia para el jugador de columna es\ (\ left [\ begin {array} {c}
2/3\\
0\
1/3
\ end {array}\ right]\).

Para encontrar el valor esperado, V, del juego, tenemos dos opciones: ya sea para encontrar el producto de las matrices R, M y C, o bien multiplicar las estrategias óptimas relativas a la matriz original a la matriz original. Elegimos el primero, y obtenemos

\ [\ begin {array} {l}
\ mathrm {V} =\ left [\ begin {array} {lll}
1/3 & 3
\ end {array}\ right]\ left [\ begin {array} {cc}
-2 & 4\
1 y -2
\ end {array}\ right]\ left [\ begin {array} {l}
2/3\\
1/ 3
\ end {array}\ right]\\
\ mathrm {V} =\ left [\ begin {array} {l}
0
\ end {array}\ right]\ end {array}
\ end {array}\ nonumber\]

Por lo tanto, si ambos jugadores juegan su estrategia óptima, el valor del juego es cero.

Resumimos de la siguiente manera:

Reducción por dominancia

1. A veces una matriz de\(m \times n\) juego se puede reducir a una\(2 \times 2\) matriz eliminando filas y columnas dominadas.
2. Una fila se llama fila dominada si existe otra fila que producirá una compensación de un valor igual o mejor. Eso sucede cuando existe una fila cuya entrada es mayor que la entrada correspondiente de la fila dominada.
3. Una columna se llama columna dominada si existe otra columna que producirá una compensación de un valor igual o mejor. Esto sucede cuando existe una columna cuya entrada es menor que la entrada correspondiente de la fila dominada.