Game Theory and Nash Equilibrium

Adversarial Search and Minimax assumed strict opposition: whatever one player gains, the other loses. Most strategic situations are not like that. Both parties may prefer cooperation to conflict, yet still fail to achieve it. Game theory studies exactly these cases, and its central solution concept explains a great deal of otherwise puzzling behaviour.

A. The ingredients

A game in normal form is specified by three things:

• the players;
• the strategies available to each;
• the payoff matrix, giving each player's utility for every combination.

A strategy profile is one strategy per player. When each player has a single strategy (rather than a plan contingent on what others do), it is a pure strategy.

B. The prisoner's dilemma

The canonical example, following Russell & Norvig. Alice and Bob are arrested and questioned separately. Each is offered a deal:

• If you testify against your partner and they refuse, you go free and they serve 10 years.
• If you both testify, you each get 5 years.
• If you both refuse, you each serve 1 year on a lesser charge.

Taking utility as negative years served, the payoff matrix is:

C. Solving it by dominance

Alice reasons through Bob's two possible choices:

Suppose Bob testifies. Alice gets $-5$ by testifying and $-10$ by refusing. Testifying is better.

Suppose Bob refuses. Alice gets $0$ by testifying and $-1$ by refusing. Testifying is better again.

Testifying is better in every case, so it is a dominant strategy for Alice. Precisely: strategy $s$ strongly dominates $s'$ if the outcome of $s$ is better than $s'$ for every choice by the other players. ($s$ weakly dominates $s'$ if it is better on at least one profile and no worse on any.)

It is irrational to play a dominated strategy, and irrational not to play a dominant one when it exists. So Alice testifies.

The matrix is symmetric, so Bob's reasoning is identical: he testifies too. When every player has a dominant strategy, the resulting profile is a dominant strategy equilibrium.

The outcome: both testify, both get 5 years.

D. Why it is a dilemma

Look at the bottom-right cell. If both had refused, each would have served 1 year instead of 5. Both players prefer that outcome, and yet rational individual play does not reach it.

The vocabulary for this: an outcome is Pareto optimal if no other outcome is preferred by all players, and Pareto dominated if some other outcome is preferred by all. Here $(-5, -5)$ is Pareto dominated by $(-1, -1)$.

That is the dilemma - individually rational choices produce a jointly worse result. Nothing is irrational about the players; the incentive structure itself drives them there.

E. Nash equilibrium

Dominant strategies are rare. The general concept:

A strategy profile is a Nash equilibrium if no player can improve their own payoff by unilaterally switching strategy, holding the others fixed.

"Unilaterally" is the load-bearing word: each player checks only their own deviation, with everyone else's choices held constant.

Checking (testify, testify): can Alice improve by switching alone? She would move from $-5$ to $-10$. No. Bob, symmetrically, no. It is a Nash equilibrium.

Checking (refuse, refuse): can Alice improve by switching alone? She would move from $-1$ to $0$. Yes. So despite being better for both, it is not an equilibrium - it is unstable, because each player is individually tempted to defect.

Every dominant strategy equilibrium is a Nash equilibrium, but not every Nash equilibrium arises from dominant strategies.

The grid below turns the definition into something you can test by hand: pick any outcome and look for a move that pays one player, alone. Two more games sit beside the dilemma because the dilemma alone runs three separate ideas together - dominance, equilibrium, and efficiency. The stag hunt has equilibria with no dominant strategy anywhere; matching pennies has no pure equilibrium at all, which is exactly the gap the next section closes.

F. Nash's theorem, and mixed strategies

Some games have no pure-strategy equilibrium at all. Matching pennies is the standard example: one player wins on a match, the other on a mismatch, and whatever pure choice you make, your opponent has a profitable deviation, forever.

The resolution is to allow mixed strategies - probability distributions over pure strategies. In matching pennies, each playing heads with probability $1/2$ is an equilibrium: since the opponent's expected payoff is then identical for heads and tails, no deviation helps.

John Nash proved that every finite game has at least one equilibrium once mixed strategies are allowed. The general concept of equilibrium is now called Nash equilibrium in his honour.

The foundational text is von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944), which included the analysis showing that some games require randomised strategies.

Existence is not uniqueness, and equilibrium is not optimality. A game can have many Nash equilibria with different payoffs, which raises the separate problem of which one gets played. And as the prisoner's dilemma shows, an equilibrium can be Pareto dominated - "stable" and "good" are different properties.

G. Verifying the analysis

Small games can be checked exhaustively - worth doing, since dominance and equilibrium arguments are easy to get subtly wrong:

Running it prints testify as dominant for both players, identifies (testify, testify) as the only Nash equilibrium with payoffs $(-5, -5)$, and reports it is Pareto-dominated by ('refuse', 'refuse') - confirming every claim above by exhaustive check rather than assertion.

H. Why this matters beyond puzzles

The dilemma's structure recurs wherever individual incentives diverge from collective ones: shared resources depleted by individually rational use, arms races, price wars, and free-riding on public goods.

It also matters for AI systems directly. When several learning agents share an environment, each optimising its own objective, the outcome is governed by the game's equilibrium structure rather than by any single agent's objective. An agent that is individually well-designed can still contribute to a collectively poor outcome - which is why mechanism design, the problem of designing the rules so that self-interested play produces good outcomes, is a field in its own right.

Key takeaways

• A normal-form game is players, strategies, payoffs; a dominant strategy is best against every opponent choice.
• In the prisoner's dilemma, testifying dominates for both, giving $(-5, -5)$ - while $(-1, -1)$ was available and better for both.
• An outcome is Pareto dominated when all players prefer another; equilibrium outcomes can be Pareto dominated.
• A Nash equilibrium is a profile where no player gains by deviating unilaterally.
• Nash proved every finite game has an equilibrium once mixed strategies are allowed.
• Equilibria need be neither unique nor efficient.

What's next

This closes the Search and Games track. To see the statistical machinery these strategic ideas sit alongside, start from What Is Statistical Learning?; to follow the optimisation thread that trains modern models, see Backpropagation and Gradient Descent.