Namespaces
Variants
Actions

Difference between revisions of "Minimax principle"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
(Category:Game theory, economics, social and behavioral sciences)
Line 1: Line 1:
 
{{TEX|done}}
 
{{TEX|done}}
An optimality principle for a [[Two-person zero-sum game|two-person zero-sum game]], expressing the tendency of each player to obtain the largest sure pay-off. The minimax principle holds in such a game $\Gamma=\langle A,B,H\rangle$ if the equality
+
An optimality principle for a [[two-person zero-sum game]], expressing the tendency of each player to obtain the largest sure pay-off. The minimax principle holds in such a game $\Gamma=\langle A,B,H\rangle$ if the equality
  
 
$$v=\max_{a\in A}\min_{b\in B}H(a,b)=\min_{b\in B}\max_{a\in A}H(a,b)\tag{*}$$
 
$$v=\max_{a\in A}\min_{b\in B}H(a,b)=\min_{b\in B}\max_{a\in A}H(a,b)\tag{*}$$
Line 6: Line 6:
 
holds, that is, if there are a value of the game, equal to $v$, and optimal strategies for both players.
 
holds, that is, if there are a value of the game, equal to $v$, and optimal strategies for both players.
  
For a [[Matrix game|matrix game]] and for certain classes of infinite two-person zero-sum games (see [[Infinite game|Infinite game]]) the minimax principle holds if mixed strategies are used. It is known that \ref{*} is equivalent to the inequalities (see [[Saddle point in game theory|Saddle point in game theory]]):
+
For a [[matrix game]] and for certain classes of infinite two-person zero-sum games (see [[Infinite game]]) the minimax principle holds if mixed strategies are used. It is known that \ref{*} is equivalent to the inequalities (see [[Saddle point in game theory|Saddle point in game theory]]):
  
 
$$H(a,b^*)\leq H(a^*,b^*)\leq H(a^*,b)$$
 
$$H(a,b^*)\leq H(a^*,b^*)\leq H(a^*,b)$$
Line 21: Line 21:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. von Neumann,  O. Morgenstern,  "Theory of games and economic behavior" , Princeton Univ. Press  (1947)  {{MR|21298}} {{ZBL|1112.91002}} {{ZBL|1109.91001}} {{ZBL|0452.90092}} {{ZBL|0205.23401}} {{ZBL|0097.14804}} {{ZBL|0053.09303}} {{ZBL|0063.05930}} </TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J. von Neumann,  O. Morgenstern,  "Theory of games and economic behavior" , Princeton Univ. Press  (1947)  {{MR|21298}} {{ZBL|1112.91002}} {{ZBL|1109.91001}} {{ZBL|0452.90092}} {{ZBL|0205.23401}} {{ZBL|0097.14804}} {{ZBL|0053.09303}} {{ZBL|0063.05930}} </TD></TR>
 +
</table>
 +
 
 +
[[Category:Game theory, economics, social and behavioral sciences]]

Revision as of 19:00, 8 November 2014

An optimality principle for a two-person zero-sum game, expressing the tendency of each player to obtain the largest sure pay-off. The minimax principle holds in such a game $\Gamma=\langle A,B,H\rangle$ if the equality

$$v=\max_{a\in A}\min_{b\in B}H(a,b)=\min_{b\in B}\max_{a\in A}H(a,b)\tag{*}$$

holds, that is, if there are a value of the game, equal to $v$, and optimal strategies for both players.

For a matrix game and for certain classes of infinite two-person zero-sum games (see Infinite game) the minimax principle holds if mixed strategies are used. It is known that \ref{*} is equivalent to the inequalities (see Saddle point in game theory):

$$H(a,b^*)\leq H(a^*,b^*)\leq H(a^*,b)$$

for all $a\in A$, $b\in B$, where $a^*$ and $b^*$ are the strategies on which the external extrema in \ref{*} are attained. Thus, the minimax principle expresses mathematically the intuitive conception of stability, since it is not profitable for either player to deviate from his optimal strategy $a^*$ (respectively, $b^*$). At the same time the minimax principle guarantees to player I (II) a gain (loss) of not less (not more) than the value of the game. An axiomatic characterization of the minimax principle for matrix games has been given (see [1]).

References

[1] E. Vilkas, "Axiomatic definition of the value of a matrix game" Theory Probabl. Appl. , 8 (1963) pp. 304–307 Teor. Veroyatnost. i Primenen. , 8 : 3 (1963) pp. 324–327 MR0154750 Zbl 0279.90044


Comments

The fact that the minimax principle holds if mixed strategies are allowed is called the minimax theorem; it is due to J. von Neumann.

References

[a1] J. von Neumann, O. Morgenstern, "Theory of games and economic behavior" , Princeton Univ. Press (1947) MR21298 Zbl 1112.91002 Zbl 1109.91001 Zbl 0452.90092 Zbl 0205.23401 Zbl 0097.14804 Zbl 0053.09303 Zbl 0063.05930
How to Cite This Entry:
Minimax principle. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Minimax_principle&oldid=32909
This article was adapted from an original article by E.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article