Matrix Games

We want to figure out how to maximize your winnings when playing a matrix game (or at least minimize your losses if the game is stacked against you!). That sounds like a maximization problem, but what are we maximizing over? We want to pick the best strategy so we’ll need a mathematical model of a playing strategy.

One strategy you could follow is to always pick the same move in every round. We’ll call these pure strategies and there is one for every choice of move. These are typically poor strategies: for example, if you use the strategy always play rock in rock, paper, scissors, your opponent will soon catch on and start using the paper 4ever strategy.

You can do much better by mixing it up unpredictably! In rock, paper, scissors playing each move one third of the time chosen randomly¹ will protect you against any possible strategy of player two: you will on average win a third of the rounds, tie a third of the rounds and lose a third of the rounds. That’s the best you can hope for, since if player two uses that same uniformly random strategy you won’t win more than a third of the time on average.

In rock, paper, scissors all the moves are basically equivalent: each move beats one of your opponents moves, ties with one and loses against one. So in a random strategy it makes sense to pick them all with the same probability. In general matrix games this need not be true, so we should consider playing randomly, but where each move is assigned a possibly different probability of being chosen.

This is what we will call a mixed strategy: a strategy described by assigning each move a certain probability and then playing randomly according to those probabilities. If player one has \(n\) possible moves, a mixed strategy for player one is given by choosing probabilities \(x_1, x_2, \ldots, x_n\). The vector of probabilities \(\begin{pmatrix} x_1 & x_2 & \ldots & x_n \end{pmatrix}^\top\) is called a stochastic vector, meaning a vector whose entries are non-negative and satisfy \(x_1 + x_2 + \cdots + x_n =1\).

Notice that pure strategies are a special case of a mixed strategy: they are the case where one of the \(x_i=1\) and all the other are \(0\). So maybe a better name would be “potentially mixed” strategies, but of course, that’s just too long! In fact we’ll mostly just say “strategies” instead of “mixed strategies”.

How do we measure how good a mixed strategy is? As a first step, let’s see how to measure how good a mixed strategy when played against a specific mixed strategy for the other player. For example, say in rock, paper, scissors the two players decided to use the following strategies:

