Question

Matrix Games:

If we are given an arbitrary I by J matrix A, there exists a greater than 0 so that the matrix B with entries Bij = Aij + a has only positive entries. Show that any optimal randomized probability vectors for the game with pay-off matrix B are also optimal for the game with pay-off matrix A.

Answer 1

Answer on Question#37193 - Math - Other

If we are given an arbitrary $I \times J$ matrix $A$, there exists $a > 0$ so that the matrix $B$ with entries $B_{ij} = A_{ij} + a$ has only positive entries. Show that any optimal randomized probability vectors for the game with pay-off matrix $B$ are also optimal for the game with pay-off matrix $A$.

Solution:

Suppose that vectors

$$\overline{x} = (x_1; x_2; \ldots; x_I), \quad \overline{y} = (y_1; y_2; \ldots; y_J),$$

are optimal randomized probability ones for the game with pay-off matrix $B$. Thus (by the definition of an optimal randomized probability vector)

$$\sum_{i=1}^{I} x_i = 1, \quad \sum_{j=1}^{J} y_j = 1.$$

If vectors $\overline{x}, \overline{y}$ are optimal randomized probability ones then

$$v_B = v_B^\beta = \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} B_{ij} x_i y_j = \max_{\overline{x}} \min_{\overline{y}} \sum_{i=1}^{I} \sum_{j=1}^{J} B_{ij} x_i y_j = v_B^\alpha$$

where $v_B$ is a value of the game with pay-off matrix $B$.

Thus we have

$$\begin{aligned} v_A^\beta &= \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} A_{ij} x_i y_j = \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} (B_{ij} - a) x_i y_j = \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} B_{ij} x_i y_j - \\ &- \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} a x_i y_j = v_B - a \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} \sum_{j=1}^{J} x_i y_j = v_B - a \min_{\overline{y}} \max_{\overline{x}} \sum_{i=1}^{I} x_i \sum_{j=1}^{J} y_j = \\ &= v_B - a \min_{\overline{y}} \max_{\overline{x}} (1 \cdot 1) = v_B - a. \end{aligned}$$

By analogy

$$v_A^\alpha = v_B - a.$$

Because

$$v_A^\beta = v_B - a = v_A^\alpha$$

thus the game with pay-off matrix $A$ has the value

$$v_A = v_B - a$$

and vectors

$$\overline{x} = (x_1; x_2; \ldots; x_I), \quad \overline{y} = (y_1; y_2; \ldots; y_J),$$

are optimal randomized probability ones for the game with pay-off matrix $A$.