%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Example of computation of Stackelberg strategies for
% bimatrix games.
%
% Author: K. Passino
% Version: 2/5/02
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all
% Set the number of different possible values of the decision variables
m=5; % If change will need to modify specific J1 value chosen below
n=3;
% Set the payoff matrices J1(i,j) and J2(i,j):
% For generating random bimatrix games:
J1=round(10*rand(m,n)-5*ones(m,n)) % Make it random integers between -5 and +5
J2=round(10*rand(m,n)-5*ones(m,n)) % Make it random integers between -5 and +5
% These can be used to find other equilibria. For instance, if you use the following two
% payoff matrices then you will get uniqueness in the response of P2.
J1 =[4 1 -4;
-2 5 3;
-3 2 -1;
4 4 4;
-3 -5 2]
J2 =[2 -1 0;
-2 4 0;
-3 0 -1;
-3 3 4;
-3 0 -5]
% One set of payoff matrices that for i=4 by P1 gives two possible responses from the follower P2
% that both achieve minimum loss for P2.
J1 =[-1 5 -3;
-2 5 1;
4 3 -2;
-5 -1 5;
3 0 2]
J2 =[-1 2 -3;
2 -3 1;
-2 3 1;
-1 1 -1;
4 -4 1]
% Compute the Stackelberg strategy:
% First, find follower reactions (note that this just finds the min loss by P2, so it can
% be that more than one P2 strategy results in this loss):
for i=1:m
minJ2(i)=min(J2(i,:)); % Finds the minimum loss of P2 given the leader P1 chooses i
end
P1loss=-inf*ones(1,m); % Initialization so that it will pick the first min value above it
jstar=0*ones(1,m); % Initialization to nonvalid values (valid ones picked next)
for i=1:m
for j=1:n
if J2(i,j)==minJ2(i) % Test that j corresponds to a min point for P2, for a given i
if J1(i,j)>=P1loss(i) % Tests if it is above any previously stored value for the loss
% (this finds the security value against all possible P2 rational reactions)
P1loss(i)=J1(i,j); % Keeps the value to compare to any other possible P2 reactions later
jstar(i)=j; % Save the index of the reaction of P2 that results in worst loss for P1 if it uses i
end
end
end
end
% Specify the Stackelberg strategy:
[stackelbergcost,istar]=min(P1loss) % Display the P1 Stackelberg strategy and cost
jstar(istar) % Display the P2 follower strategy
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Do another example:
clear all
% Define payoff (cost) functions for each player
theta1=-4:0.05:4; % Ok, while we think of it as an infinite game computationally
% we of course only study a finite number of points.
m=length(theta1);
theta2=-5:0.05:5;
n=length(theta2);
% A set of cost functions, J1 for player 1 and J2 for player 2
for ii=1:length(theta1)
for jj=1:length(theta2)
J1(ii,jj)=-2*(exp( (-(theta1(ii)-2)^2)/5 +(-4*(theta1(ii)*theta2(jj))/20) + ((-(theta2(jj)-3)^2)/2)));
J2(ii,jj)=-1*(exp( (-(theta1(ii)-1)^2)/4 + (5*(theta1(ii)*theta2(jj))/10) + ((-(theta2(jj)+1)^2)/2)));
end
end
% Next, compute the reaction curves for each player and will plot on top of J1 and J2
for j=1:length(theta2)
[temp,t1]=min(J1(:,j)); % Find the min point on J1 with theta2 fixed, for all theta2
R1(j)=theta1(t1); % Compute the theta1 value that is the best reaction to each theta2
end
for i=1:length(theta1)
[temp,t2]=min(J2(i,:)); % Find the min point on J2 with theta1 fixed
R2(i)=theta2(t2); % Compute the theta2 value that is the best reaction to each theta1
end
% Compute the Stackelberg strategy:
% First, find follower reactions (note that this just finds the min loss by P2, so it can
% be that more than one P2 strategy results in this loss):
for i=1:m
minJ2(i)=min(J2(i,:)); % Finds the minimum loss of P2 given the leader P1 chooses i
end
P1loss=-inf*ones(1,m); % Initialization so that it will pick the first min value above it
jstar=0*ones(1,m); % Initialization to nonvalid values (valid ones picked next)
for i=1:m
for j=1:n
if J2(i,j)==minJ2(i) % Test that j corresponds to a min point for P2, for a given i
if J1(i,j)>=P1loss(i) % Tests if it is above any previously stored value for the loss
% (this finds the security value against all possible P2 rational reactions)
P1loss(i)=J1(i,j); % Keeps the value to compare to any other possible P2 reactions later
jstar(i)=j; % Save the index of the reaction of P2 that results in worst loss for P1 if it uses i
end
end
end
end
% Specify the Stackelberg strategy:
[stackelbergcost,istar]=min(P1loss) % Display the P1 Stackelberg strategy and cost
jstar(istar) % Display the P2 follower strategy
theta1(istar)
theta2(jstar(istar))
figure(1)
clf
contour(theta2,theta1,J1,14)
hold on
contour(theta2,theta1,J2,14)
hold on
plot(theta2,R1,'k-')
hold on
plot(R2,theta1,'k--')
hold on
plot(theta2(jstar(istar)),theta1(istar),'x')
xlabel('\theta^2')
ylabel('\theta^1')
title('J_1, J_2, R_1 (-), R_2 (--), "x" marks Stackelberg solution')
hold off
%-------------------------------------
% End of program
%-------------------------------------