Optimization (D2) DPK

Easter 2005

4. GAME THEORY

4.1 Saddle points of two-person zero-sum games

We consider a game with two players. Player I can choose one of m strategies, indexed by i = 1, …, m and Player II can choose one of n strategies, indexed by j = 1, …, n; if Player I plays strategy i and Player II plays strategy j the payoff to Player I is a_{i,j} and the game is zero-sum in that what Player I wins Player II loses. The payoff matrix A = (a_{i,j}) is given, and known to each player. For example, consider the game in which Player I has 3 choices of strategy and Player II has 4 and the payoff matrix is:

A = ( \begin{matrix}3 & 4 & 1 & −2 \\ 2 & 5 & 2 & 4 \\ −5 & 2 & 1 & 0 \end{matrix} ).

To analyze the game, consider the worst outcome that can happen for Player I if he picks each of his strategies 1, 2 or 3. Looking along row 1 we see that the minimum he can get, if II picks option 4, is −2; if I picks 2 his worst possibility is 2, which occurs when II picks 1 or 3, and if I picks 3, his worst is −5 when II picks 1. These are illustrated below, and if we consider similarly the worst possibilities for Player II, we get the column maxima in the table.

Player I chooses i

Player II chooses j

Strategy  1 2 3 4 Row min
1  3 4 1 −2  −2
2  2 5 2 4  2  ←
3  −5 2 1 0  −5
Col. max  3 5 2 4

↑

By taking the maximum of the row minima we see that Player I is guaranteed not to get less than the amount 2 by choosing strategy 2, while, by considering the minimum of the column maxima, Player II is guaranteed not to lose more than 2 by choosing his strategy 3. The upshot is that they will settle on the (2,3) element which is worth 2 to Player I (−2 to Player II) and either player may be worse off if they deviate from the strategies indicated. The amount that they settle on, here 2, is known as the value of the game and the element (2,3) of the matrix is a saddle point. The matrix has a saddle point when min_{j} max_{i} a_{i,j} = max_{i} min_{j} a_{i,j}. It is always the case that min_{j} max_{i} a_{i,j} ⩾ max_{i} min_{j} a_{i,j} but not all matrices have a saddle point as the next example below illustrates.

For the row player I, we say that strategy i dominates strategy i′ if a_{i,j} ⩾ a_{i′,j} for all j = 1, …, n; for the column player II, strategy j dominates strategy j′ if a_{i,j} ⩽ a_{i,j′} for all i = 1, …, m. A player will never play a strategy that is dominated by another (except possibly in the special case where the payoffs are identical for all outcomes). In the example above, for the row player strategy, 2 dominates 3, while for the column player strategies 1 and 3 dominate 2.

Example 4.1 Undercut In a version of the game Undercut, each player selects a number from 1, 2, 3, 4. The players reveal their numbers and the player with the smaller number wins £2, unless the numbers are either adjacent, when the player with the larger number wins £1, or equal, when the game is tied with payoff zero. The payoff matrix is

Strategy  1 2 3 4 Row min
1  0 −1 2 2  −1
2  1 0 −1 2  −1
3  −2 1 0 −1  −2
4  −2 −2 1 0  −2
Col. max  1 1 2 2

Since all the row minima are negative and all the column maxima are positive there can be no saddle point. This is an example of a symmetric game; its payoff matrix is an anti-symmetric matrix, that is A = −A^{⊤}.

4.2 Mixed strategies

In order to study games for which there is no saddle point, we widen the sets of strategies available to each player. A mixed strategy for Player I is a set of probabilities

40 p = (p_{1}, …, p_{m})^{⊤}, where p_{1}, …, p_{m} ⩾ 0, and ∑_{i=1}^{m} p_{i} = 1; if Player I uses the mixed strategy p he chooses row i with probability p_{i}. A mixed strategy for Player II is a set of probabilities q = (q_{1}, …, q_{n})^{⊤}, where q_{1}, …, q_{n} ⩾ 0, and ∑_{j=1}^{n} q_{j} = 1 with the analogous interpretation. The expected payoff to Player I if Player II uses j is ∑_{i} p_{i}a_{i,j}, so Player I seeks to

maximize [min_{j} ∑_{i=1}^{m} p_{i}a_{i,j}] subject to ∑_{i=1}^{m} p_{i} = 1, p_{i} ⩾ 0, 1 ⩽ i ⩽ m.

