Also found in: Wikipedia.
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 = ║aij║, where aij 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 i0 for which the maximum is achieved in
and player II strives to select a strategy j0 for which the minimum is achieved in
If v1 = v2, then the pair (i0, j0) constitutes a saddlepoint of the game, that is, the double inequality
aij0 ≤ a10j0 ≤ ai0j, i = 1, …, m, j = 1, …, n
is fulfilled. The number ai0j0 is called the value of the game, and the strategies i0 and j0 are called the optimal pure strategies of players I and II, respectively. If v1 ≠ V2, then v1 < v2 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 i0 = 2, j0 = 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).
REFERENCESMatrichnye igry. Edited by N. N. Vorob’ev. Moscow, 1961. (Collection of translated articles.)
Von Neumann, J., and O. Morgenstern. Teoriia igr i ekonomicheskoe povedenie. Moscow, 1970. (Translated from English.)
Owen, G. Teoriia igr. Moscow, 1971. (Translated from English.)
A. A. KORBUT