% function [x, y, value] = zsumextformlp(A, a, B, b, R)
%
% Solve a zero-sum extensive form game from its sequence
% representation.  Find x and y such that
%
%   Ax = a,  x >= 0
%   By = b,  y >= 0
%   x = arg max y' * R * x
%   y = arg min y' * R * x
%
% where (A,a) represent player 1's sequences, (B,b) represent player
% 2's sequences, and R is the reward matrix.  Works by converting to a
% linear program and solving using iqph().
%
% The linear program is
%
%   minimize b'z subject to
%   Rx + B'z >= 0
%   x >= 0
%   Ax = a

function [x, y, value] = zsumextformlp(A, a, B, b, R)

[n, m] = size(R);
k = length(a);
l = length(b);

obj = [zeros(m,1); -b];
[val, primals, duals, eduals] = iqph([], obj, [R B'; eye(m) zeros(m,l)], ...
				     zeros(n+m, 1), [A zeros(k,l)], -a);

x = primals(1:m);
y = duals(1:n);

if (nargout > 2)
  value = val;
end


% This is an equivalent formulation of the LP with player 2 as the
% primal variables.
%
% obj = [zeros(m,1); -a];
% [val, primals, duals, eduals] = iqph([], obj, [-R' A'; eye(n) ...
%		    zeros(n,k)], zeros(n+m, 1), [B zeros(l,k)], -b);
% yy=primals(1:n);
% xx=duals(1:m);