Namespaces
Variants
Actions

Difference between revisions of "Minimax principle"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
(TeX)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639501.png" /> if the equality
+
{{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
  
<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/m063/m063950/m0639502.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639503.png" />, 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 (*) is equivalent to the inequalities (see [[Saddle point in game theory|Saddle point in game theory]]):
+
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]]):
  
<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/m063/m063950/m0639504.png" /></td> </tr></table>
+
$$H(a,b^*)\leq H(a^*,b^*)\leq H(a^*,b)$$
  
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639505.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639506.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639507.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639508.png" /> are the strategies on which the external extrema in (*) 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m0639509.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m063/m063950/m06395010.png" />). 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 [[#References|[1]]]).
+
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 [[#References|[1]]]).
  
 
====References====
 
====References====

Revision as of 12:20, 14 August 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=28249
This article was adapted from an original article by E.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article