Section 5.2.5: Mixed strategies for matrix games

% Boyd & Vandenberghe "Convex Optimization"
% Joëlle Skaf - 08/24/05
%
% Player 1 wishes to choose u to minimize his expected payoff u'Pv, while
% player 2 wishes to choose v to maximize u'Pv, where P is the payoff
% matrix, u and v are the probability distributions of the choices of each
% player (i.e. u>=0, v>=0, sum(u_i)=1, sum(v_i)=1)

% Input data
randn('state',0);
n = 10;
m = 10;
P = randn(n,m);

% Optimal strategy for Player 1
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;

% Optimal strategy for Player 2
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;

% Displaying results
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!