Suppose I have a matrix

$$ \begin{bmatrix} 1&4&2\\ 3&2&1 \end{bmatrix} $$

How do I find the minimax value of the matrix?

( It will be considered as a matrix of a matrix game where Player I chooses a row and simultaneously Player II chooses a column. The matrix entry of the jointly selected row and column represents as usual the winnings of the row chooser and the loss of the column chooser.)

It would be better if some one can explain it by solving with linear programming techniques.

  • $\begingroup$ First note that the column player will never choose column 2 since it is dominated by column 3. $\endgroup$ – Théophile Mar 6 '16 at 20:22
  • $\begingroup$ Are you considering mixed strategies or only pure strategies? $\endgroup$ – Théophile Mar 8 '16 at 4:34

First eliminate the second column, because the column player can always do strictly better by choosing the third column instead: $$\require{enclose} \begin{bmatrix} 1&\enclose{verticalstrike}4&2\\ 3&\enclose{verticalstrike}2&1 \end{bmatrix}$$ This reduces the game to a $2\times2$ matrix: \begin{bmatrix} 1&2\\ 3&1 \end{bmatrix} You can solve this using linear programming, but that would be more laborious in this case, and you haven't explained what you're having trouble with. Instead, suppose the row player chooses the first row with probability $p$ and that the column player chooses the first column with probability $q$. Then the row player's expected winnings will be $$w = 1pq + 2p(1-q) + 3(1-p)q + 1(1-p)(1-q) = -3pq + p + 2q + 1.$$ Taking partial derivatives, $$\frac{\partial w}{\partial p} = -3q + 1; \quad \frac{\partial w}{\partial q} = -3p + 2.$$ Set these equal to zero to find the optimal strategies.

  • $\begingroup$ I know this way my problem was writing them as equations I end up getting different answers because I am going wrong somewhere ... could you please list out steps to solve the problem by linear programming $\endgroup$ – csmath Mar 7 '16 at 13:14
  • $\begingroup$ Could you write out your model of the linear program first? $\endgroup$ – Théophile Mar 7 '16 at 22:04
  • $\begingroup$ max λ a1^T x >= λ a2^T x >= λ a3^T x >= λ so we have a1^T >= λ is the min of all values and we maximize over lambda to get maxmin value $\endgroup$ – csmath Mar 7 '16 at 22:33

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.