Disprove that the given strategy pair is a solution to the game.

Question

Problem: For the following matrix game, prove or disprove that the given strategy pair is a solution to the game.

\begin{align} A &= \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & 2 \\ -2 & 0 & 1 \end{bmatrix} \\ X_1 &= \left(\frac25,\frac15,\frac25\right)\\ Y_1 &= \left(\frac14,\frac12,\frac14\right) \end{align}

Answer(from book): Security level of $X_1$ is $-3/5$ and $Y_1$ is $0$. $X_1, Y_1$ is not a solution.

---

My work:

First I calculate $r=1-\min_{i,j}(a_{ij}) = 1-(-4)=5$

Then, I build my new matrix $a_{ij}+r$ with all coeficient greater than $0$. And the dual of this problem will be.

$$\max: y'_1+y'_2+y'_3$$

subject to \begin{align} 4 y'_1 + 7 y'_2+ y'_3&\le1\\ 8 y'_1+ y'_2+ 7 y'_3&\le1\\ 3 y'_1+ 5 y'_2+ 6 y'_3&\le1\\ y'_1,y'_2,y'_3 &\ge 0 \end{align}

The next picture show the solving process using LP assistant;

My question: I don't know where is my mistake to prove that the given x1 and y1 is not a solution. I didn't finish at the same optimal points of the given anwer. Any help, will be really apreciated. Thanks!

Answer 1

I've never took any course in game theory, so I'll explain it in a simple way. I hope an interested high school student without any background can understand.

You can skip this if you know the formulation

The question involves "a solution of a game" and "the security level of a strategy". For someone without any background, I'll first explain what they are.

To understand the "answer" in the quesiton, one has to know why the security levels of the solution of the game $(X^*,Y^*)$ has the same value.

Assumptions

• The game has two players $X$ and $Y$.
• $X$ can choose the rows of matrix $A$ to represent $X$'s strategy.
• $Y$ can choose $A$'s columns to represent $Y$'s strategy.
• $X$ doesn't know $Y$'s strategy, and vice versa.
• The $i,j$-th entry of matrix $A$ represents $X$'s payoff if players $X$ and $Y$ choose strategies $i$ and $j$ respectively.
• $X$ wants to maximise the $X$'s payoff (a.k.a. $Y$'s loss).
• $Y$ wants to minimise the $X$'s payoff.

Motivations from simple cases

To explain things in a simpler way, let's temporarily assume that each play will only choose one single pure strategy.

Let us think from player $X$'s point of view.

$$A = \begin{bmatrix} -1 & 2 & -3 & \ge -3 \\ 3 & -4 & 2 & \ge -4 \\ -2 & 0 & 1 & \ge -2 \\ \le 3 & \le 2 & \le 2 \end{bmatrix}$$

• If $X$ choose the first row (i.e. $X = (1,0,0)$), he will at least gain $-3$ because $\min(XA) = \min \begin{bmatrix} -1 & 2 & -3 \end{bmatrix} = -3$, so the security level of $X = (1,0,0)$ is $-3$.
• Similarly, the security levels of $X = (0,1,0)$ and $X = (0,0,1)$ are $-4$ and $-2$ respectively.

$X$ tends to choose $X = (0,0,1)$ to gain at least $-2$.

Let us think from player $Y$'s point of view.

• If $Y$ choose the first column (i.e. $Y = (1,0,0)$), he will at most lost $3$ because $\max(AY^T) = \max \begin{bmatrix} -1 & 3 & -2 \end{bmatrix}^T = 3$, so the security level of $Y = (1,0,0)$ is $3$.
• Similarly, the security levels of $Y = (0,1,0)$ and $Y = (0,0,1)$ are $2$ and $2$ respectively.

$Y$ tends to choose $Y = (0,0,1)$ or $Y = (0,1,0)$ to lose at most $2$.

Combining these two results, $X$ gains at least $-2$ and $Y$ loses (i.e. $X$ gains) at most $2$.

• Player $X$ wants to gain more (i.e. increase the lower bound of his gain).
• Player $Y$ wants to lose less (i.e. decrease the upper bound of his loss).

They will mix strategies with probabilities to improve the situation. Eventually, due to the Fundamental Theorem of Game Theory, the two bounds will eventuall agree.

Definitions

Solution of a game

If $X = (x_1,x_2,x_3)$ and $Y = (y_1,y_2,y_3)$ are their strategies, the expected value of the game is $$E(X,Y) = XAY^T = \sum_{i=1}^3\sum_{j = 1}^3 x_i a_{ij} y_j.$$

Since $\sum_{i=1}^3 x_i = \sum_{j=1}^3 y_j = 1$, adding a constant to $A$ will simply increase $E(X,Y)$ by a constant.

The solution of the game is a pair of strategies $(X^*,Y^*)$ such that for any X's strategy $X$ and Y's strategy $Y$, $$E(X^*,Y) \ge E(X^*,Y^*) \ge E(X,Y^*).$$

To understand this definition, given that player $Y$ adopts strategy $Y^*$, if $X$ adopts strategy $X \ne X^*$, from the above inequality, $$E(X^*,Y^*) \ge E(X,Y^*).$$ Therefore, provided that player $Y$ adopts $Y^*$, player $X$ should adopt $X^*$, and vice versa. Therefore, players $X$ and $Y$ agree at $(X^*,Y^*)$, which we want to find and we call "solution".

