Min-Max Theorem

The Min-Max theorem is a fundamental solution concept in game theory and is sometimes referred to as the main theorem for 2-person zero-sum games . The Min imierung the opponent Max imal payout of both players is paramount and is the cause for the origin of the name Min-Max -Theorem. Alternatively, the Min-Max theorem is referred to in the relevant literature as the Maximin solution. The basis for the dual definition of terms is the fact that in zero-sum games the minimization of the opponent's maximum payout (Minimax) corresponds to both the minimization of your own maximum loss and the maximization of your own minimum payout (Maximin).

Game theory formulation

The main clause for 2-person zero-sum games includes:

In the mixed extension of every 2-person zero-sum game with finite (pure) strategy spaces A and B, there is a constant V and for each player at least one (mixed) equilibrium strategy or with which he can guarantee an expected payout of at least V. ${\displaystyle (X,Y,G^{\prime })}$ ${\displaystyle x^{*}}$ ${\displaystyle y^{*}}$

For player A there is an with and such that . ${\displaystyle x^{*}=\lbrace x_{1}^{*},...x_{\text{i}}^{*},...x_{\text{m}}^{*}\rbrace }$ ${\displaystyle x_{\text{i}}^{*}\geq 0}$ ${\displaystyle \sum _{i=1}^{m}x_{\text{i}}^{*}=1\quad }$ ${\displaystyle \quad \max \limits _{x}}$ ${\displaystyle \min \limits _{y}}$ ${\displaystyle G^{\prime }{\bigl (}x,y{\bigr )}\ =\min \limits _{y}}$ ${\displaystyle G^{\prime }{\bigl (}x^{*},y{\bigr )}=V}$

For player B there is an with and so that . ${\displaystyle y^{*}=\lbrace y_{1}^{*},...y_{\text{j}}^{*},...y_{\text{n}}^{*}\rbrace }$ ${\displaystyle y_{\text{j}}^{*}\geq 0}$ ${\displaystyle \sum _{j=1}^{n}y_{\text{j}}^{*}=1\quad }$ ${\displaystyle \quad \min \limits _{y}}$ ${\displaystyle \max \limits _{x}}$ ${\displaystyle G^{\prime }{\bigl (}x,y{\bigr )}\ =\max \limits _{x}}$ ${\displaystyle G^{\prime }{\bigl (}x,y^{*}{\bigr )}=V}$

classification

In the following it is assumed that both players follow the minimax criterion, that is, they choose the mixed strategy which maximizes the minimum expected payout for themselves (and consequently minimizes the maximum expected loss). The set guarantees both players an expected profit V in finite two-person zero-sum games, provided that they choose the mixed strategy that is optimal according to the minimax criterion. This pair of Maximin and Minimax strategies means that neither player can improve their own position by changing their strategy unilaterally. The minimax algorithm , which is also based on the minimax strategy, is used in contrast to the min-max theorem in the field of sequential games.

The sentence was first proven by John von Neumann in 1928 in his publication "On the theory of parlor games".

The resulting combination of strategies for both players forms a saddle point, which is a special case of the Nash equilibrium for two-person zero-sum games. Linear optimization is used to determine this equilibrium strategy in very complex zero-sum games.

Consequently, if player A plays rationally, depending on player B's choice of strategy, he can expect at least the amount V, and if he plays rationally, player B can achieve that player A does not win more than this amount on average.

General procedure

A 2-person zero-sum game in matrix form can be represented as follows ( bimatrix ):

		Player B:
		s 1 ${\displaystyle _{B}}$	s 2 ${\displaystyle _{B}}$	⋯	s n-1 ${\displaystyle _{B}}$	s n ${\displaystyle _{B}}$
Player A:
	s 1 ${\displaystyle _{A}}$	u 1.1	u 1.2	⋯	u 1, n-1	u 1, n
	s 2 ${\displaystyle _{A}}$	u 2.1	u 2.2	⋯	u 2, n-1	u 2, n
	⋮	⋮	⋮		⋮	⋮
	s m-1 ${\displaystyle _{A}}$	u m-1.1	u m-1.2	⋯	u m-1, n-1	u m-1, n
	s m ${\displaystyle _{A}}$	u m, 1	u m, 2	⋯	u m, n-1	u m, n

Player A is the row player and player B is the column player. The game is viewed from the perspective of player A, with the row and the column denoted in the strategy vector . The payoff is in the matrix cells so that the payout of player A equals the loss of player B. ${\displaystyle s=(s_{A},s_{B})}$ ${\displaystyle s_{A}}$ ${\displaystyle s_{B}=s_{A}}$ ${\displaystyle u_{A}(s)=-u_{B}(s)}$

Player A first chooses a strategy (row), being aware that the opponent will always choose the minimum payout in the row that player A has given. Accordingly, player A specifies the strategy (line) in which the line minimum is maximum (maximin strategy), so that the optimization rule for player A is: ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$

