Matrix game

A two-person zero-sum game in which each player possesses only a finite number of pure strategies. If player I possesses $ m $ strategies and player II possesses $ n $ strategies, then the matrix game can be given by an $ ( m \times n ) $- matrix $ A = \| a _ {ij} \| $, where $ a _ {ij} $, $ i = 1 \dots m $, $ j = 1 \dots n $, is the payoff of player I if (s)he chooses strategy $ i $ while player II chooses strategy $ j $. According to the general optimality principle in two-person zero-sum games (see also Minimax principle), player I tends to choose a strategy $ i _ {0} $ on which

$$ \max _ { i } \min _ { j } a _ {ij} = \underline{v} $$

is attained, whereas player II tends to choose a strategy $ j _ {0} $ on which

$$ \min _ { j } \max _ { i } a _ {ij} = \overline{v}\; $$

is attained. If $ \underline{v} = \overline{v}\; $, then the pair $ ( i _ {0} , j _ {0} ) $ is called a saddle point (cf. Saddle point in game theory) of the game; the number $ a _ {i _ {0} j _ {0} } $ is called the value of the game, and the strategies $ i _ {0} , j _ {0} $ are optimal pure strategies. If $ \underline{v} \neq \overline{v}\; $( i.e. a pure strategy solution does not exist), then always $ \underline{v} < \overline{v}\; $. In this case one must seek the optimal strategies of the players among their mixed strategies (cf. Strategy (in game theory)). Let $ X \subset \mathbf R ^ {m} $( respectively, $ Y \subset \mathbf R ^ {n} $) be the set of mixed strategies of player I (respectively, player II). Then players I and II will tend to choose the strategies $ x ^ \star $ and $ y ^ \star $ on which

$$ \underline{v} ^ \star = \max _ {x \in X } \min _ {y \in Y } xAy ^ {T} $$

and

$$ \overline{v}\; {} ^ \star = \min _ {y \in Y } \max _ {x \in X } xAy ^ {T} $$

are attained, respectively (the superscript $ {} ^ {T} $ denotes transposition). The main theorem in the theory of matrix games (von Neumann's minimax theorem) asserts that $ \underline{v} ^ \star = \overline{v}\; {} ^ \star = v $, i.e. for every matrix game there are optimal mixed strategies $ x ^ \star , y ^ \star $ and a value $ v $ of the game.

For the numerical solution of matrix games (i.e. for finding optimal strategies and the value of the game) one most frequently uses the fact that the problem of solving a matrix game can be reduced to a linear programming problem. A less efficient approach is the Brown–Robinson iterative method, which amounts to "playing" fictitiously the matrix game so that at each step the players choose the best pure strategies under an "accumulated" mixed strategy of the opponent. Matrix games in which one of the players has only two strategies are readily solved using graphical methods.

Matrix games serve as mathematical models of many of the simplest conflict situations in the areas of economics, mathematical statistics, war science, and biology. In applications, the role of one of the players is sometimes assigned to "nature" , by which one understands the totality of external circumstances which are unknown to the decision maker (the other player).

References

[1]	J.M. Dresher, "Games of strategy: theory and practice" , Prentice-Hall (1961)
[2]	J. von Neumann, O. Morgenstern, "Theory of games and economic behavior" , Princeton Univ. Press (1947)
[3]	H.G. Owen, "Game theory" , Saunders (1968)
[4]	N.N. Vorob'ev, "Game theory. Lectures for economists and system scientists" , Springer (1977) (Translated from Russian)

Comments

The theory of matrix games is divided into zero-sum and non-zero-sum games. Two-person non-zero-sum matrix games are usually referred to as bimatrix games, cf. Bimatrix game.

References

[a1]	S. Karlin, "Matrix games, programming and mathematical economics" , 1–2 , Addison-Wesley (1959)