Prove that if (x*, y*) is a solution of an m times n matrix game A in mixed stra

Question

Prove that if (x*, y*) is a solution of an m times n matrix game A in mixed strategies and y*_k > 0 for some k element {1, ..., n} then A(x*, e_k) = v(A). Here e_k is the k^th unit vector. Use (1) to deduce a method for finding a solution in mixed strategies for a 3 times 3 matrix game A which has no solution in pure strategies without using the simplex method or domination to A (domination may however be applied to a submatrix of A if necessary). Make sure that you use the implication in (1) correctly and do not make a wrong statement.

Explanation / Answer

Let x = (x1, x2, . . . , xn) and y = (y1, . . . , ym) be the mixed strategies of the row player and the column player respectively.

Note that aij is the payoff of the row player (player 1) when the row player chooses row i and column player chooses column j with probability 1.

The corresponding payoff for the column player is aij . The expected payoff to the row player with the above mixed strategies x and y is given by

= u1(x, y)   

= Xm i=1 Xn j=1 aijxiyj = xAy where x = (x1, . . . , xm); y = (y1, . . . , yn) T ; A = [aij ] The expected payoff to column player = xAy. When the row player plays x, she assures herself of an expected payoff min y(S2) xAy The row player should therefore look for a mixed strategy x that maximizes the above. That is, an x such that max x(S1) min y(S2) xAy In other words, an optimal strategy for the row player is to do maxminimization. Note that the row player chooses a mixed strategy that is best for her on the assumption that whatever she does, the column player will choose an action that will hurt her (row player) as much as possible. This is a a direct consequence of rationality and the fact that the payoff for each player is the negative of the other player’s payoff. Similarly, when the column player plays y, he assures himself of a payoff = min x(S1) xAy = max x(S1) xAy That is, he assures himself of losing no more than max x(S1) xAy The column player’s optimal strategy should be to minimize this loss: min y(S2) max x(S1) xAy This is called minmaximization

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.