Must the equilibrium use equal randomization?

No. In the worked example, the column player chooses Left with probability 3/8.

Can the game's value be negative?

Yes. A player's best guaranteed expected payoff can still be below zero.

Is the equilibrium strategy always unique?

No. Some games have several optimal strategies, although their zero-sum equilibrium value is the same for the fixed game.

AI Glossary / Graphs and symbolic AI / Intermediate

Maximin equilibrium

Definition

In the standard two-player zero-sum setting, a maximin equilibrium is a pair of strategies in which each player secures the best worst-case expected payoff available to them. For finite games allowing mixed strategies, these security strategies form a Nash equilibrium. Neither player can improve their expected payoff by changing strategy alone while the other keeps theirs fixed.

What it means

One player's gain is the other player's loss in a zero-sum game. A strategy that guarantees a certain expected payoff against every opponent strategy therefore limits how much the opponent can gain. At equilibrium, the two players' guarantees meet at the game's value.

The strategies may involve randomization rather than a fixed move. Knowing the opponent's probability distribution does not necessarily let a player exploit it. What matters is whether a different response improves expected payoff against that distribution. This entry uses the classical zero-sum meaning associated with the supplied AI glossary context; other research traditions use related terminology for different equilibrium concepts.

How it works

Write the row player's payoff matrix A; the column player's payoff is its negative. For a row strategy p, calculate the smallest expected payoff pᵀAq over column strategies q, then choose p to maximize it. The column player chooses q to minimize the largest row payoff available against q.

The finite-game minimax theorem makes these two values equal when mixed strategies are permitted. A pair of optimal strategies is a saddle point in expected payoff: changing the row strategy cannot improve the row player's payoff against the equilibrium column strategy, and changing the column strategy cannot reduce it against the equilibrium row strategy.

Pure-strategy equilibria need not exist. Randomization can close the gap between the pure maximin and minimax values.

Three practical examples

Game-playing agents: compute a randomized strategy for a small competitive subgame whose rewards are exactly opposed.
Adversarial evaluation: analyze a simplified defender - challenger game, while checking whether the assumed payoff opposition matches the actual objective.
Competitive resource allocation: study a toy allocation contest before introducing cooperation, unequal costs, or multiple players that change the model.

Think of it this way

Think of two players balancing opposite ends of a seesaw, each trying to prevent the other from gaining an advantage. At the balance point, one player cannot improve their position merely by changing their own planned mixture of moves.

The analogy is limited: equilibrium is a property of strategies and expected payoffs, not a guarantee of equal rewards or a peaceful outcome. The game's value can favor one player, and individual rounds can swing sharply.

Worked example

Let the row player choose Up or Down, and the column player Left or Right. Row payoffs are 3 for Up - Left, −1 for Up - Right, −2 for Down - Left, and 2 for Down - Right. Column payoffs are the negatives.

Let p be the probability of Up. Against Left, expected row payoff is 3p−2(1−p)=5p−2. Against Right it is −p+2(1−p)=2−3p. Equating these gives p=1/2 and payoff 1/2. For smaller p, Left gives less than 1/2; for larger p, Right gives less. Thus equal mixing maximizes the worst expected row payoff.

Let q be the probability of Left. Up earns 4q−1 and Down earns 2−4q. Equating them gives q=3/8, again with payoff 1/2. If q moves either way, one row action earns more than 1/2. The equilibrium is therefore row probabilities (1/2,1/2), column probabilities (3/8,5/8), and expected payoffs +1/2 and −1/2. No individual round pays +1/2: that number is an expectation over randomized play.

Illustrative case study

Fictional case: a game studio analyzes a two-move duel before training an AI opponent. Its first bot always uses the move with the better pure worst-case payoff. Players exploit its predictability, so the studio calculates the mixed equilibrium for the small payoff table.

The team implements private random action selection and separately verifies the randomization mechanism. It also notices that tournament bonuses change the larger game's payoffs, so it avoids claiming that the local duel equilibrium solves the entire tournament strategy. This fictional case illustrates a modeling boundary, not a reported result from a real game product.

Common misconceptions and mistakes

Equilibrium does not mean each realized outcome is optimal or fair. A player using a security strategy can still lose an individual round. Revealing the realized random action before the opponent chooses can remove the protection associated with a mixed strategy.

Do not transfer the zero-sum equivalence automatically to general-sum games. There, jointly chosen maximin strategies need not form a Nash equilibrium. Also distinguish a Nash equilibrium from a dominant strategy: an equilibrium strategy is a best response to the particular opposing equilibrium strategy, not necessarily to every possible opponent strategy.

Business use

The concept gives AI teams a precise baseline for resistance to exploitation in well-defined competitive settings. It can help separate a strategy's guaranteed expected performance from its performance against a weak or predictable opponent.

Before using it in a business model, check who the players are, which actions they can take, what they observe, and whether their utilities truly sum to a constant. Many real relationships allow mutual benefit and should not be forced into a zero-sum table. A security strategy may also sacrifice gains available from reliably predicting a particular opponent.

Check your understanding

if the column player uses the worked equilibrium mixture, can the row player improve expected payoff by always choosing Up?

Answer: no. Up gives 4×(3/8)−1=1/2, the same equilibrium value. This particular deviation is equally good, not better, against that fixed mixture.

Related terms

Maximin
Mixed strategy
Pure strategy
Zero-sum games
minimax theorem
Nash equilibrium
zero-sum game
saddle point
security strategy
game value

Learn next

verify all four pure outcomes in the worked matrix and compare the pure-strategy lower and upper bounds. Then derive the mixed strategies from their expected-payoff lines. Study a coordination game afterward to see why general-sum equilibrium reasoning requires different assumptions.

Pure strategy

Sources

Roman Barták, “Decisions with multiple agents,” classical maximin-equilibrium treatment: https://ktiml.mff.cuni.cz/~bartak/ui2/lectures/lecture07eng.pdf. John Baez, “Game Theory, Part 16,” zero-sum maximin/Nash relationship: https://math.ucr.edu/home/baez/games/games_16.html. Relevant primary teaching passages were read. The payoff matrix, calculations, and fictional case are original; scope is explicitly limited to the classical two-player zero-sum concept.

Previous: Maximin Next: Maximum a posteriori