Augusto Rufasto: MINIMAX Analysis for Zero Sum Games

MINIMAX Analysis
for Zero Sum Games

Zero sum games modeled in matrices need to be solved by finding the saddle point solution, by means of minimax analysis. A non-stochastic minimax solution should be considered in the first place. If this solution doesn't exist, then a stochastic minimax solution should be found.

Saddle point

A saddle point is a cell which comes as a maximum in one sense and as a minimum in another. In payoff matrices, a saddle point cell is a local maximum as well as a local minimum. We are now interested in finding a saddle point cell for the whole matrix.

Step 1: Find your minimum payoff

To find out if there is a saddle point solution for the game represented in the matrix, label each row at its end with its minimum payoff. This way you'll define your worst case scenarios when choosing a strategy.

Step 2: Find your opponent's minimum payoff

Then label each column at its bottom with its maximum payoff. This will show the worst case scenarios for your opponent. Find out which is the highest value in the series of minimum values. Then find out which is the lowest value in the series of maximum values.

Step 3: Find out if there is a minimax solution

If these two values match, then you just found the saddle point cell. This is the non-stochastic minimax solution.

If there is a minimax solution, then it is possible that both agents choose the corresponding strategies. You and your opponent are maximizing the gain that the worst possible scenario can drive.

Stochastic MINIMAX solving

The following game has not a non-stochastic MINIMAX solution:

	B1	B2	B3
A1	2	4	3
A1	7	2	10
A1	11	3	2

To study and solve this problem linear programming is necessary. Each player will not look for one strategy, but for one random choice, i.e., for a choice whose actual value depends on randomness. Thus, each player should seek for a probability distribution, instead searching for a specific strategy. We call this a mixed strategy. The value of this mixed strategy comes from the expected value fo the random choices. This is an ex ante value, and we'll call it V.

Player A has the following probability distribution for his choices:

{p₁, p₂,..., p_n}

Player B has the following probability distribution for his choices:

{q₁, q₂,..., q_m}

This stochastic MINIMAX is a convergence point for both players. The reason for this is that both players will use the same technique to minimize risk and maximize payoff, so that finally both of them are expected to use the probability distribution found by the technique. It can be shown that a unique expected value V will represent the expected values of the two players: player A will receive V and player B will receive -V, but only as an expected value. The actual value will deoend on the actual strategies defined by the mixed strategy (which is a roulette of sorts).

Let's call A's mixed MINIMAX strategy as {p_i} and B's mixed MINIMAX strategy as {q_i}.

If A uses {p_i}, then th ex ante value of the game is one and only one, and it is V. It doesn't matter if B chooses a pure strategy, the ex ante value of the game remains being V.

If B uses {q_i}, then the ex ante value of the game is one and only one, and it is V. It doesn't matter if B chooses a pure strategy, the ex ante value of the game remains being V.

If both use their respective mixed strategies, this ex ante V logically stands. But if they prefer to use pure strategies then there is no ex ante value of the game, and the result is not protected by a MINIMAX defensive strategy.

How to find the stochastic MINIMAX solution

Linear Programming is needed to make the calculations. The following is the procedure to find the mixed MINIMAX strategies:
max V
s.t. (subject to restrictions):
V=(p₁ + p₂ +...+ p_n)
a₁₁p₁ + a₂₁p₂ +...+ a_n1p_n >= V
a₁₂p₁ + a₂₂p₂ +...+ a_n2p_n >= V
.
.
.
a_1np₁ + a_2np₂ +...+ a_nmq_n >= V
p₁ + p₂ +...+ p_m = 1
Transform r using r_i = p_i/V(game), and then you have:
min (r₁ + r₂ +...+ r_n)
s.t.:
a₁₁r₁ + a₂₁r₂ +...+ a_n1r_n >= 1
a₁₂r₁ + a₂₂r₂ +...+ a_n2r_n >= 1
.
.
.
a_1mr₁ + a_m2r₂ +...+ a_mnr_n >= 1
Once this Linear Programming problem is solved, you'll find an m-size set for r_i. Calculate then the values for p_i by using the formulae:

p_i = r_i*V

where:

V = value(game) = (r₁ + r₂ +...+ r_n)

Problem

Using the technique find the solution for this problem:

	B1	B2	B3
A1	2	4	3
A1	7	2	10
A1	11	3	2

AugustoRufasto