Matrix Games

a concept in game theory. Matrix games are games played by two players (I and II) with opposing interests, each player having a finite number of pure strategies. If player I has m strategies and player II has n strategies, then the game may be defined by the (m × n) matrix A = ║a_ij║, where a_ij is the payoff paid to player I by player II if player I selects strategy i (i = 1, …, m) and player II selects strategy j (j = 1, …, n). Player I, following the general principles of behavior in zero-sum games (of which the matrix game is a particular case) strives to select a strategy i₀ for which the maximum is achieved in

and player II strives to select a strategy j₀ for which the minimum is achieved in

If v₁ = v₂, then the pair (i₀, j₀) constitutes a saddlepoint of the game, that is, the double inequality

a_ij0 ≤ a_10j0 ≤ a_i0j, i = 1, …, m, j = 1, …, n

is fulfilled. The number a_i0j0 is called the value of the game, and the strategies i₀ and j₀ are called the optimal pure strategies of players I and II, respectively. If v₁ ≠ V₂, then v₁ < v₂ always. In this case, no saddlepoint exists in the game, and the optimal strategies of the players must be found from among their mixed strategies (that is, probability distributions on the set of pure strategies). In this case, the players’ choice of strategies are determined by the mathematical expectations of the payoffs.

The principal theorem of the theory of matrix games—the minimax theorem of von Neumann—asserts that in any matrix game there exist optimal mixed strategies x^*, y^* for which the achieved “minimaxes” are equal (their common value is the value of the game). For example, a game with matrix

has a saddlepoint with i₀ = 2, j₀ = 1, and the value of the game is equal to 2. A game with matrix

has no saddlepoint; the optimal mixed strategies for it are x* = (¾, ¼), y* = (½, ½), and the value of the game is ½.

The possibility of reducing a matrix game to linear programming problems is most often used to actually find the optimal mixed strategies. It is possible to use what is called the Brown-Robinson iteration method, which consists of successive fictitious “playing out” of the given game during which each player in turn selects his own pure strategies that would have been optimal against the strategies selected by the opponent up to this time. Games in which one of the players has only two strategies are solved simply by graphs.

Matrix games can be used as mathematical models of many simple situations of conflict in economics, mathematical statistics, military science, and biology. Often “nature” is considered as one of the players, where by “nature” is understood the entire set of external facts unknown to the individual undertaking a solution (who is considered as the other player).