gameSolver

Solves zero-sum finite strategic games using the pivot method. Two players are playing a game where they each choose a move from a finite set of possibilities. For each combination of strategies, a (possibly negative) value is specified that player II must pay to player I. The game can then be represented as a matrix, and the game reduces to player I picking a row and player II picking a column. Solving the game is to find a probability vector for each player that guarantees I a minimal expected profit and II a maximal expected loss, and to find the value of the game. The value is the expected profit or loss, which are equal by von Neumann's minimax theorem.

function [p, q, V] = gameSolver(A)

% uses the pivot method to solve finite strategic games given in matrix form A.

[m, n] = size(A);

[sp] = pony(A);
if ~isempty(sp),
p = zeros(m, 1);
p(sp(1)) = 1;
q = zeros(1, n);
q(sp(2)) = 1;
V = a(sp(1), sp(2));
return;
end;

c = min(A(:));
if c < 0,
A = A + abs(c);
end;

T = initPivotTable(A);
T = pivotMethod(A);

V = 1 / T.A(m + 1, n + 1) - abs(c);

p = zeros(m, 1);
for c = 1:n,
swappedx = findstr(T.y{c}, 'x');
if isempty(swappedx),
continue;
end;
r = str2num(T.y{c}(2:end));
p(r) = T.A(c, n + 1) .* (1 / T.A(m + 1, n + 1));
end;

q = zeros(1, n);
for r = 1:m,
swappedy = findstr(T.x{r}, 'y');
if isempty(swappedy),
continue;
end;
c = str2num(T.x{r}(2:end));
q(c) = T.A(m + 1, r) .* (1 / T.A(m + 1, n + 1));
end;

function T = initPivotTable(A)
[m, n] = size(A);
for r = 1:m,
T.x{r} = ['x' num2str(r)];
end;
for c = 1:n,
T.y{c} = ['y' num2str(c)];
end;
T.A = [[A ones(m, 1)]; [-1 * ones(1, n) 0]];

function T = pivotMethod(A)
T = initPivotTable(A);
while length(find(T.A(end, :) < 0)) > 0,
c = find(T.A(end, :) < 0);
if ~isempty(find(c == 2)),
c0 = 2;
else,
c0 = c(1);
end;
fprintf(['Pivotting column ' num2str(c0) '.\n']);
T = pivot(T, c0);
end;

function T_new = pivot(T, c0)
%T.A is the game matrix with added column and row
%T.x
%T.y
T_new = [];
if T.A(end, c0) >= 0,
return;
end;
[m, n] = size(T.A);
% find row with smallest border-column / A(row, c0) ratio
minrat = [];
r0 = [];
for r = 1:m,
if T.A(r, c0) <= 0,
continue;
end;
rat0 = T.A(r, n) / T.A(r, c0);
if isempty(minrat),
minrat = rat0;
r0 = r;
elseif rat0 < minrat,
minrat = rat0;
r0 = r;
end;
end;
if isempty(r0),
return;
end;
T_new.x = T.x;
T_new.x(r0) = T.y(c0);
T_new.y = T.y;
T_new.y(c0) = T.x(r0);
T_new.A = [];
for r = 1:m,
for c = 1:n,
if r == r0 && c == c0,
T_new.A(r, c) = 1/T.A(r0, c0);
elseif r == r0,
T_new.A(r, c) = T.A(r, c) / T.A(r0, c0);
elseif c == c0,
T_new.A(r, c) = -T.A(r, c) / T.A(r0, c0);
else,
T_new.A(r, c) = T.A(r, c) - T.A(r, c0) * T.A(r0, c) / T.A(r0, c0);
end;
end;
end;
disp(T_new.y);
for r = 1:(m-1),
fprintf([T_new.x{r} ' ' num2str(T_new.A(r, :)) '\n']);
end;
fprintf(['  ' num2str(T_new.A(m, :)) '\n']);

function sp = pony(A)