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$"?

Thank you in advance!

  • $\begingroup$ If it's a zero-sum game, shouldn't Player 2's payoff be $-M(x,y)$ instead of $1-M(x,y)$? $\endgroup$ – Herr K. May 24 '13 at 23:05
  • $\begingroup$ 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"? $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.