Game theory

Explanation

• A two-person game is one with exactly two players. It is zero-sum when the sum of the losses for one player equals the sum of the gains for the other, so whatever one player wins the other loses and no value is created or destroyed.
• The pay-off matrix records the outcome of every pair of choices, and unless a question says otherwise it is always written from the row player's point of view: the entry in row $i$ and column $j$ is what the row player gains when the row player chooses strategy $i$ and the column player chooses strategy $j$.
• A negative entry therefore means the row player loses that amount.
• Because the game is zero-sum, the column player's own matrix is obtained by changing the sign of every entry and then transposing, so a single matrix carries all the information.
• The row player wants large entries and the column player wants small ones, which is why the two players read the same table in opposite directions.

Explanation

• A player plays safe by choosing the strategy whose worst outcome is as good as possible. For the row player, who gains the entries, the worst outcome of a row is its smallest entry, so the play-safe strategy is the row whose minimum is largest; that largest row minimum is called the row maximin.
• For the column player, who loses the entries, the worst outcome of a column is its largest entry, so the play-safe strategy is the column whose maximum is smallest; that smallest column maximum is the column minimax. The row maximin is never greater than the column minimax.
• The game has a stable solution if and only if the two are equal, and the common value is then the value of the game.
• The cell where they meet is called a saddle point: its entry is the smallest in its row and the largest in its column, so neither player can gain by moving away from it alone.
• When the row maximin is strictly less than the column minimax there is no stable solution and the game must be solved with mixed strategies.

Explanation

• A row of a pay-off matrix is dominated if some other row is at least as good in every column and strictly better in at least one; since the row player is choosing between them with no information about the column, the dominated row can never be needed and may be deleted.
• For the column player the comparison runs the other way, because the column player prefers small entries: a column is dominated if some other column is at least as small in every row and strictly smaller in at least one, and again it may be deleted.
• Deleting rows and columns alternately can reduce a large matrix to one small enough for the graphical method or even to a single cell.
• Dominance must be checked entry by entry against one other row or column at a time, and the comparison must be stated: an examiner expects "row 2 is dominated by row 1 because $4<5$, $1<2$ and $2<3$", not merely "row 2 is dominated".
• Deletion never removes an optimal strategy, because any mixed strategy using a dominated row can be improved by moving that probability to the dominating row.

Explanation

• When a game has no saddle point, each player uses a mixed strategy, choosing between the pure strategies at random with fixed probabilities. If the row player has only two strategies, let $p$ be the probability of playing row 1, so row 2 has probability $1-p$.
• Against column $j$ the expected pay-off is a linear function of $p$,
• so each column gives a straight line on a graph with $p$ running from $0$ to $1$. The row player's guarantee for a given $p$ is the lowest of those lines, so the optimal $p$ is where the lower envelope is highest, which is at the intersection of the two lines that meet there.
• Solving that pair of equations gives $p$ and the value of the game. If instead the column player has only two strategies, let $q$ be the probability of column 1; each row gives a line, the column player's exposure is the highest of them, and the optimal $q$ minimises the upper envelope.
• The graphical method needs one of the players to have exactly two strategies, so a game with three or more strategies each way must first be reduced by dominance or converted to a linear program. The specification limits the graphical method to $2\times n$ or $n\times2$ games where $n=1$, $2$, $3$ or $4$.

Explanation

• A game too large for the graphical method is solved by turning it into a linear program. Work from the row player's point of view, with probabilities $p_1,\dots,p_m$ summing to $1$ and a value $V$.
• The row player wants to make $V$ as large as possible subject to the expected pay-off against every single column being at least $V$, that is $\sum_i a_{ij}p_i\geqslant V$ for each column $j$.
• If any entry of the matrix is negative then $V$ could be negative, which the simplex algorithm cannot handle, so first add a constant $k$ to every entry, large enough to make them all positive; this raises the value of the game by exactly $k$ and changes nothing else, so $k$ is subtracted at the end.
• Writing the objective as $P=V$ and each column constraint as $V-\sum_i a_{ij}p_i\leqslant0$, together with $p_1+\dots+p_m=1$ and $p_i\geqslant0$, gives a linear program in $m+1$ variables that the simplex algorithm solves.
• The column player's optimal strategy is read from the final tableau, or found separately by the same construction applied to the transposed, sign-changed matrix.