ISEGORIA / MATH ENCYCLOPEDIA
Game theory: strategy when others choose too
When the outcome depends on what others choose, the best move depends on what you expect them to do, and they reason the same way about you. A Nash equilibrium is a set of choices no one wants to change alone, and it can be good for everyone, bad for everyone, or impossible without randomising. Let strategies spread by success instead of reasoning and the same payoffs drive a population around in cycles. In games of pure conflict, randomising optimally turns into a pair of dual linear programs.
Before you begin: Probability, expected values and linear optimisation
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Two players, two choices, and Nash equilibria
In a two-player game each player picks a row or a column, and the table gives both payoffs. A pair of choices is a Nash equilibrium if neither player gains by switching alone: in the table, a cell that no deviation arrow leaves. Players may also randomise, Row playing the first row with probability p and Column the first column with probability q. Each player’s best reply to the other’s mix is a step function, and the equilibria are exactly where the two best-reply graphs cross; a mixed equilibrium is where each player’s mix leaves the other indifferent. Choose a classic game and drag the strategy point: the streamlines show both players drifting towards better replies.
Worked example. In the stag hunt, hunting stag pays 4 if the other hunts stag too and 0 otherwise, while hunting hare pays a sure 3. Row is indifferent when \(4q=3\), so \(q^*=3/4\), and by symmetry \(p^*=3/4\); at this mixed equilibrium each expects exactly 3, no better than the safe hare. In the battle of the sexes, Row is indifferent when \(3q=2(1-q)\), giving \(q^*=2/5\), and Column when \(2p=3(1-p)\), giving \(p^*=3/5\): both then expect \(6/5\), less than the 2 or 3 of either coordinated outcome.
Watch out. A Nash equilibrium is a stability condition, not a prediction or a recommendation: the prisoner’s dilemma has a unique equilibrium that both players would happily trade for another outcome, and games with several equilibria say nothing about which one will be played. The streamlines are the two-population replicator dynamics, one natural model of learning; other learning rules give other flows with the same equilibria.
Why must a player who randomises in equilibrium be indifferent between the choices they mix?
Because the expected payoff of a mix is the average of the pure payoffs, weighted by the probabilities. If one choice paid strictly more, shifting all the probability onto it would raise the average, so the mix would not be a best reply. That is why each player’s equilibrium mix is pinned down by the other player’s payoffs: it is chosen to make the opponent indifferent, not to help oneself.
2. Replicator dynamics: rock, paper, scissors
Replace reasoning players by a large population in which strategies spread in proportion to their success: the share of a strategy grows at a rate equal to how much better it does than the population average. In rock-paper-scissors every strategy is beaten by another, so the population cycles. Whether the cycles die down depends on a single number, the payoff w of a win when a loss costs 1. If a win is worth more than a loss costs, mixing pays and every orbit spirals in to one third each; if less, the cycles grow into wild booms and crashes; at w = 1 the product of the three shares is conserved and the cycles last for ever. Drag the starting point and change w.
Worked example. Every column of \(A\) sums to \(w-1\), so \(\sum_i(Ax)_i=w-1\), and the average payoff is \(x\cdot Ax=(w-1)(x_1x_2+x_2x_3+x_3x_1)\). Since \((x_1+x_2+x_3)^2=1\ge3(x_1x_2+x_2x_3+x_3x_1)\), the bracket is never negative, so \(\log(x_1x_2x_3)\) rises when \(w>1\) and falls when \(w<1\). Near the centre the motion is a spiral with eigenvalues \((1-w)/6\pm i(w+1)/(2\sqrt3)\): for \(w=0.5\), \(0.083\pm0.433i\), one turn every 14.5 time units, growing by a factor \(e^{0.083\times14.5}=3.3\) per turn.
Watch out. Replicator dynamics model a population, not individuals: shares change by differential success, which can mean imitation, reproduction or reinforcement learning, but no one is optimising. For \(w<1\) the orbits only approach the boundary, never reach it, and a finite population would lose a strategy to chance long before. Side-blotched lizards and some bacterial communities are often cited as natural rock-paper-scissors systems.
Why is the product of the shares conserved exactly when w = 1?
At \(w=1\) the game is zero-sum, \(A=-A^{T}\), so the average payoff \(x\cdot Ax\) is zero for every population and each share changes at the rate \((Ax)_i\). Then \(\frac{d}{dt}\sum\log x_i=\sum(Ax)_i\), the sum of all entries weighted by \(x\), which is \(w-1=0\) because each column of \(A\) sums to zero. A conserved quantity whose level sets are closed curves around the centre forces every orbit to be periodic.
3. Zero-sum games and the minimax theorem
In a zero-sum game one player’s gain is the other’s loss, so Row should assume Column will answer every mix with the column that hurts Row most. Against a fixed p each column gives Row a payoff that is linear in p, and Row can only count on the lowest of these lines, the lower envelope. The best guarantee is the top of that envelope. Column can reason the same way from the other side, and von Neumann’s minimax theorem says the two guarantees meet: there is a single value v that Row can secure and Column can hold Row down to. Finding the two optimal mixes is a pair of dual linear programs. Drag p and watch Column’s best reply change.
Worked example. In the penalty kick, the kicker scores with probability 0.58 kicking left if the keeper dives left, 0.93 kicking right; against a dive right, 0.95 and 0.60. Equating the two dive lines, \(0.93-0.35p=0.60+0.35p\), gives \(p^*=0.33/0.70=0.471\): kick left 47% of the time, and score with probability 0.765 whatever the keeper does. The keeper’s best mix is to dive left and right half the time each and never stay, because staying would concede \(0.83\times0.471+0.80\times0.529=0.814\). These probabilities are illustrative, chosen in the range reported for professional penalties.
Watch out. The theorem needs mixed strategies: in pure strategies the row player’s best guarantee is usually strictly less than the column player’s, as in matching pennies. It also needs the game to be zero-sum; in general games the guarantees can differ and Nash equilibria take over. The graphical method works because Row has only two pure strategies; with more, the envelope becomes a surface over a simplex and the linear program does the work.
Why does the keeper never stay in the middle, even though staying is not the worst choice against either kick?
Because against the kicker’s optimal mix, staying concedes 0.814 while either dive concedes 0.765. A column that lies above the value at \(p^*\) can never be part of an optimal mix: mixing any weight onto it would raise the line the kicker faces above \(v\) somewhere, giving the kicker more than the value. Staying is a good answer to a predictable kicker, but against an optimal one it is dominated by randomising between the dives.