I tried to implement this linear problem using GLPK. When I tested it against rock-paper-scissors game (which has equilibrium in mixed strategies x=(1/3, 1/3, 1/3), y=(1/3, 1/3, 1/3) I've got infeasable solution.
I got back to MathProg to check if it would succeed. Unfortunately it also failed. I guess it is due to -1 values, since basic simplex method doesn't allow negative variables and requires some transformation to be done to get around it (though I thought it concerns only variables and GLPK does this automatically).
I've defined problem like this:
model for player 1:
set P1S;
set P2S;
param Payoff{P1S, P2S};
var y{P1S} >= 0;
minimize GameValue: sum{i in P1S} y[i];
s.t. Condition2{j in P2S}:
sum{i in P1S} Payoff[i,j] * y[i] >= 1;
solve;
printf "Value: %s\n", GameValue;
printf "Player 1 strategies:\n";
for{i in P1S}
printf "Found %s, actual %s\n", y[i], y[i]/GameValue;
end;
data:
data;
set P1S := r p s;
set P2S := r p s;
param Payoff
: r p s :=
r 0 -1 1
p 1 0 -1
s -1 1 0;
end;
I run it:
$ glpsol --model rps.mod --data rps.dat
GLPSOL: GLPK LP/MIP Solver, v4.54
Parameter(s) specified in the command line:
--model rps.mod --data rps.dat
Reading model section from rps.mod...
22 lines were read
Reading data section from rps.dat...
12 lines were read
Generating GameValue...
Generating Condition2...
Model has been successfully generated
GLPK Simplex Optimizer, v4.54
4 rows, 3 columns, 9 non-zeros
Preprocessing...
3 rows, 3 columns, 6 non-zeros
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 3
0: obj = 0.000000000e+00 infeas = 3.000e+00 (0)
LP HAS NO PRIMAL FEASIBLE SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
Time used: 0.0 secs
Memory used: 0.1 Mb (126428 bytes)
Is my guessing right and I can apply some easy workaround (e.g. set some flag)? Or is it something else that I messed up (wrote down the problem in a wrong way or overlooked something)?
EDIT:
After increasing each value of the matrix by constant 1 (making all values non-negative) I obtained correct solution (GameValue was also shifted by 1 so I could recover it by subtract it). Is it only valid in this case or will it break if (before running GLPK) I increase all parameters by constant to make them all non-negative? Is there some flag I can set in GLPK to do it automatically?
We are allowed to increase payoff matrix by constant to make all elements positive - it will make our GameValue increased by that constant as well (wiki).
So before delegating problem to the GLPK we should find the smallest element of the matrix (let say m), and calculate m' = min(m, 0). Then we should increment all elements by abs(m'), solve problem as usual, and obtained GameValue decrease by abs(m').
In both MathProg as well as GLPK it can be done manually (actually MathProg has nice min and abs functions for calculating parameters - see manual), but apparently there are no flags for it. This transformation doesn't change correctness of a NE problem but might affect correctness of other LP problems and we cannot take it for granted.