Encontrar la matriz de pagos de un juego

Question

Un juego de suma cero de dos jugadores puede ser representado por un $m\times n$ matriz de pagos $M$ teniendo $m$ filas y $n$ columnas con valores en $[0,1]$ . El valor $M(x,y)$ representan la retribución otorgada al jugador $1$ [y $1-M(x,y)$ es la retribución que recibe el jugador $2$ ] cuando el jugador $1$ decide jugar la estrategia $x\in 0\dots m$ y Jugador $2$ la estrategia $y\in 0\dots n$ .

También se permite a los jugadores jugar con estrategias mixtas, es decir, con distribuciones de probabilidad discretas sobre $\{0,\dots,m\}$ y $\{0,\dots, n\}$ respectivamente. La retribución asociada a paris de estrategias mixtas se define entonces como esperada (=Valor esperado)

Es un hecho: Se sabe (creo que por el teorema minimax de von Neumann) que dado $M$ ambos jugadores tienen estrategias mixtas óptimas y estas estrategias pueden ser calculadas.

Pregunta: Me gustaría saber si:

"dada una estrategia $s$ para el jugador $1$ (es decir, una distribución de probabilidad $s$ en $\{0,\dots,m\}$ , ¿es posible encontrar un número $n\geq 2$ y un $m\times n$ matriz de pagos $M$ tal que $s$ es efectivamente una estrategia óptima para el jugador $1$ en el juego representado por $M$ "?

Gracias de antemano.

Answer 1

A menos que me pierda algo, parece que hay muchas posibilidades. Trivialmente, todos los pagos podrían ser iguales, en cuyo caso todas las estrategias son óptimas. Otra, por ejemplo, que $n=m$ y que la matriz de pagos sea diagonal con entradas $\dfrac{V}{p_i}$ para los casos en los que el valor es distinto de cero $V, p_i$ . Estoy seguro de que se pueden generar muchos más.

Answer 2

Si el juego es realmente de suma cero, entonces $$ \min_{\substack{0 \le \mathbf{s} \le \mathbf{1}\\\mathbf{1}^T \mathbf{s}=1}} \max_{\substack{0 \le \mathbf{t} \le \mathbf{1}\\\mathbf{1}^T \mathbf{t}=1}} \mathbf{s}^T\mathbf{M}\mathbf{t} = \max_{\substack{0 \le \mathbf{t} \le \mathbf{1}\\\mathbf{1}^T \mathbf{t}=1}} \min_{\substack{0 \le \mathbf{s} \le \mathbf{1}\\\mathbf{1}^T \mathbf{s}=1}} \mathbf{s}^T\mathbf{M}\mathbf{t} =0 $$ Las estrategias óptimas deben satisfacer $\mathbf{M}^T\mathbf{s}^* \le \mathbf{0}$ y $\mathbf{M}\mathbf{t}^* \ge \mathbf{0}$ . Los componentes no nulos de $\mathbf{s}^*$ debe corresponder a componentes cero de $\mathbf{M}\mathbf{t}^*$ . Asimismo, los componentes no nulos de $\mathbf{t}^*$ debe corresponder a componentes cero de $\mathbf{M}^T\mathbf{s}^*$ .

Así que dado $\mathbf{s}^*$ podemos construir $\mathbf{M}$ eligiendo columnas ortogonales a $\mathbf{s}^*$ y, a continuación, escalarlas para que $\mathbf{Mt} = 0$ para algún positivo $\mathbf{t}$ .