This problem is equivalent to

P: maximize v subject to ∑_{i=1}^{m} p_{i}a_{i,j} ⩾ v, 1 ⩽ j ⩽ n, ∑_{i=1}^{m} p_{i} = 1, p_{i} ⩾ 0, 1 ⩽ i ⩽ m.

If we write e = (1, 1, …, 1)^{⊤} (we will use the same notation, e, for vectors of lengths m and n with all components equal to 1 – it will be clear from the context which is meant), then this problem may be written in matrix form as

P: maximize v subject to A^{⊤}p ⩾ ve, e^{⊤}p = 1, p ⩾ 0.

This is of course a linear programming problem and it is easy to see that the dual problem is Player II’s problem as he will wish to solve

D: minimize v subject to ∑_{j=1}^{n} a_{i,j}q_{j} ⩽ v, 1 ⩽ i ⩽ m, ∑_{j=1}^{n} q_{j} = 1, q_{j} ⩾ 0, 1 ⩽ j ⩽ n,

which in matrix form is

D: minimize v subject to Aq ⩽ ve, e^{⊤}q = 1, q ⩾ 0.

Theorem 4.2 If \overline{p}, \overline{q} and \overline{v} satisfy:

A^{⊤}\overline{p} ⩾ \overline{v}e, e^{⊤}\overline{p} = 1, \overline{p} ⩾ 0 (primal feasibility)
A\overline{q} ⩽ \overline{v}e, e^{⊤}\overline{q} = 1, \overline{q} ⩾ 0 (dual feasibility)
\overline{v} = \overline{p}^{⊤}A\overline{q}  (complementary slackness)

then \overline{p} and \overline{q} are optimal for P and D respectively, and \overline{v}, the common value of the two problems, is the value of the game. Proof. This is just Lagrangian sufficiency again. Suppose that v, p are feasible for P and w, q are feasible for D, then

v ⩽ v + q^{⊤} (A^{⊤}p − ve)^{⊤} = qA^{⊤}p = w + p^{⊤} (Aq − we) ⩽ w,

with equality throughout if we have v = w = \overline{v}, p = \overline{p} and q = \overline{q} since we have complementary slackness, which (along with e^{⊤}\overline{p} = 1 = e^{⊤}\overline{q}) is equivalent to

\overline{q}^{⊤} (A^{⊤}\overline{p} − \overline{v}e) = 0 = \overline{p}^{⊤} (A\overline{q} − \overline{v}e) ,

which completes the argument. □

Remark The necessity part of the duality result for the pair of linear programming problems P and D is of course also true: that is, for any matrix A there exist \overline{p}, \overline{q} and \overline{v} satisfying the conditions of Theorem 4.2. This fact is sometimes known as the Fundamental Theorem of Matrix Games, but as we have seen it is just a consequence of linear programming duality. It’s conclusion is also equivalent to the statement that

min_{q} max_{p} p^{⊤}Aq = max_{p} min_{q} p^{⊤}Aq,

where the minimum is over q ⩾ 0, e^{⊤}q = 1 and the maximum over p ⩾ 0, e^{⊤}p = 1.

4.3 Finding solutions for games

There are several approaches to tackling the problem of finding solutions to games:

1. Direct solution of a player’s optimization problem For small matrices it may be possible to solve one of the players problems directly;

for example, consider the payoff matrix

( \begin{matrix}2 & 3 & 4 \\ 3 & 1 & \frac{1}{2} \\ 1 & 3 & 2 \end{matrix} ) .

42 For Player 1 it is clear that row 1 dominates row 3 so that an optimal row strategy will put no weight on row 3, and if we let p_{1} = p, p_{2} = 1 − p, p_{3} = 0 the problem becomes one of trying to find the maximum v such that v and p satisfy

\begin{matrix}2p + 3(1 − p) = 3 − p & ⩾ v, \\ 3p + (1 − p) = 1 + 2p & ⩾ v, \\ 4p + \frac{1}{2}(1 − p) = \frac{1}{2} + \frac{7}{2}p & ⩾ v, 0 ⩽ p ⩽ 1. \end{matrix}

Plotting the three lines as functions of p gives

.................................................................................................................................................................................................................................................................................................................................. ............................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................. •  p 1 v . . . . . . . . . . . . ..............._{\frac{2}{3}}  3 − p 1 + 2p \frac{1}{2} + \frac{7}{2} p  ..................................................................................................................................

