function [xopt,yopt,payoff] = ZeroSumGameSolve(A)
% usage: [xopt,yopt,payoff] = ZeroSumGameSolve(A)
% description: This code solves a two-person zero-sum
% game with payoff matrix A for player 1. It returns
% player 1 optimal strategy in xopt, and optionally,
% player 2 optimal strategy in yopt and payoff of
% the game in payoff.

% set up for a linprog application
[m,n] = size(A);
Amin = min(min(A));
Amin = Amin*(Amin<0);
A1 = A - Amin;
% inequality A1*x<=b1 is required, so...
A1 = [-A1',ones(n,1)];
b1 = zeros(n,1);
% now the equality
E = [ones(1,m),0];
e = 1;
% finally, the objective function
c = -[zeros(m,1);1];
xopt = linprog(c,A1,b1,[],[],E,e);
payoff = xopt(m+1) + Amin;
xopt = xopt(1:m);
% next the =dual problem
% inequality A1*y<=b1
A1 = A - Amin;
A1 = [A1,-ones(m,1)];
b1 = zeros(m,1);
% now the equality
E = [ones(1,n),0];
e = 1;
% finally, the objective function
c = [zeros(n,1);1];
yopt = linprog(c,A1,b1,[],[],E,e);
yopt = yopt(1:n);