Security Games over Lexicographic Orders

Comments, Follow-up work and Supplementary material

For convenience of the reader, and also to easy playing around with variants of the implementation, we provide the full MATLABcode for the examples provided in Appendix B.1 of the work. It has been written and tested in Octave, version 5.2.0.

Download both scripts as ZIP file

Main script:

001 clear all 
002
003 %rand ("seed", 12345)   % uncomment this line to get repeatable results (specifically reproduce the numbers in the paper)
004
005 % Construct a game with randomly chosen equilibria
006 n = 5;  % number of strategies for player 1
007 m = 6;  % number of strategies for player 2
008 % number of desired equilibria
009 k1 = 2; 
010 k2 = 3;
011 % pick some random vectors to be equilibrium strategies
012 % for player 1
013 p = zeros(k1, n);
014 for i = 1:k1
015   aux = rand(1, n);
016   p(i,:) = aux / sum(aux);
017 endfor
018 % likewise, pick some random vectors to be 
019 % equilibrium strategies for player 2
020 q = zeros(k2, m);
021 for i = 1:k2
022   aux = rand(1, m);
023   q(i,:) = aux / sum(aux);
024 endfor
025 X = null(p)' 
026 Y = null(q)'
027
028 % now, pick a random matrix Z to "connect" X and Y
029 Z = rand(size(X,1), size(Y,1))
030
031 % this is the payoff for the first goal
032 A1 = X'*Z*Y
033
034 % we have (verifiably, up to numeric precision)
035 % X*p' == 0
036 % Y*q' == 0
037 % furthermore:
038 % q(i,:) * A1 == 0     for all i
039 % A1 * (p(i,:))' == 0  for all i
040
041 % this is X_(k-1)
042 eq11 = p;
043           
044 % this is Y_(k-1)
045 eq12 = q;
046
047 nk = size(eq11,1); % = size(eq12,1)
048           
049 % do the pairwise combination of equilibria to construct the next stage game
050 A2 = randi(5, size(A1)) % we pick a randomly payoff structure A2 for the second goal
051
052 % compute the payoff for the second goal (equation (1) in the paper)
053 B2 = eq11 * A2 * eq12';
054
055 % now, let us pick an arbitrary but fixed equilibrium in B2
056 % ...and compute the equilibrium using the standard linear programming
057 % LP for player 1
058 A = [ -B2'                 ones(size(B2,2),1) ;
059       ones(1,size(B2,1))  0                   ];
060 c = [zeros(size(B2,1),1); 1];
061 b = [zeros(size(B2,2),1); 1];
062 [xmax, fmax, status2, extra2] = glpk(c, A, b, [], [], 
063     [repmat("U", [1 size(b,1)-1]) "S"], 
064     [repmat("C", [1 size(c,1)])], -1);
065 % LP for player 2
066 [ymin, fmin, status, extra] = glpk(b, A', c, [], [], 
067     [repmat("L", [1 size(c,1)-1]) "S"], 
068     [repmat("C", [1 size(b,1)])], 1);
069
070 alpha = xmax(1:(size(c)-1))
071 beta = ymin(1:(size(b)-1))
072
073 % x1mix = x_k', y1mix = y_k' (in the paper)
074 x1mix = alpha' * eq11; %  = (alpha_k*)^T * X_(k-1)
075 y1mix = beta' * eq12; %  = Y_(k-1)^T * beta_k*
076
077 %%% Finally, for a humble/naive trial verification that (x1mix, y1mix) is really
078 %%% lex-optimal; note that a systematic search for a better solution would be just 
079 %%% what was done above anyway
080
081 % first, let us take player 1's view:
082 trials = 10000
083 disp('trial verification for player 1')
084 v1 = x1mix * A1 * y1mix';    % will always equal the (same) saddle point value 
085 v2 = x1mix * A2 * y1mix'; 
086
087 n = size(A1,1);
088 for i=1:trials 
089   if (i <= n) 
090     % try pure strategies as alternative first; are they optimal?
091     xalt = zeros(1, n);
092     xalt(i) = 1;
093   else 
094     % now, try random strategies; do we find a better one that computed above?
095     xalt = rand(1, n);
096     xalt = xalt / sum(xalt);
097   endif
098   v1alt = xalt * A1 * y1mix';
099   v2alt = xalt * A2 * y1mix';
100   
101   if (lexgt([v1alt v2alt], [v1 v2] + 1e-6))  % tolerance 1e-6 to account for numerical roundoff errors 
102     disp('found a better solution here:')  % if the computation is correct, this message should never show up
103     disp([v1 v1alt])
104     break
105   endif
106 endfor 
107
108 %%%%% now, from player 2's perspective
109 disp('trial verifications for player 2')
110 n = size(A1, 2);
111 for i=1:trials 
112   if (i <= n) 
113     % as before, let us try pure strategies first
114     yalt = zeros(1, n);
115     yalt(i) = 1;
116   else 
117     % and also try randomly mixed strategies to look for a better result
118     yalt = rand(1, n);
119     yalt = yalt / sum(yalt);
120   endif
121   v1alt = x1mix * A1 * yalt';
122   v2alt = x1mix * A2 * yalt';
123   % lex-<=-predicate computed by "a < c" <=> "-a > -c"
124   if (lexgt(-[v1alt v2alt], -[v1 v2] + 1e-6))   % include round-off errors
125     disp('found a better solution here:') % again, this should never be displayed if everything work's the right way
126     disp([v1 v1alt])
127     break
128   endif
129 endfor 
130
131 disp('done')
Helper function to compute the lexicographic order (called above in lines 101 and 124); file "lexgt.m":

01  function result = lexgt(x,y) 
02    n = size(x,2);
03    if (n == 1) 
04      result = (x(1) > y(1));
05      return
06    endif
07    if (x(1) > y(1)) 
08      result = 1;
09      return
10    else 
11      if (x(1) < y(1)) 
12        result = 0;
13      else
14        result = lexgt(x(2:n), y(2:n));
15      endif
16    endif
17  endfunction