${\displaystyle {\underset {s_{A}}{\max }}[{\underset {s_{B}}{\min }}\;u_{A}(s_{A},s_{B})]}$

This guarantees him a minimum payout, no matter what player B does. Player B tries to minimize his losses and chooses a strategy (column) that fulfills exactly the opposite condition ( minimax rule , minimax strategy), so that the optimization rule for player B is: ${\displaystyle s_{B}}$

${\displaystyle {\underset {s_{B}}{\min }}[{\underset {s_{A}}{\max }}\;u_{A}(s_{A},s_{B})]}$

Consequently, through his minimax strategy, he can limit player A's payout to at most equal to this amount, regardless of what player A does. The following applies accordingly:

${\displaystyle {\underset {s_{A}}{\max }}[{\underset {s_{B}}{\min }}\;u_{A}(s_{A},s_{B})]}$ ${\displaystyle \leq }$ ${\displaystyle {\underset {s_{B}}{\min }}[{\underset {s_{A}}{\max }}\;u_{A}(s_{A},s_{B})]}$

The main theorem for 2-person zero-sum games implies that these two optimal strategies have a common value v, so that the necessary and sufficient condition for the value (equilibrium, saddle point) is: ${\displaystyle v}$

${\displaystyle {\underset {s_{A}}{\max }}[{\underset {s_{B}}{\min }}\;u_{A}(s_{A},s_{B})]\;=\;{\underset {s_{B}}{\min }}[{\underset {s_{A}}{\max }}\;u_{A}(s_{A},s_{B})]}$.

Player A, if he plays intelligently, can therefore expect a minimum payout, and if he plays intelligently, player B can cause player A to win no more than the minimum payout.

example

In the following, the Min-Max theorem will be clarified in a tennis game. In the bimatrix , the payouts have been replaced by the corresponding success rates of the two players for each of their pure strategies. Player A serves first.

		Player B:
		forehand	Backhand
Player A:	forehand	50	80
	Backhand	90	20th

Since the interests of the two players are exactly opposite, player B will try to return the ball successfully and to minimize the maximum success rate of her opponent (minimax strategy). With this prior knowledge, player A will try to maximize his own minimum success rate (Maximin strategy).
In this example the minimum success rate of player A for each of his pure strategies in the line forehand 50 and backhand 20. The maximum of these minima (maximin) is therefore 50 and guarantees him the greatest possible success if he is 100% on the forehand plays, insofar as player B returns as well as possible in her own interests. Player A would choose the forehand strategy.
Player B's maximum success rate for each of her strategies is 90 in the forehand and 80 backhand column. The minimum of these maxima (minimax) is 80 and guarantees her the greatest possible success, provided that player A returns as best as possible in his own interests. Player B would choose the backhand.

		Player B:
		forehand	Backhand	Line min
Player A:	forehand	50	80	50 (maximin)
	Backhand	90	20th	20th
	Column max	90	80 (minimax)

The minmax and maxmin values ​​of the two tennis players are different: Maximin player A (50%) <Minimax player B (80%).

Accordingly, this game has no balance (saddle point) in pure strategies, because each of the two players can improve their position by mixing the pure strategies forehand and backhand and weaken the opponent's success rate, since the correct position is no longer predictable.

The strategy sets that arise for the two players from the mix of their pure strategies are first considered from the perspective of player A. He plays forehand with probability and backhand with probability . The -Mix indicates, for each of the pure strategies of player B, the expected success of player A for his mixed strategy. ${\displaystyle p}$ ${\displaystyle (1-p)}$ ${\displaystyle p}$

		Player B:
		forehand	Backhand	Line min
Player A:	forehand	50	80	50
	Backhand	90	20th	20th
	p mix	50p + 90 (1 - p)	80p + 20 (1 - p)	min =?

If player B plays forehand, player A's success rate is the same as for backhand . The probability is calculated as follows. ${\displaystyle 50p+90(1-p)}$ ${\displaystyle 80p+20(1-p)}$ ${\displaystyle p}$

${\displaystyle 50p+90(1-p)=80p+20(1-p)}$

${\displaystyle 70(1-p)=30p}$

${\displaystyle 70=100p}$

${\displaystyle p=0,7}$ → expected success rate: ${\displaystyle 50*0,7+90(1-0,7)=62}$

The strategy sets are now viewed from player B's perspective. She plays forehand with probability and backhand with probability . The -Mix indicates, for each of the pure strategies of player A, the expected success of player B for her mixed strategy. ${\displaystyle q}$ ${\displaystyle (1-q)}$ ${\displaystyle q}$

		Player B:
		forehand	Backhand	q mix