Value of a game

If the solution of a game is $(X^*,Y^*)$, then the value of the game is defined as $E(X^*,Y^*)$.

Security level of a strategy

Fix the strategy of player $X$ to $X$. We want to be sure how many points $X$ can gain at least. In other words, we want to find $\min_Y XAY^T$, which is called the security level of $X$. Similarly, the security level of $Y$ is $\max_X XAY^T$.

Security levels and the solution of the game

Thanks this fact, we only need to consider finitely many cases.

Lemma: For any $X$, $$\min_Y XAY^T = \min_{1 \le j \le n} XAe_j^T,$$ where $e_j$ is a $1$-by-$n$ row vector with $1$ in the $j$-th entry and with zero in the other entries.

Intuition: A weighted mean of a set of numbers bounded above by the maximum.

Proof: One side is trivial because the $Y$ on the LHS includes $e_j$ for all $j$. Suppose $j_0$ is an index such that $XAe_{j_0}^T = \min_{1 \le j \le n} XAe_j^T$.

$$XAY^T = \sum_{j = 1}^n XA y_j e_j^T \ge \sum_{j = 1}^n XA y_j e_{j_0}^T = \left(\sum_{j = 1}^n y_j \right) XAe_{j_0}^T = \min_{1 \le j \le n} XAe_j^T$$

Similarly, we have this lemma.

Lemma: For any $Y$, $$\max_X XAY^T = \max_{1 \le i \le m} e_i AY^T,$$ where $e_i$ is a $1$-by-$m$ row vector with $1$ in the $i$-th entry and with zero in the other entries.

Suppose that the solution of the game is $(X^*,Y^*)$. For any X's strategy $X$ and Y's strategy $Y$, $$E(X^*,Y) \ge E(X^*,Y^*) \ge E(X,Y^*).$$

Therefore, $$E(X^*,Y^*) = X^*A{Y^*}^T = \min_Y XAY^T = \min_{1 \le j \le n} XAe_j^T,$$ and similarly, $$E(X^*,Y^*) = X^*A{Y^*}^T = \max_X XAY^T = \max_{1 \le i \le m} e_i AY^T.$$

Hence, for a solution of a game $(X^*,Y^*)$, the security levels of $X^*$ and $Y^*$ are the same and are $E(X^*,Y^*) = X^*A{Y^*}^T$.

The book's "answer"

Hence, to check if $X_1$ and $Y_1$ are the solution of the game $A$, it suffices to calculate the security levels of $X_1$ and $Y_1$. If they don't agree, they aren't the solution of the game. To do this, we can the lemmas above.

\begin{align} X_1 A &= \begin{bmatrix} \frac25 & \frac15 & \frac25 \end{bmatrix} \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & 2 \\ -2 & 0 & 1 \end{bmatrix} = \begin{bmatrix} -\frac35 & 0 & -\frac25 \end{bmatrix} \\ AY_1^T &= \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & 2 \\ -2 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac14 \\ \frac12 \\ \frac14 \end{bmatrix} = \begin{bmatrix} 0 \\ -\frac34 \\ -\frac14 \end{bmatrix} \end{align}

\begin{align} \text{Security level of } X &= \min_{1 \le j \le n} XAe_j^T = \min \begin{bmatrix} -\frac35 & 0 & -\frac25 \end{bmatrix} = -\frac35 \\ \text{Security level of } Y &= \max_{1 \le i \le 3} e_i AY^T = \max \begin{bmatrix} 0 & -\frac34 & -\frac14 \end{bmatrix}^T = 0 \end{align}

So we conclude that $(X_1,Y_1)$ is not a solution of the game.

Find the solution of the game

I've point out where you made a mistake in my comment. The idea is right, it's just a careless mistake. Use the pivot elements at the same position in each step, and you'll get the optimal simplex tableau below. To save time, I'll post the GNU Octave code here. You may verify them online

format rat;
A0 = [-1 2 -3; 3 -4 2; -2 0 1];
A = [A0 + 5 eye(3)];
c = [1 1 1 0 0 0]'; b = [1 1 1]';
basis = [1 3 2]; B = A(:,basis); cB = c(basis);
T = [B\A B\b; cB'*(B\A)-c' cB'*(B\b)]
T =

          1          0          0     29/231     32/231    -47/231       2/33
          0          0          1    -37/231     -1/231     52/231       2/33
          0          1          0       9/77      -6/77       4/77       1/11
          0          0          0     19/231     13/231     17/231       7/33
basis = [1 2 3]; B = A(:,basis); cB = c(basis);
Y2 = B\b; X2 = T(4,4:6)';
x2 = X2 ./ T(4,7); y2 = Y2 ./ T(4,7); 
x2'*A0
ans =

       -2/7       -2/7       -2/7

A0*y2
ans =

       -2/7
       -2/7
       -2/7

x2'*A0*y2
ans = -2/7

References:

1. http://www.slideshare.net/leingang/lesson-35-game-theory-and-linear-programming
2. http://www.uobabylon.edu.iq/eprints/publication_9_23116_31.pdf