# Finding the payoff matrix of a game

A two player zero-sum game can be represented by a $m\times n$ payoff matrix $M$ having $m$ rows and $n$ columns with values in $[0,1]$. The value $M(x,y)$ represent the payoff given to player $1$ [and $1-M(x,y)$ is the payoff given to Player $2$] when Player $1$ decides to play the strategy $x\in 0\dots m$ and Player $2$ the strategy $y\in 0\dots n$.

Players are also allowed to play with mixed strategies, i.e., discrete probability distributions over $\{0,\dots,m\}$ and $\{0,\dots, n\}$ respectively. The payoff associated to paris of mixed strategies is then defined as expected (=Expected value)

Fact: It is known (form von Neumann minimax theorem I believe) that given $M$, both players have optimal mixed strategies and these strategies can be computed.

Question: I would like to know if:

"given a strategy $s$ for Player $1$ (i.e., a probability distribution $s$ over $\{0,\dots,m\}$, is it possible to find a number $n\geq 2$ and a $m\times n$ payoff matrix $M$ such that $s$ is indeed an optimal strategy for Player $1$ in the game represented by $M$"?

• If it's a zero-sum game, shouldn't Player 2's payoff be $-M(x,y)$ instead of $1-M(x,y)$? – Herr K. May 24 '13 at 23:05
• Also, am I correct to rephrase your question as "Given a mixed strategy $s$ of Player 1, is it possible to construct a zero-sum game where Player 2 has more than one pure strategy such that $s$ is a best response to some of Player 2's (mixed) strategies"? – Herr K. May 24 '13 at 23:12
Unless I miss something, there seem to be many possibilities. Trivially, all payoffs could be the same, in which case every strategy is optimal. Another e.g. let $n=m$ and the payoff matrix be diagonal with entries $\dfrac{V}{p_i}$ for non-zero $V, p_i$. I am sure you can generate many more.
If the game is truly zero-sum, then $$\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$$ The optimal strategies must satisfy $\mathbf{M}^T\mathbf{s}^* \le \mathbf{0}$, and $\mathbf{M}\mathbf{t}^* \ge \mathbf{0}$. The nonzero components of $\mathbf{s}^*$ must correspond to zero components of $\mathbf{M}\mathbf{t}^*$. Likewise, the nonzero components of $\mathbf{t}^*$ must correspond to zero components of $\mathbf{M}^T\mathbf{s}^*$.
So given $\mathbf{s}^*$, we can construct $\mathbf{M}$ by choosing columns orthogonal to $\mathbf{s}^*$, and then scaling them so that $\mathbf{Mt} = 0$ for some positive $\mathbf{t}$.