Linear Programming for two-person zero-sum Games

Graphical Solution of 2*n Matrix Games

In this Excel file you can graph the lines or planes. We have to maximize the function
v(x)=min{a1jx1+a2jx2}.
v(x)=min{(a1j-a2j)x1+a2j}, since x2= 1-x1.
These n linear functions fj(x1)=(a1j-a2j)x1+a2j in x1 (given in slope-intercept form) can be graphed, and then the x1 that maximizes the minimum of these lines can be found graphically. Actually these linear functions are very easy to graph, since f(0)=a2j and f(1)=a1j ---we just graph these two points, getting the height directly from the matrix. Viewing all these graphs as our ceiling, the optimization problem consists in finding that x1 where the ceiling (the lowest one) is highest.

Put in the Matrix in Normal Form

Number of columns:
Here is the Analysis:

Intersections of the (m choose 2) straight lines.
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
x1: height:
And the two border values, x1=0 and x1=1.
x1: height:
x1: height:

Here is the Solution:

x1: Value:

Graphical Solution of 3*n Matrix Games

We have to maximize the function
v(x)=min{a1jx1+a2jx2+a3jx3}.
Since x3=1-x1-x2 follows from the choice of x1 and x2, it suffices to choose x1 and x2 only (both between 0 and 1, with sum less or equal to 1).
v(x)=min{a1jx1+a2jx2+a3j(1-x1-x2)} = min{(a1j-a3j)x1+(a2j-a3j)x2+a3j}.
These n linear functions in x1 and x2 can be graphed over the triangle x1 ≥ 0, x2 ≥ 0, x1+x2 ≤ 1, and then the point (x1,x2) that maximizes the minimum of these planes can be found graphically.

Put in the Matrix in Normal Form

Number of columns:
Here is the Analysis:

Intersections of the (m choose 3) planes.
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
And the three border values, x2=0 and x2=1.
x1: x2: height:
x1: x2: height:
x1: x2: height:
And the intersections of two planes and the borders.
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:
x1: x2: height:

Here is the Solution:

x1: x1: Value:

Larger Matrices

Let A be the payoff matrix. We are looking for probabilities p1, p2, ... pn with p1+p2+...+pn=1, all pi ≥ 0, which maximizes

We want to maximize m under the restrictions pT ≥ (m,m,...m), with p1+p2+...+pn=1, all pi ≥ 0. This is linear program with variables m, p1, p2, ... , pn.