Exam 16

Exercise 16. Consider the following bimatrix game:

$$C_1 =\left\lbrack \begin{array}{ccc} 9 & 7 & 3\\ 8 & 4 & 1\\ 5 & 3 & 2 \end{array}\right\rbrack$$

$$C_2 =\left\lbrack \begin{array}{ccc} 8 & 3 & 1\\ 9 & 6 & 5\\ 1 & 4 & 2 \end{array}\right\rbrack$$

close all;
clear;
clc;

matlab.lang.OnOffSwitchState = 1;

16.1 Find strictly dominated strategies (if any) and reduce the cost matrices accordingly.

This game is two-person non-cooperative game where the sets of pure strategies are finite, hence the sets of mixed stratergies are $X=\left\lbrace x;\epsilon ;\Re^m :x\ge 0,\sum_{i=1}^m x_i =1\right\rbrace ;$ and $Y=\left\lbrace y;\epsilon ;\Re^n :y\ge 0,\sum_{j=1}^n y_j =1\right\rbrace$ . $f_{2;} \not= -f_1$ (non-zero sum game), the cost functions are $f_1 \left(x,y\right)=x^T C_1 y$ and $f_2 \left(x,y\right)=x^T C_2 y$ , where $C_1$ and $C_2$ are $m\times n$ matrices.

16.2 Do pure strategies Nash equilibria exist? Why?

16.3 Evaluate the gap function at the point (x, y), where x = (1/3, 2/3) and y = (1/4, 3/4), in order to check if it is a Nash equilibrium.

16.4 Plot the polyhedra P and Q related to the game and find all the mixed strategies Nash equilibria.

16.5 Find the KKT multipliers related to the mixed strategies Nash equilibrium.

In game theory, The Karush-Kuhn-Tucker conditions are a set of necessary conditions for an optimization problem with contraints to have a solution.

syms x1 x2 x3 y1 y2 y3 mu1 mu2
C1 = [9 7 3
      8 4 1
      5 3 2];

C2 = [8 3 1
      9 6 5
      1 4 2]';

row_player = [x1
              x2
              x3];

column_player = [y1
                 y2
                 y3];

p = m*n*3 + 2;
equations = [];

for i = 1:m
    equations = [ equations
                  C1(i,:) * (column_player) + mu1 >= 0
                  row_player(i) >= 0
                  row_player(i)*(C1(i,:) * (column_player) + mu1) == 0];
end 

for i = 1:n
    equations = [ equations
                  C2(i,:) * (row_player) + mu2 >= 0 
                  column_player(i) >= 0
                  column_player(i)*(C2(i,:) * (row_player) + mu2) == 0];
end 

equations = [ equations
              row_player(1) + row_player(2) + row_player(3) == 1
              column_player(1) + column_player(2) + column_player(3)== 1 ]

variables = [x1, x2, x3, y1, y2, y3, mu1, mu2]
[x1, x2, x3, y1, y2, y3, mu1, mu2] = solve(equations,variables)

Output

$$\begin{array}{l} \left(\begin{array}{c} 0\le \sigma_1 \\ 0\le x_1 \\ x_1 ,\sigma_1 =0\\ 0\le \sigma_4 \\ 0\le x_2 \\ x_2 ,\sigma_4 =0\\ 0\le \sigma_2 \\ 0\le x_3 \\ x_3 ,\sigma_2 =0\\ 0\le \sigma_5 \\ 0\le y_1 \\ y_1 ,\sigma_5 =0\\ 0\le \sigma_3 \\ 0\le y_2 \\ y_2 ,\sigma_3 =0\\ 0\le \sigma_6 \\ 0\le y_3 \\ y_3 ,\sigma_6 =0\\ x_1 +x_2 +x_3 =1\\ y_1 +y_2 +y_3 =1 \end{array}\right)\\ \mathrm{}\\ \textrm{where}\\ \mathrm{}\\ \ \ \sigma_1 =\mu_1 +9,y_1 +7,y_2 +3,y_3 \\ \mathrm{}\\ \ \ \sigma_2 =\mu_1 +5,y_1 +3,y_2 +2,y_3 \\ \mathrm{}\\ \ \ \sigma_3 =\mu_2 +3,x_1 +6,x_2 +4,x_3 \\ \mathrm{}\\ \ \ \sigma_4 =\mu_1 +8,y_1 +4,y_2 +y_3 \\ \mathrm{}\\ \ \ \sigma_5 =\mu_2 +8,x_1 +9,x_2 +x_3 \\ \mathrm{}\\ \ \ \sigma_6 =\mu_2 +x_1 +5,x_2 +2,x_3 \end{array}$$

$$\left(\begin{array}{cccccccc} x_1 \left(1\right) & x_2 \left(1\right) & x_3 \left(1\right) & y_1 \left(1\right) & y_2 \left(1\right) & y_3 \left(1\right) & \mu_1 \left(1\right) & \mu_2 \left(1\right) \end{array}\right)=\left(\begin{array}{cccccccc} 0 & 0 & 1 & 1 & 0 & 0 & -5 & -1 \end{array}\right)$$

$$\left(\begin{array}{cccccccc} x_1 \left(2\right) & x_2 \left(2\right) & x_3 \left(2\right) & y_1 \left(2\right) & y_2 \left(2\right) & y_3 \left(2\right) & \mu_1 \left(2\right) & \mu_2 \left(2\right) \end{array}\right)=\left(\begin{array}{cccccccc} 0 & 1 & 0 & 0 & 0 & 1 & -1 & -5 \end{array}\right)$$

$$\left(\begin{array}{cccccccc} x_1 \left(3\right) & x_2 \left(3\right) & x_3 \left(3\right) & y_1 \left(3\right) & y_2 \left(3\right) & y_3 \left(3\right) & \mu_1 \left(3\right) & \mu_2 \left(3\right) \end{array}\right)=\left(\begin{array}{cccccccc} 0 & \frac{1}{5} & \frac{4}{5} & \frac{1}{4} & 0 & \frac{3}{4} & -\frac{11}{4} & -\frac{13}{5} \end{array}\right)$$