Namespaces
Variants
Actions

Difference between revisions of "Matrix game"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A [[Two-person zero-sum game|two-person zero-sum game]] in which each player possesses only a finite number of pure strategies. If player I possesses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628201.png" /> strategies and player II possesses <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628202.png" /> strategies, then the matrix game can be given by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628203.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628204.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628205.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628206.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628207.png" />, is the payoff of player I if (s)he chooses strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628208.png" /> while player II chooses strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m0628209.png" />. According to the general optimality principle in two-person zero-sum games (see also [[Minimax principle|Minimax principle]]), player I tends to choose a strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282010.png" /> on which
+
<!--
 +
m0628201.png
 +
$#A+1 = 29 n = 0
 +
$#C+1 = 29 : ~/encyclopedia/old_files/data/M062/M.0602820 Matrix game
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282011.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
is attained, whereas player II tends to choose a strategy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282012.png" /> on which
+
A [[Two-person zero-sum game|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|Minimax principle]]), player I tends to choose a strategy $  i _ {0} $
 +
on which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282013.png" /></td> </tr></table>
+
$$
 +
\max _ { i }  \min _ { j }  a _ {ij}  = \underline{v}
 +
$$
  
is attained. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282014.png" />, then the pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282015.png" /> is called a saddle point (cf. [[Saddle point in game theory|Saddle point in game theory]]) of the game; the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282016.png" /> is called the value of the game, and the strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282017.png" /> are optimal pure strategies. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282018.png" /> (i.e. a pure strategy solution does not exist), then always <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282019.png" />. In this case one must seek the optimal strategies of the players among their mixed strategies (cf. [[Strategy (in game theory)|Strategy (in game theory)]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282020.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282021.png" />) be the set of mixed strategies of player I (respectively, player II). Then players I and II will tend to choose the strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282023.png" /> on which
+
is attained, whereas player II tends to choose a strategy  $  j _ {0} $
 +
on which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282024.png" /></td> </tr></table>
+
$$
 +
\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|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)|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
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282025.png" /></td> </tr></table>
+
$$
 +
\overline{v}\; {}  ^  \star  = \min _ {y \in Y }  \max _ {x \in X }  xAy  ^ {T}
 +
$$
  
are attained, respectively (the superscript <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282026.png" /> denotes transposition). The main theorem in the theory of matrix games (von Neumann's minimax theorem) asserts that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282027.png" />, i.e. for every matrix game there are optimal mixed strategies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282028.png" /> and a value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062820/m06282029.png" /> of the game.
+
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|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.
 
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|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.
Line 23: Line 68:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.M. Dresher,  "Games of strategy: theory and practice" , Prentice-Hall  (1961)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. von Neumann,  O. Morgenstern,  "Theory of games and economic behavior" , Princeton Univ. Press  (1947)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H.G. Owen,  "Game theory" , Saunders  (1968)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.N. Vorob'ev,  "Game theory. Lectures for economists and system scientists" , Springer  (1977)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.M. Dresher,  "Games of strategy: theory and practice" , Prentice-Hall  (1961)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J. von Neumann,  O. Morgenstern,  "Theory of games and economic behavior" , Princeton Univ. Press  (1947)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  H.G. Owen,  "Game theory" , Saunders  (1968)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.N. Vorob'ev,  "Game theory. Lectures for economists and system scientists" , Springer  (1977)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 08:00, 6 June 2020


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)
How to Cite This Entry:
Matrix game. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matrix_game&oldid=47795
This article was adapted from an original article by A.A. Korbut (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article