which shows that the largest value of v is when the first two lines meet (at p = \frac{2}{3}) giving v = \frac{7}{3}. Thus we have the optimal strategy for Player I is (\frac{2}{3}, \frac{1}{3}, 0). Notice that the line \frac{1}{2} + \frac{7}{2}p is strictly greater that v at p = \frac{2}{3}, thus Player II’s optimal strategy must be of the form (q, 1 − q, 0) and looking at the top row we get (using complementary slackness) that 2q + 3(1 − q) = v = \frac{7}{3} which gives q = \frac{2}{3}.

2. Determining strategies satisfying the conditions of the Theorem In some cases features of the matrix may be used to help determine strategies which

may be checked to be optimal using the sufficient conditions of the Theorem. For example, for the Undercut game introduced above the matrix is

( \begin{matrix}0 & −1 & 2 & 2 \\ 1 & 0 & −1 & 2 \\ −2 & 1 & 0 & −1 \\ −2 & −2 & 1 & 0 \end{matrix} ) ,

and since the game is symmetric (A = −A^{⊤}) the value is necessarily 0 and any strategy optimal for Player I must also be optimal for Player II. Suppose that p = (p_{1}, p_{2}, p_{3}, p_{4})^{⊤} is an optimal strategy, then if p_{1} > 0, complementary slackness will give (from the first row)

−p_{2} + 2p_{3} + 2p_{4} = 0 or − p_{2} + 2(1 − p_{1} − p_{2}) = 0  (1)

which gives p_{2} = 2(1 − p_{1})/3. If p_{2} > 0, we would have from the second row,

p_{1} − p_{3} + 2p_{4} = 0 or p_{1} − p_{3} + 2(1 − p_{1} − p_{2} − p_{3}) = 0,  (2)

which gives p_{3} = (2 + p_{1})/9, after using the expression for p_{2}. Similarly, from the third row, if p_{3} > 0, we must have

−2p_{1} + p_{2} − p_{4} = 0,  (3)

and we deduce that p_{4} = (2 − 8p_{1})/3. But we also have p_{4} = 1 − p_{1} − p_{2} − p_{3} which gives p_{4} = (1 − 4p_{1})/9. Equating the two expressions for p_{4} shows that we must have p_{1} = \frac{1}{4}. This proves p = (\frac{1}{4}, \frac{1}{2}, \frac{1}{4}, 0) is an optimal strategy and it is the unique optimal strategy since its first three components are strictly positive, the argument above shows that any optimal strategy must satisfy (1), (2) and (3) which has only one solution.

3. Using linear programming Although Player I’s problem is a linear programming problem, it is not immediately

in a form to which we could apply the simplex algorithm because v is unconstrained in sign. However, if we add a constant c > − min_{i,j} a_{i,j}, to each element of the matrix A, all the elements of A may be taken as positive, and we can assume that v > 0; this will not change the optimal strategies and will just add c to the value. Now set x_{i} = p_{i}/v and the row player’s problem which is

maximize v subject to A^{⊤}p ⩾ ve, e^{⊤}p = 1, p ⩾ 0,

becomes

maximize v subject to A^{⊤}x ⩾ e, e^{⊤}x = 1/v, x ⩾ 0,

which is equivalent to

minimize e^{⊤}x subject to A^{⊤}x ⩾ e, x ⩾ 0.

44 This may now be tackled using the simplex algorithm. The column player’s problem may be reduced in the same way, by putting y_{i} = q_{i}/v, to

maximize e^{⊤}y subject to Ay ⩽ e, y ⩾ 0;

this latter problem is somewhat simpler to solve by this method as it does not require the use of the Phase I procedure to find an initial b.f.s. as the row player’s problem would.

Consider the Undercut game and add 3 to each element to obtain the matrix

( \begin{matrix}3 & 2 & 5 & 5 \\ 4 & 3 & 2 & 5 \\ 1 & 4 & 3 & 2 \\ 1 & 1 & 4 & 3 \end{matrix} );

setting up the tableau (with slack variables z_{1}, z_{2}, z_{3}, z_{4}) we have

