Game Theory and Decision Analysis

Both halves of this chapter start from the same object: a payoff matrix. Its rows are the decision maker's actions, its columns are the possible states, and each entry is what that action pays in that state. Everything turns on one question about the columns — who chooses which one occurs?

The distinction is not cosmetic. Against nature you may reasonably be optimistic, or assign probabilities, or gamble on a good column appearing — nature will not punish you for it. Against an opponent, optimism is fatal: whatever you hope they will do, they will do the opposite if it hurts you. This is why game theory gravitates to pessimistic, security-first reasoning, and why the two fields, despite sharing a matrix, arrive at such different notions of a good decision.

When the states are governed by nature and no probabilities are available, there is no single "correct" choice — only criteria that encode different attitudes to risk. Five are standard, and a well-posed decision problem should be examined through several, because they can disagree.

The first four read directly off the payoff rows. The fifth needs a transformation worth understanding, because it recurs under risk as opportunity loss. The regret of an action in a state is how much better the best action for that state would have done — what you would kick yourself for, in hindsight, having missed:

Build the regret matrix column by column — subtract each entry from the best entry in its column — then choose the action whose largest regret is smallest. The Hurwicz criterion deserves a second look too: its optimism coefficient \(\alpha \in [0,1]\) is a dial, with \(\alpha = 0\) collapsing to pure maximin and \(\alpha = 1\) to pure maximax. As Example 1 shows, sliding \(\alpha\) can flip the recommended action — a reminder that the "answer" here is a function of temperament as much as of the numbers.

When probabilities can be assigned to the states — from data, models or judgement — the problem moves from uncertainty to risk, and a single dominant criterion emerges: choose the action with the best expected monetary value, the probability-weighted average payoff.

That residual has a name and a use. The expected value of perfect information is what you could gain if an oracle told you the true state before you chose. Compute the expected payoff with perfect information by taking the best action in each state and weighting by probability; the EVPI is the improvement that buys over acting on EMV alone — and it equals the minimum EOL exactly.

When decisions come in sequence — test, then decide; or decide, then observe, then decide again — the natural tool is the decision tree. Square nodes are decisions the analyst controls; circular nodes are chance events governed by probability; branches carry payoffs. The tree is solved by rollback: starting from the leaves, take expectations at chance nodes and maxima at decision nodes, folding the future back to the present until the first decision's value — and the best opening move — is known.

Now the column is chosen by an adversary. A two-person zero-sum game has two players with exactly opposed interests: whatever one wins, the other loses, so a single payoff matrix — read as gains to the row player \(A\) and losses to the column player \(B\) — describes the whole game. \(A\) picks a row to maximise the payoff; \(B\) picks a column to minimise it; and each must choose knowing the other is a rational optimizer.

Security-first reasoning is now forced. Player \(A\), assuming the worst, evaluates each row by its minimum and picks the row whose minimum is largest — the maximin, the most \(A\) can guarantee. Player \(B\), symmetrically, evaluates each column by its maximum and picks the column whose maximum is smallest — the minimax, the most \(B\) can be forced to concede. When these two coincide, the game is settled.

The name is geometric. A saddle point is a mountain pass: the lowest point along the ridge and the highest point along the valley, at once. \(A\) climbing the valley and \(B\) descending the ridge meet exactly there, and neither can do better by moving. Not every game has one, though — and when maximin \(<\) minimax, there is a gap, no pure-strategy equilibrium exists, and the players must randomise, which is the subject of the next section.

Before solving any game, prune it. A row is dominated if some other row is at least as good for \(A\) in every column — \(A\) would never play the worse one, so delete it. A column is dominated if some other column is at least as good for \(B\) (that is, smaller in every row) — delete it too. Dominance often shrinks a large matrix to a \(2\times2\) that can be solved by hand, and never removes an optimal strategy.

When no saddle point survives, no single row is safe: whatever pure strategy \(A\) commits to, \(B\) can exploit it. The escape is to become unpredictable — to play a mixed strategy, choosing rows at random with carefully set probabilities so that \(B\) cannot profit from guessing. The optimal mix makes \(A\)'s expected payoff the same whichever column \(B\) picks; that indifference is exactly what removes \(B\)'s ability to exploit.

The graphical view makes the logic vivid. Plot \(A\)'s expected payoff against \(p\) as \(p\) runs from 0 to 1: against each of \(B\)'s columns it is a straight line, and the two lines cross. To the left of the crossing one column is worse for \(A\); to the right, the other. \(B\), minimising, always pushes \(A\) onto the lower of the two lines — so \(A\)'s guaranteed payoff is the lower envelope, and its highest point is exactly the crossing. The optimal \(p\) is where the lines meet, and its height is the value \(V\).

That every finite two-person zero-sum game has a solution is not obvious — it is a theorem, and a landmark one. Von Neumann's minimax theorem (1928) guarantees that once mixed strategies are allowed, the maximin and the minimax always meet: there is a value \(V\) that \(A\) can guarantee to get and \(B\) can guarantee to hold \(A\) to, simultaneously.

Zero-sum is a special world, though — pure opposition, so one number \(V\) describes it. Most real conflicts are non-zero-sum: the players' interests overlap as well as clash, outcomes can be jointly good or jointly bad, and there is no single "value." The generalising idea is John Nash's, and it is the cornerstone of modern game theory.

The famous cautionary tale is the prisoner's dilemma. Two parties each choose to cooperate or defect; for each, defecting pays more whatever the other does, so "defect" is a dominant strategy and mutual defection is the unique Nash equilibrium — yet both would have been better off cooperating. The equilibrium is stable but collectively poor, which is the whole point: individual rationality and group welfare can diverge, and no player can fix it alone. Example 6 works the numbers; the phenomenon underlies price wars, arms races, and the tragedy of the commons alike.

The chapter's whole territory organises around the two questions of Section 29-1 — who controls the columns, and what you know about them.

Two threads run through it all. The first is that maximin is the safe default whenever the environment might be against you — a mere option against passive nature, an obligation against a rational adversary. The second closes a loop opened much earlier in the course: solving a game is solving a linear program, so the duality theory of Part 2 turns out to be the same mathematics as von Neumann's minimax. The optimization techniques of this book are not a list of separate tricks; under uncertainty and conflict they keep revealing themselves to be one another in different clothing — which is the note Part 7 has been sounding all along, and the one Chapter 30 will close on with real engineering case studies.

Examples 1–2 use one profit matrix, three actions against three states of nature: \(A_1 = (50,40,5)\), \(A_2 = (10,45,55)\), \(A_3 = (30,35,40)\) across states \(S_1,S_2,S_3\).

For decision problems, build the regret matrix carefully — subtract from the column maximum. For games, always check for a saddle point before reaching for mixed strategies, and prune by dominance first. Difficulty rises down the list.