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));
    fprintf('Saddle point found.\n');
    return;
end;

c = min(A(:));
if c < 0,
    A = A + abs(c);
    fprintf([num2str(abs(c)) ' added to A.\n']);
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)
% finds saddle points
[m, n] = size(A);
maxPerColumn = max(A);
minPerRow = min(A, 2);
sp = [];
for r = 1:m,
    for c = 1:n,
        if A(r, c) == minPerRow(r) && A(r, c) == maxPerColumn(c),
            sp = [r c];
            return;
        end;
    end;
end;