Security Games over Lexicographic Orders
For convenience of the reader, and also to easy playing around with
variants of the implementation, we provide the full MATLAB
code 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