* * * *
y_{1} y_{2} y_{3} y_{4} z_{1} z_{2} z_{3} z_{4}
z_{1}  3 2 5 5 1 0 0 0 1
z_{2} 4 3 2 5 0 1 0 0 1
z_{3}  1 4 3 2 0 0 1 0 1
z_{4}  1 1 4 3 0 0 0 1 1
Payoff 1 1 1 1 0 0 0 0 0
↑

Then a sequence of pivots as indicated, gives

∗ ∗ ∗ ∗
y_{1} y_{2} y_{3} y_{4} z_{1} z_{2} z_{3} z_{4}
z_{1}  0 −\frac{1}{4}  \frac{7}{2}  \frac{5}{4} 1 −\frac{3}{4} 0 0 \frac{1}{4}
y_{1}  1 \frac{3}{4}  \frac{1}{2}  \frac{5}{4} 0 \frac{1}{4} 0 0 \frac{1}{4}
z_{3}  0 \frac{13}{4}  \frac{5}{2}  \frac{3}{4} 0 −\frac{1}{4} 1 0 \frac{3}{4}
z_{4}  0 \frac{1}{4}  \frac{7}{2}  \frac{7}{4} 0 −\frac{1}{4} 0 1 \frac{3}{4}
Payoff 0 \frac{1}{4}  \frac{1}{2} −\frac{1}{4} 0 −\frac{1}{4} 0 0 −\frac{1}{4}
↑
∗ ∗ ∗ ∗
y_{1} y_{2} y_{3} y_{4} z_{1} z_{2} z_{3} z_{4}
z_{1}  0 0 \frac{48}{13}  \frac{17}{13} 1 −\frac{10}{13}  \frac{1}{13} 0 \frac{4}{13}
y_{1}  1 0 −\frac{1}{13}  \frac{14}{13} 0 \frac{4}{13} −\frac{3}{13} 0 \frac{1}{13}
y_{2}  0 1 \frac{10}{13}  \frac{3}{13} 0 −\frac{1}{13}  \frac{4}{13} 0 \frac{3}{13}
z_{4}  0 0 \frac{43}{13}  \frac{22}{13} 0 −\frac{3}{13} −\frac{1}{13} 1 \frac{9}{13}
Payoff 0 0 \frac{4}{13} −\frac{4}{13} 0 −\frac{3}{13} −\frac{1}{13} 0 −\frac{4}{13}
↑

The final pivot, bringing in y_{3} and dropping z_{1}, gives the optimal solution

∗ ∗ ∗  ∗
y_{1} y_{2} y_{3} y_{4} z_{1} z_{2} z_{3} z_{4}
y_{3}  0 0 1 \frac{17}{48}  \frac{13}{48} −\frac{5}{24}  \frac{1}{48} 0 \frac{1}{12}
y_{1}  1 0 0 \frac{53}{48}  \frac{1}{48}  \frac{7}{24} −\frac{11}{48} 0 \frac{1}{12}
y_{2}  0 1 0 −\frac{1}{24} −\frac{5}{24}  \frac{1}{12}  \frac{7}{24} 0 \frac{1}{6}
z_{4}  0 0 0 \frac{25}{48} −\frac{43}{48}  \frac{11}{24} −\frac{7}{48} 1 \frac{5}{12}
Payoff 0 0 0 −\frac{5}{12} −\frac{1}{12} −\frac{1}{6} −\frac{1}{12} 0 −\frac{1}{3}

The optimal value of the linear programming problem is \frac{1}{3}, which means the value of the game is 3 (remember we added 3 to all the components of the original symmetric game whose value was 0). We can read off the optimal solution y_{1} = \frac{1}{12}, y_{2} = \frac{1}{6}, y_{3} = \frac{1}{12} and y_{4} = 0. These values must be scaled by the value 3 to get the optimal strategy q_{1} = \frac{1}{4}, q_{2} = \frac{1}{2}, q_{3} = \frac{1}{4} and q_{4} = 0, as we had obtained before. Remarks

1. Notice the symmetry between the payoff row and the right-hand side in the final tableau; minus the entries in the payoff row are the optimal solution to the dual problem–because of the symmetry of the original game the optimal solutions to the primal and dual are the same, one giving the row player’s strategy, the other the column player’s. For any game, when we solve one player’s problem by linear programming, we may identify the other player’s optimal strategy from the final payoff row.

2. It is clear from this section that solving a game by linear programming may not be tractable by hand except for the smallest problems. However, for larger problems and with the aid of a computer, it may be the only way to fly.

6 April 2005

46