Player A:	forehand	50	80	50q + 80 (1 - q)
	Backhand	90	20th	90q + 20 (1 - q)
	Column maximum	90	80	min =?

If player A plays forehand, the success rate is equal to player B and backhand . The probability is: ${\displaystyle 50q+80(1-q)}$ ${\displaystyle 90q+20(1-q)}$ ${\displaystyle q}$

${\displaystyle 50q+80(1-q)=90q+20(1-q)}$

${\displaystyle 60(1-q)=40q}$

${\displaystyle 60=100q}$

${\displaystyle q=0,6}$ → expected success rate: ${\displaystyle 50*0,6+80(1-0,6)=62}$

Player A was able to increase his maximin from 50% to 62% by mixing pure strategies. Player B was able to reduce her minimax from 80% to 62% by using her mixed strategy. If both players play their optimal mixed strategy against each other, then the maximin of player A corresponds to the minimax of player B and neither can stand up to the other.

criticism

According to some authors, the Min-Max theorem is of little importance in game theory, since this solution concept is only suitable for two-person zero-sum games. In particular, the assumption made by both players in the Min-Max Theorem that the opponent only ever chooses the strategy that is best for himself is assessed as unconvincing. The solution concept is only considered expedient on the assumption that the opposing player strives to maximize his payout and does not make any mistakes, i.e. acts optimally and rationally.

literature

• Avinash K. Dixit, Susan E. Skeath: Games of Strategy , New York [et al. a.], Norton Verlag, 1999, ISBN 0-393-97421-9 .
• Avinash K. Dixit, Barry J. Nalebuff: Game theory for beginners: Strategic know-how for winners , Stuttgart, Schäffer Poeschel Verlag, 1999, ISBN 978-3-7910-1239-1 .
• Christian Rieck: Game Theory: An Introduction , Christian Rieck Verlag, Eschborn, 2006, ISBN 3-924043-91-4 .
• Hans Bühlmann, Hans Loeffel, Erwin Nievergelt: Decision and Game Theory , Springer Verlag, Berlin, 1975, ISBN 3-540-07462-7 .
• Frederick S. Hillier, Gerald J. Liebermann: Operations Research , Oldenbourg Verlag, Munich [u. a.], 1996, ISBN 978-3-486-23987-4 .
• John von Neumann: On the theory of parlor games , Mathematische Annalen No. 100, 1928, pp. 295-320.
• John von Neumann, Oskar Morgenstern: Theory of Games and Economic Behavior , Verlag Princeton Paperback, Princeton, 1990, ISBN 0-691-00362-9 , online at archive.org (PDF; 31.6 MB)
• Manfred J. Holler , Gerhard Illing: Introduction to Game Theory , Berlin [u. a.], Springer Verlag, 2006, ISBN 978-3-540-27880-1 .
• Melvin Dresher : Strategic Games, Theory and Practice , Industrielle Organization Verlag, Zurich, 1961.

See also

• Set by Ky Fan

supporting documents

1. ↑ Hans Bühlmann, Hans Loeffel, Erwin Nievergelt: Decision and Game Theory , Springer Verlag, Berlin, 1975, p. 182.
2. ↑ Manfred J. Holler, Gerhard Illing: Introduction to Game Theory , Berlin [u. a.], Springer Verlag, 2006, p. 55.
3. ↑ Thomas Riechmann: Game Theory , Munich, Vahlen Verlag, 2008, p. 87.
4. ↑ Hans Bühlmann , Hans Loeffel, Erwin Nievergelt: Decision and Game Theory , Springer Verlag, Berlin, 1975, p. 183.
5. ↑ Frederick S. Hillier, Gerald J. Liebermann: Operations Research, Verlag Oldenbourg, 1996, p. 360.
6. ^ John von Neumann: On the theory of parlor games , Mathematische Annalen No. 100, 1928, pp. 295-320 ( Digi journals ).
7. ^ Christian Rieck: Game Theory: An Introduction , Christian Rieck Verlag, Eschborn, 2006, p. 291.
8. ^ Melvin Dresher: Strategic Games, Theory and Practice , Verlag Industrielle Organization, Zurich, 1961, p. 15.
9. ^ Melvin Dresher: Strategic Games, Theory and Practice , Verlag Industrielle Organization, Zurich, 1961, pp. 14-15.
10. ^ Christian Rieck: Game Theory: An Introduction , Christian Rieck Verlag, Eschborn, 2006, p. 291.
11. ^ Melvin Dresher: Strategic Games, Theory and Practice , Verlag Industrielle Organization, Zurich, 1961, p. 15.
12. ^ Avinash K. Dixit, Susan E. Skeath: Games of Strategy , Norton Verlag, New York [u. a.], 1999, pp. 194-198.
13. ^ Christian Rieck: Game Theory: An Introduction , Christian Rieck Verlag, Eschborn, 2006, p. 292.