Namespaces
Variants
Actions

Minimax principle

From Encyclopedia of Mathematics
Revision as of 15:57, 14 February 2020 by Ivan (talk | contribs) (label)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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)\label{*}\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 \eqref{*} 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 \eqref{*} 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=34361
This article was adapted from an original article by E.B. Yanovskaya (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article