Minimax

related topics
{math, number, function}
{game, team, player}
{rate, high, increase}
{theory, work, human}
{woman, child, man}
{acid, form, water}

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

Contents

Game theory

In the theory of simultaneous games, a minimax strategy is a mixed strategy which is part of the solution to a zero-sum game. In zero-sum games, the minimax solution is the same as the Nash equilibrium.

Minimax theorem

The minimax theorem states:

For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given player 2's strategy, the best payoff possible for player 1 is V, and (b) Given player 1's strategy, the best payoff possible for player 2 is −V.

Equivalently, Player 1's strategy guarantees him a payoff of V regardless of Player 2's strategy, and similarly Player 2 can guarantee himself a payoff of −V. The name minimax arises because each player minimizes the maximum payoff possible for the other—since the game is zero-sum, he also maximizes his own minimum payoff.

This theorem was established by John von Neumann[1], who is quoted as saying "As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved".[2]

Full article ▸

related documents
Nim
Shuffling
Zero-sum
Supervised learning
Probability distribution
Minimum spanning tree
Parameter
Finite difference
Liouville number
Hypercomplex number
Power set
Positive-definite matrix
Stone–Weierstrass theorem
Yoneda lemma
Cauchy's integral formula
Even and odd permutations
Linear
Blackboard bold
Julia set
Pseudorandom number generator
Polytope
Solvable group
Separation axiom
Max-flow min-cut theorem
Tychonoff space
Line integral
Topology
Mersenne twister
Quine (computing)
LL parser