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 sedumi: 21 variables, 11 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 11, order n = 23, dim = 23, blocks = 2
nnz(A) = 130 + 0, nnz(ADA) = 121, nnz(L) = 66
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 7.25E+00 0.000
1 : -3.56E-01 3.20E+00 0.000 0.4411 0.9000 0.9000 2.38 1 1 5.8E+00
2 : -3.05E-02 1.49E+00 0.000 0.4661 0.9000 0.9000 4.41 1 1 1.3E+00
3 : -2.17E-02 4.60E-01 0.000 0.3087 0.9000 0.9000 1.54 1 1 3.2E-01
4 : -2.93E-02 1.25E-01 0.000 0.2719 0.9000 0.9000 1.09 1 1 8.1E-02
5 : -2.82E-02 2.48E-02 0.000 0.1980 0.9000 0.9000 1.06 1 1 1.7E-02
6 : -2.79E-02 4.80E-03 0.000 0.1937 0.9000 0.9000 1.02 1 1 3.2E-03
7 : -2.79E-02 3.40E-05 0.000 0.0071 0.9990 0.9797 1.00 1 1 3.2E-05
8 : -2.79E-02 5.46E-12 0.000 0.0000 1.0000 1.0000 1.00 1 1 7.4E-12
iter seconds digits c*x b*y
8 0.0 10.7 -2.7855878953e-02 -2.7855878954e-02
|Ax-b| = 2.4e-12, [Ay-c]_+ = 1.2E-12, |x|= 1.1e+00, |y|= 4.4e-01
Detailed timing (sec)
Pre IPM Post
1.000E-02 4.000E-02 0.000E+00
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.94695.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.0278559
Done!
Computing the optimal strategy for player 2 ...
Calling sedumi: 21 variables, 11 equality constraints
For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 11, order n = 23, dim = 23, blocks = 2
nnz(A) = 130 + 0, nnz(ADA) = 121, nnz(L) = 66
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 7.25E+00 0.000
1 : -3.21E-01 3.14E+00 0.000 0.4336 0.9000 0.9000 2.39 1 1 5.7E+00
2 : -1.32E-02 1.43E+00 0.000 0.4552 0.9000 0.9000 4.37 1 1 1.1E+00
3 : 1.20E-02 4.28E-01 0.000 0.2993 0.9000 0.9000 1.53 1 1 2.9E-01
4 : 2.63E-02 1.13E-01 0.000 0.2648 0.9000 0.9000 1.09 1 1 7.2E-02
5 : 2.74E-02 2.30E-02 0.000 0.2028 0.9000 0.9000 1.05 1 1 1.5E-02
6 : 2.77E-02 4.44E-03 0.000 0.1929 0.9000 0.9000 1.01 1 1 2.9E-03
7 : 2.79E-02 1.27E-05 0.000 0.0029 0.9990 0.9990 1.00 1 1 1.5E-05
8 : 2.79E-02 1.80E-12 0.000 0.0000 1.0000 1.0000 1.00 1 1 2.1E-12
iter seconds digits c*x b*y
8 0.0 11.1 2.7855878954e-02 2.7855878954e-02
|Ax-b| = 9.4e-13, [Ay-c]_+ = 1.0E-13, |x|= 9.0e-01, |y|= 5.4e-01
Detailed timing (sec)
Pre IPM Post
0.000E+00 4.000E-02 0.000E+00
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.62822.
------------------------------------------------------------
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!