Make your own free website on Tripod.com


MINIMAX Analysis
for Zero Sum Games

Augusto Rufasto


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:

B1B2B3
A1243
A17210
A11132


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:

{p1, p2,..., pn}

Player B has the following probability distribution for his choices:

{q1, q2,..., qm}

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 {pi} and B's mixed MINIMAX strategy as {qi}.

If A uses {pi}, 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 {qi}, 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=(p1 + p2 +...+ pn)
a11p1 + a21p2 +...+ an1pn >= V
a12p1 + a22p2 +...+ an2pn >= V
.
.
.
a1np1 + a2np2 +...+ anmqn >= V
p1 + p2 +...+ pm = 1

Transform r using ri = pi/V(game), and then you have:

min (r1 + r2 +...+ rn)
s.t.:
a11r1 + a21r2 +...+ an1rn >= 1
a12r1 + a22r2 +...+ an2rn >= 1
.
.
.
a1mr1 + am2r2 +...+ amnrn >= 1

Once this Linear Programming problem is solved, you'll find an m-size set for ri. Calculate then the values for pi by using the formulae:

pi = ri*V

where:

V = value(game) = (r1 + r2 +...+ rn)



Problem

Using the technique find the solution for this problem:

B1B2B3
A1243
A17210
A11132