Minimax#Minimax theorem
The min-max theorem is a fundamental solution concept in game theory and is sometimes referred to as the main set for 2 -person zero- sum games. The minimization of the opponent's maximum payoff of both players is paramount and is the cause for the emergence of the term min-max theorem. Alternatively, the min-max theorem is referred to in the literature as Maximinlösung. The basis for the dual concept of finding the fact that in zero-sum games minimizing the opponent's maximum payoff ( Minimax ) correspond to both the minimization of one's maximum loss and the maximization of their own minimum payoff ( maximin ).
Game Theoretical Formulation
The main theorem for two -person zero- sum games includes:
In the mixed extension of any two -person zero- sum game with finite ( pure ) strategy spaces A and B there exists a constant V and for every player at least one (mixed ) equilibrium strategy or with which he is able to guarantee an expected payoff of at least V.
For player A, there exists a with and so.
For players with a B exists and such that.
Classification
In the following, assume both players follow the minimax criterion, that is, they choose the mixed strategy that maximizes the minimum expected payoff for themselves (and hence minimizes the maximum expected loss). The theorem guarantees both parties in finite two-person zero-sum games an expected profit V, insofar as they choose the one mixed strategy, which is optimal according to the minimax criterion. This pair of maximin and minimax strategies means that none of the players can improve by unilaterally changing its strategy, the own position. The minimax algorithm which is also based on the minimax strategy is in contrast to the min-max theorem in the sequential game application.
The phrase was first " On the theory of games " proved by John von Neumann in 1928 in his publication.
The resulting strategy combination of the two players forms a saddle point, which is a special case of the Nash equilibrium for two-person zero -sum games. For the determination of this equilibrium strategy in very complex zero-sum games, the linear optimization is used.
Consequently, Player A may, if he plays rationally, depending on the strategy choice of player B, at least the amount expected V and Player B can achieve when he plays rationally, that player also no longer wins A on average, than that amount.
General Procedure
A two -person zero- sum game in matrix form can be represented as follows:
Player A is the row player and player B the column player. The game is viewed from the perspective of player A, where the strategy vector s = (s, s) is the line through s and column s = s is called. In the matrix cell is the payoff u ( s) = - u (s ), so that the payoff of player A corresponds to equal the player B the loss.
Player A first chooses a strategy s ( line ), where it is aware that the opponent will always choose the minimum of the payoffs in the line, the player has A predetermined. Accordingly, Player A is the one strategy s ( line), in which the lines minimum maximum ( maximin strategy ), so that the optimization rule for player A is:
This guarantees him a minimum payout, no matter what player B takes. Player B tries to minimize its losses and chooses a strategy s ( column) that is exactly the reverse condition is satisfied ( minimax rule, minimax strategy ), so that the optimization rule for player B is:
Consequently, he may by his minimax strategy to limit the payment of player A at most equal to this amount, no matter what Player A takes. It is accordingly:
The main theorem for two -person zero- sum games implies that these two optimal strategies have a common value v, so that necessary and sufficient condition for the value v ( balance, saddle point ) is:
Player A may therefore if he plays smart, a minimum payout to expect and Player B can cause he plays smart, that player is not more than the minimum payout to A wins.
Example
In a tennis game will be illustrated in the following, the min-max theorem. In the matrix cells, the payments were replaced by the corresponding success rates for the two players for each of their pure strategies. Player A serves first.
Since the interests of the two players are exactly the opposite, player B will try to pass to the successful return and to minimize the maximum success rate of their adversary ( minimax strategy ). With this knowledge player A is trying to maximize its 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 is 20 The maximum of these minima ( Maximin ) consequently is 50 and guaranteed him the greatest success when he 100% on the forehand plays, in that player B in their own interests as well as possible returned. Player A would choose the strategy forehand. The maximum success rate of player B for each of their strategies is in column 90 forehand and backhand 80 The minimum of these maxima ( Minimax ) is 80 and guarantees you the greatest success, in that players returned A as much as possible in his own interests. Player B would choose the backhand.
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 equilibrium ( saddle point ) in pure strategies, for each of the two players can improve his position by mixing the pure strategies forehand and backhand and weaken the success rate of the opponent, because the correct position is no longer predictable.
The strategy sets that are obtained for the two players out of the mix their pure strategies are considered first from the perspective of player A. He plays forehand with probability p and backhand hence with probability (1 - p). The p- Mix are on for each of the pure strategies of player B, player A the expected success for its mixed strategy.
If player B plays forehand, the success rate is the player A 50p 90 (1-p ) and backhand 80p 20 (1- p). The probability P is:
Now, the strategy sets from the perspective of player B are considered. She plays forehand with probability q and backhand hence with probability (1 - q). The q- Mix are on for each of the pure strategies of player A, the expected success of the player B for their mixed strategy.
If player A plays forehand, the success rate is the player B 50q 80 (1 - q ) and backhand 90q 20 (1 - q). The probability q is:
Player A could increase its Maximin of 50 % to 62 %, consequently, by mixing pure strategies. Player B could reduce their Minimax from 80% to 62 % through the use of their mixed strategy. If both players select their optimal mixed strategy play against each other, as corresponds to the maximin of the player A, player B of the Minimax and no one can be better off compared to the others.
Criticism
Currently, the min-max theorem is a rather low importance attached to, since this solution concept is only suitable for two-person zero -sum games. Likewise, the decision taken in the min-max theorem adoption of both players, the opponent always choose only the best one for strategy, unconvincing. The solution concept is appropriate only under the assumption that the opposing player seeks to maximize his payoff, and no error is produced, that is optimal and rational acts.