How do those strategies fare against each other? If the game goes on for \(N\) rounds, we’d expect it to go approximately like this (where P_i means player #i):

So the net winnings for player one over the course of those \(N\) rounds will be \(- N/6 + N/12 - N/4 + N/6 = -N/6\), for an average of \(-1/6\) per round. Notice that the \(N\) just “comes along for the ride” and cancels in the end. We could find the average winnings just thinking about probabilities: for example, with probability \((1/2)(1/3) = 1/6\), player one picks rock and player two picks paper, and since with those moves player one loses 1, this contributes a \(-1/6\) to the average winnings.

In general, assuming player one will follow the mixed strategy \(\mathbf{x}\) and that player two will follow the mixed strategy \(\mathbf{y}\), we can compute the expected² winnings for player one as follows: with probability \(x_i y_j\) player one will make move #\(i\) and player two will make move #\(j\); that combination results in player one winning \(a_{ij}\), so in total the expected winnings of player one are \(\sum_{i,j} a_{ij} x_i y_j = \mathbf{x}^{\top} A \mathbf{y}\).

Now that we know how to evaluate any pair of mixed strategies against each other, let’s think about how to find optimal strategies. Let’s think from the point of view of player one. Player one has no control over what strategy player two will use, so to play it safe, player one should pick one that maximizes her winnings assuming player two responds as well as possible against the strategy. If player one use strategy \(\mathbf{x}\), the best player two can do against that would be to pick a strategy \(\mathbf{y}\) that minimizes \(\mathbf{x}^{\top} A \mathbf{y}\) —remember that that expression computes the expected winnings for player one, so player two wants to minimize it! So if player one uses strategy \(\mathbf{x}\), she can’t guarantee she’ll win more than \(\min_{\text{stoch. } \mathbf{y}} \mathbf{x}^{\top} A \mathbf{y}\) (where the minimum is taken over all stochastic vectors \(\mathbf{y}\)) on average per round. To be prepared for player two playing as smart as possible, player one should choose the strategy \(\mathbf{x}\) that maximizes that number, i.e., player one should compute: \[v(A) = \max_{\text{stoch. }\mathbf{x}} \left(\min_{\text{stoch. }\mathbf{y}} \mathbf{x}^{\top} A \mathbf{y}\right).\]

We’ll call that number the value of the game. It is the largest number \(v\) so that player one has a mixed strategy that guarantees an expected winnings per round of at least \(v\). To compute \(v(A)\) we will phrase the maximization as a linear program, which can then solved via the Simplex Method.

The key step is that the inner minimization is actually very simple! For a fixed stochastic vector \(\mathbf{x}\) we want to find the minimum value of \(\mathbf{x}^{\top}A\mathbf{y}\) where \(y\) varies over all stochastic vectors (of the appropriate size). We can think of this in terms of the game: player one is committed to using strategy \(\mathbf{x}\), player two knows this and is trying to figure out how to best respond. In that situation, player two could simply figure out which pure strategy is best against \(\mathbf{x}\) and just use that! For example, if in rock, paper, scissors player one proclaims: “I shall play rock 70% of the time, paper 20% and scissors 10%!”, player two should respond by always playing paper!

In more algebraic terms, what we are saying is that \[\min_{\text{stoch. } \mathbf{y}} \mathbf{x}^{\top} A \mathbf{y} = \min\text{entry of } \mathbf{x}^{\top}A.\] This is not hard to prove formally: if \(\mathbf{x}^{\top}A = (s_1, s_2, \ldots, s_m)\) and \(s_j\) is the smallest of those entries, we have for any stochastic vector \(\mathbf{y}\): \[\begin{aligned} \mathbf{x}^{\top}A\mathbf{y} & = s_1 y_1 + s_2 y_2 + \cdots + s_m y_m \\ & \ge s_j y_1 + s_j y_2 + \cdots s_j y_m = s_j (y_1 + \cdots + y_m) = s_j.\end{aligned}\] Since when we take \(y\) to be the pure strategy for move #\(j\) equality is attained, we can conclude that \(\min_{\text{stoch. } \mathbf{y}} \mathbf{x}^{\top} A \mathbf{y} = s_j\).

Using this we can easily turn the computation of the value of the game into a linear program. We’ll add a variable \(z\) to stand for the minimum entry of \(\mathbf{x}^{\top} A\). Of course, we can’t simply put “\(z = \min\text{entry of } \mathbf{x}^{\top}A\)” as a constraint in the linear program. But if we put in constraints that say “\(z \le j\text{th entry of } \mathbf{x}^{\top} A\)” for each \(j\), then those already tells us \(z\) is at most the minimum entry. Since \(z\) is exactly what we wish to maximize, in any optimal solution \(z\) will be equal to that minimum entry. Putting it all together this is the LP we get:

Maximize \(z\)

subject to \[\begin{aligned} \begin{pmatrix} z & z & \ldots & z \end{pmatrix} & \le \mathbf{x}^\top A \\ x_1 + x_2 + \cdots + x_n & = 1 \\ x_1, x_2, \ldots, x_n & \ge 0 \end{aligned}\]

The optimal value of this LP is \(v(A)\), the value of the game with matrix \(A\). Notice that this LP always has an optimal value:

• It is feasible because we can get a feasible solution by taking \(\mathbf{x}\) to be any stochastic vector and \(z\) to be the minimum entry of \(\mathbf{x}^{\top} A\).
• It is bounded because as \(\mathbf{x}\) varies over all stochastic vectors, the entries of \(\mathbf{x}^{\top} A\) are bounded (by \(\sum_{i,j} |a_{ij}|\), for example), and thus so is the objective function \(z\).

The analysis above is written from the point of view of player one. Player two could also carry out similar reasoning and reach the conclusion that the smallest number \(v\) such that player two has strategy that guarantees that player one can’t find a strategy against it with more than \(v\) expected winnings is equal to \[\min_{\text{stoch. } \mathbf{y}} \left(\max_{\text{stoch.} \mathbf{x}} \mathbf{x}^{\top} A \mathbf{y} \right).\]

We can also repeat the argument in the last section: first, to show that \[\max_{\text{stoch. } \mathbf{x}} \mathbf{x}^{\top} A \mathbf{y} = \max\text{entry of } A \mathbf{y},\] and second, to find an LP whose optimal value is that minimum that player two wants:

Minimize \(w\)

subject to \[\begin{aligned} \begin{pmatrix} w & w & \ldots & w \end{pmatrix}^\top & \ge A \mathbf{y} \\ y_1 + y_2 + \cdots + y_m & = 1 \\ y_1, y_2, \ldots, y_m & \ge 0 \end{aligned}\]

If you look at this LP carefully you’ll notice something wonderful: it’s the dual of the LP for player one!³ Let’s figure out what duality theory for these LP’s means in terms of the games. For that, notice that there is a strong connection between feasible solutions and mixed strategies. Take the LP for player one, for instance. Its variables are the \(x_i\) and an extra variable \(z\). A feasible solution is precisely a stochastic vector \(\mathbf{x}\) together with a number \(z\) that is at most the minimum entry of the vector \(\mathbf{x}^{\top}A\). Given any stochastic vector \(\mathbf{x}\) we can get a corresponding feasible solution simply by setting \(z := \min \text{entry of } \mathbf{x}^{\top} A\); and this value of \(z\) is the maximum we can take for a feasible solution that includes \(\mathbf{x}\).

Using that correspondenc we can translate results from duality theory for LPs to results about matrix games.

Strong duality tells us the optimal values of primal and dual must agree (when those LPs have optimal solutions, which as we saw above, is guaranteed in this case). This translates to:

We can also use duality theory to get a very convenient way to check whether or not strategies are optimal. The fact that given feasible primal and dual solutions they are optimal if and only if their objective functions agree translates to:

If you have a good guess as to what optimal strategies for players one and two are then the above theorem is certainly the best way to prove your guess is correct. But even if you only have a guess for player one it might be that the easiest way to show you’re right is to make a guess for an optimal strategy for player two and check using this theorem.

A game is called fair is its value is zero. This means that on average the wins and loses for each player balance out. Remember that a game is symmetric if “its rules are the same for player one and player two”, or mor formally, if its payoff matrix is antisymmetric: \(A = -A^{\top}\). It seems obvious that a symmetric game is fair: if the rules are the same for both player, neither player should have an advantage! Let’s show that.

Notice that this is for an arbitrary matrix, we are not assuming that \(A = -A^{\top}\).

Now if the game is symmetric, that is, if \(A = -A^{\top}\), the lemma tells us that \(v(A) = -v(-A^{\top}) = -v(A)\), from which we conclude that \(v(A)=0\).

Certain moves are never a good idea. If player one has two moves, say #\(k\) and #\(i\) such that against every move of player two the payoff using move #\(k\) is at least as much as it is for move #\(i\), then player one can simply decide to never use move #\(i\) and doesn’t miss out any potential payoff. We’ll say that move #\(k\) dominates move #\(i\).

We can state that dominated moves are irrelevant as follows:

Before we prove this, a couple of remarks:

• Notice that we can’t claim that in every optimal strategy for player one we have \(x^{*}_i = 0\), i.e., that move #\(i\) is never used in an optimal: for one thing rows \(k\) and \(i\) could be equal, but even if they are not, they could differ only in entries occurring in columns that an optimal strategy for player two doesn’t need to use, in which case the difference is not relevant. The best we can say is that it is possible to avoid using move #\(i\) in an optimal strategy.
• By symmetry there is an analogous proposition for player two: if \(\mathrm{col}_k(A) \ge \mathrm{col}_i(A)\), then there is an optimal strategy \(\mathbf{y}^{*}\) for player two in which \(y^{*}_k = 0\). Notice that with that inequality, move #\(k\) is the one that player two can avoid: it always give a payoff for player one that is at least as large as the one from move #\(i\).

Once we know that a move can be avoided, we can just remove that row or column from the matrix and get a smaller game with the same value! And sometimes after removing a move there appears a new dominated move that can be removed in turn and so on. For example, consider the game with payoff matrix: \[ A = \begin{pmatrix} 3 & 4 & 1 & -5 & -2 \\ 1 & -3 & 10 & -1 & 2 \\ 7 & -1 & 8 & 5 & 6 \\ 8 & -2 & 9 & 4 & 3 \\ \end{pmatrix}.\]

Columns 1 and 3 are both dominated by column 4, so we can reduce to: \[ A' = \begin{pmatrix} 4 & -5 & -2 \\ -3 & -1 & 2 \\ -1 & 5 & 6 \\ -2 & 4 & 3 \\ \end{pmatrix}.\]

Now rows 2 and 4 are dominated by row 3 (and this wasn’t true in \(A\)!), so we can reduce to: \[ A'' = \begin{pmatrix} 4 & -5 & -2 \\ -1 & 5 & 6 \\ \end{pmatrix}.\]

Finally, column 3 is dominated by column 2, so we can reduce to: \[ A''' = \begin{pmatrix} 4 & -5 \\ -1 & 5 \\ \end{pmatrix}.\]

At this point no move dominates another move so if we want to compute \(v(A''')\), we need to do something else. We could of course just use the Simplex Method on the LP for player one:

Maximize \(z\)

subject to \[\begin{aligned} z & \le 4x_1 - x_2\\ z & \le -5x_1+5x_2\\ & x_1 + x_2 = 1 \\ & x_1, x_2 \ge 0 \end{aligned}\]

But maybe for such a small problem it’s not worth it to bust out the Simplex Method. Just let \(t=x_1\) so \(x_2=1-t\). The LP becomes:

Maximize \(z\)

subject to \[\begin{aligned} z & \le 5t-1\\ z & \le 5-10t\\ 0 & \le t \le 1 \end{aligned}\]

Now, \(5t-1 \le 5-10t\) when \(t \le 2/5\). So for \(0 \le t \le 2/5\) we have \(z \le 5t-1\) and the maximum is for \(t=2/5, z=1\). For \(2/5 \le t \le 1\) we have \(z \le 5-10t\) and the maximum is again \(t=2/5, z=1\).

So we get that \(v(A''')=1\) and that an optimal strategy is given by \(\begin{pmatrix} 2/5 & 3/5 \end{pmatrix}^\top\). This in turn means that \(v(A)=1\) with optimal strategy \(\begin{pmatrix} 0 & 2/5 & 0 & 3/5 & 0 \end{pmatrix}^\top\).