Section 5.2.5: Mixed strategies for matrix games
randn('state',0);
n = 10;
m = 10;
P = randn(n,m);
fprintf(1,'Computing the optimal strategy for player 1 ... ');
cvx_begin
variable u(n)
minimize ( max ( P'*u) )
u >= 0;
ones(1,n)*u == 1;
cvx_end
fprintf(1,'Done! \n');
obj1 = cvx_optval;
fprintf(1,'Computing the optimal strategy for player 2 ... ');
cvx_begin
variable v(m)
maximize ( min (P*v) )
v >= 0;
ones(1,m)*v == 1;
cvx_end
fprintf(1,'Done! \n');
obj2 = cvx_optval;
disp('------------------------------------------------------------------------');
disp('The optimal strategies for players 1 and 2 are respectively: ');
disp([u v]);
disp('The expected payoffs for player 1 and player 2 respectively are: ');
[obj1 obj2]
disp('They are equal as expected!');
Computing the optimal strategy for player 1 ...
Calling SDPT3: 21 variables, 11 equality constraints
------------------------------------------------------------
num. of constraints = 11
dim. of linear var = 20
dim. of free var = 1 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|2.8e+01|9.0e+00|4.5e+02| 1.437979e-10| 0:0:00| chol 1 1
1|0.934|0.874|1.9e+00|1.2e+00|5.5e+01| 2.209773e-02| 0:0:00| chol 1 1
2|1.000|0.982|9.2e-07|3.2e-02|6.9e+00| 3.330082e-01| 0:0:00| chol 1 1
3|1.000|0.502|8.0e-07|1.7e-02|2.8e+00|-5.128516e-01| 0:0:00| chol 1 1
4|0.836|0.757|3.0e-06|4.1e-03|8.1e-01|-1.308434e-01| 0:0:00| chol 1 1
5|1.000|0.154|1.5e-07|3.6e-03|6.7e-01|-1.363386e-01| 0:0:00| chol 1 1
6|1.000|0.552|7.4e-08|1.6e-03|4.0e-01|-4.539742e-02| 0:0:00| chol 1 1
7|0.732|0.680|5.1e-08|5.2e-04|1.4e-01|-9.442017e-04| 0:0:00| chol 1 1
8|1.000|0.227|6.9e-09|4.0e-04|9.4e-02|-3.892950e-03| 0:0:00| chol 1 1
9|1.000|0.505|7.2e-09|2.0e-04|4.6e-02| 1.083435e-02| 0:0:00| chol 1 1
10|0.938|0.739|1.5e-09|5.2e-05|1.2e-02| 2.328138e-02| 0:0:00| chol 1 1
11|0.969|0.534|1.4e-10|2.4e-05|5.1e-03| 2.547030e-02| 0:0:00| chol 1 1
12|1.000|0.849|4.6e-11|3.7e-06|7.6e-04| 2.748632e-02| 0:0:00| chol 1 1
13|0.988|0.980|2.0e-12|1.0e-05|1.6e-05| 2.784832e-02| 0:0:00| chol 1 1
14|1.000|0.989|3.4e-14|2.1e-07|3.5e-07| 2.785579e-02| 0:0:00| chol 1 1
15|1.000|0.989|1.3e-14|4.7e-09|6.5e-09| 2.785588e-02| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 15
primal objective value = 2.78558807e-02
dual objective value = 2.78558744e-02
gap := trace(XZ) = 6.54e-09
relative gap = 6.19e-09
actual relative gap = 5.97e-09
rel. primal infeas = 1.29e-14
rel. dual infeas = 4.69e-09
norm(X), norm(y), norm(Z) = 7.8e-01, 5.4e-01, 1.0e+00
norm(A), norm(b), norm(C) = 1.2e+01, 2.0e+00, 2.4e+00
Total CPU time (secs) = 0.3
CPU time per iteration = 0.0
termination code = 0
DIMACS: 1.3e-14 0.0e+00 5.7e-09 0.0e+00 6.0e-09 6.2e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.0278559
Done!
Computing the optimal strategy for player 2 ...
Calling SDPT3: 21 variables, 11 equality constraints
------------------------------------------------------------
num. of constraints = 11
dim. of linear var = 20
dim. of free var = 1 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|3.0e+01|1.0e+01|5.0e+02|-1.437979e-10| 0:0:00| chol 1 1
1|0.950|0.898|1.5e+00|1.1e+00|5.1e+01|-4.126547e-01| 0:0:00| chol 1 1
2|1.000|0.977|6.9e-07|3.5e-02|6.7e+00| 2.377477e-01| 0:0:00| chol 1 1
3|1.000|0.305|7.0e-07|2.5e-02|3.3e+00|-7.337621e-01| 0:0:00| chol 1 1
4|1.000|0.700|4.6e-06|7.6e-03|1.2e+00|-2.652953e-01| 0:0:00| chol 1 1
5|0.899|0.325|6.1e-07|5.1e-03|7.7e-01|-2.677782e-01| 0:0:00| chol 1 1
6|1.000|0.313|1.9e-07|3.5e-03|6.1e-01|-1.875588e-01| 0:0:00| chol 1 1
7|1.000|0.364|5.5e-08|2.2e-03|4.0e-01|-1.385436e-01| 0:0:00| chol 1 1
8|1.000|0.520|2.3e-08|1.1e-03|1.9e-01|-8.814715e-02| 0:0:00| chol 1 1
9|0.940|0.582|5.9e-09|4.5e-04|7.5e-02|-5.641711e-02| 0:0:00| chol 1 1
10|1.000|0.189|1.0e-09|3.8e-04|6.1e-02|-5.199254e-02| 0:0:00| chol 1 1
11|1.000|0.666|1.7e-10|1.3e-04|2.2e-02|-3.649244e-02| 0:0:00| chol 1 1
12|1.000|0.762|5.5e-11|3.0e-05|5.0e-03|-3.001714e-02| 0:0:00| chol 1 1
13|1.000|0.535|6.8e-12|1.4e-05|2.2e-03|-2.891959e-02| 0:0:00| chol 1 1
14|0.999|0.935|2.2e-12|9.1e-07|1.4e-04|-2.792693e-02| 0:0:00| chol 1 1
15|0.989|0.988|1.4e-13|1.9e-06|1.9e-06|-2.785675e-02| 0:0:00| chol 1 1
16|1.000|0.989|4.4e-15|2.5e-08|3.9e-08|-2.785589e-02| 0:0:00| chol 1 1
17|1.000|0.989|7.3e-16|5.3e-10|7.3e-10|-2.785588e-02| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 17
primal objective value = -2.78558788e-02
dual objective value = -2.78558795e-02
gap := trace(XZ) = 7.35e-10
relative gap = 6.96e-10
actual relative gap = 6.69e-10
rel. primal infeas = 7.27e-16
rel. dual infeas = 5.26e-10
norm(X), norm(y), norm(Z) = 1.0e+00, 4.4e-01, 7.8e-01
norm(A), norm(b), norm(C) = 1.2e+01, 2.0e+00, 2.4e+00
Total CPU time (secs) = 0.3
CPU time per iteration = 0.0
termination code = 0
DIMACS: 7.3e-16 0.0e+00 6.3e-10 0.0e+00 6.7e-10 7.0e-10
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.0278559
Done!
------------------------------------------------------------------------
The optimal strategies for players 1 and 2 are respectively:
0.1804 0.0000
0.0000 0.3254
0.0000 0.0924
0.1549 0.0000
0.1129 0.0000
0.0000 0.0264
0.0000 0.4099
0.1003 0.0509
0.1474 0.0949
0.3040 0.0000
The expected payoffs for player 1 and player 2 respectively are:
ans =
0.0279 0.0279
They are equal as expected!