[Intermediate] — Choosing well when the outcome is uncertain: decision trees, expected value, what information is worth, and attitudes to risk. Then the case where the uncertainty is another player choosing against you: zero-sum games, mixed strategies, and why solving a game is an LP.
Source: [reference] — see the domain note. The numbers in the worked example were checked by hand; the SciPy script itself has not been run yet — see “Still to run” in the index.
Before you start
You need basic probability: conditional probability and Bayes’ rule, and expected value → probability. For the game theory half, you need LP duality → note 05.
After this lesson you will be able to:
- Draw and solve a decision tree by “rolling back” expected values.
- Compute the expected value of perfect information, and of an imperfect forecast using Bayes’ rule.
- Explain why expected value isn’t always the right criterion, and what a utility function changes.
- Find the optimal mixed strategy in a two-player zero-sum game, by hand and as an LP.
Study route: sections 1–4 (decisions under uncertainty), then stop and redo the survey calculation. Then sections 5–6 (games).
The kid version
You’re deciding whether to bring an umbrella. If it rains and you have one, you’re fine; if it rains and you don’t, you’re soaked; if it’s sunny, the umbrella is just a nuisance. Draw a little tree: your choice first, then the weather, then how happy you’d be. Weigh each ending by how likely it is, and pick the choice that comes out best on average. Decision analysis is drawing that tree properly. And if a friend could tell you the weather in advance, the tree also tells you how much that tip is worth.
Where the analogy stops working. The weather doesn’t care what you do. In a game, the other side does — a rival business or an opponent reacts to your choice. Then “the most likely outcome” stops making sense, because the probabilities depend on what you pick, and you need game theory instead.
1. Why this exists
A firm is deciding whether to launch a product. If the market is good, launch earns ₦100 million; if bad, launch loses ₦60 million. Not launching earns nothing. Market research suggests a 60% chance the market is good. And a research agency offers a survey for ₦10 million.
Three questions, all answerable with numbers:
- Should we launch?
- How much would perfect knowledge of the market be worth?
- Is the ₦10 million survey worth buying?
Terms used in decision analysis and game theory
- Decision node: This is a point in a tree where you choose. Drawn as a square.
- Chance node: This is a point where nature “chooses” at random, with known probabilities. Drawn as a circle.
- Expected value: This is also known as the expected monetary value or EMV. This is the probability-weighted average of the outcomes: what you’d get on average if you faced the same gamble many times.
- Rolling back: This is the method of solving a tree from the right-hand end backwards: at chance nodes, take the expected value; at decision nodes, take the best option.
- Expected value of perfect information: This is also known as EVPI. This is the most you should pay to know the uncertain outcome before deciding.
- Utility function: This is a function that converts money into a measure of how much the outcome is actually worth to you, so that attitudes to risk can be included.
- Certainty equivalent: This is the sure amount you’d accept in place of a gamble. If it’s less than the gamble’s expected value, you’re risk-averse.
- Zero-sum game: This is a game where one player’s gain is exactly the other’s loss, so the payoffs always add to zero.
- Pure strategy: This is a single fixed choice — always play the same move.
- Mixed strategy: This is a strategy of choosing moves at random with fixed probabilities.
- Saddle point: This is a cell in a payoff matrix that’s the smallest in its row and the largest in its column. If one exists, both players should play it.
- Nash equilibrium: This is a set of strategies, one per player, where no player can do better by changing theirs alone.
2. Decision trees and rolling back
good (0.6)
┌─────────────── +100
launch ○──┤
┌─────────────┤ bad (0.4)
■ ───┤ └─────────────── −60
│
└──────────────────────────────── 0
don't launch
Roll back. At the chance node, take the expected value:
At the decision node, compare 36 (launch) with 0 (don’t). Launch, with expected value ₦36 million.
Note what the 36 means: not “we’ll earn 36.” We’ll earn either 100 or lose 60. 36 is the long-run average if this were one of many similar bets.
3. What information is worth
Perfect information
Suppose an oracle would tell you the market before you decide. Then:
- If the oracle says “good” (probability 0.6), you launch and earn 100.
- If it says “bad” (probability 0.4), you don’t launch and earn 0.
Expected value with perfect information: .
EVPI = 60 − 36 = ₦24 million. That’s an upper limit: no forecast, survey or consultant is worth more than ₦24 million for this decision. It’s a useful number for killing proposals quickly.
Why information has value at all: it lets you avoid the bad branch. Here, without information you sometimes launch into a bad market and lose 60. The information is worth exactly what it saves you there, on average: .
Imperfect information: the survey
Real surveys aren’t oracles. Suppose the agency’s track record is:
- When the market is good, the survey says “positive” 80% of the time.
- When the market is bad, the survey says “positive” 20% of the time.
To use it, you need the reverse probabilities: given a positive survey, how likely is a good market? That’s Bayes’ rule.
Step 1 — how often is the survey positive?
Step 2 — update the probabilities.
Step 3 — roll back each branch.
- Positive survey: launch is worth . Better than 0, so launch.
- Negative survey: launch is worth . Worse than 0, so don’t.
Step 4 — expected value with the survey (before paying for it):
Expected value of the survey’s information: 43.2 − 36 = ₦7.2 million. The survey costs ₦10 million. Don’t buy it. It’s informative, but not informative enough for this decision.
Pause and check: the survey is worth 7.2, perfect information 24. The survey must always be worth less, because it’s never better than knowing.
4. When expected value isn’t enough
Expected value treats a sure ₦36 million and the gamble “+100 or −60” as equal. Most people and most firms don’t. If losing ₦60 million would bankrupt the firm, the gamble is far worse than its average.
A utility function fixes this by scoring outcomes by their value to the decision-maker, then maximising expected utility. A risk-averse decision-maker has a concave utility function (each extra naira is worth a little less than the last), so losses hurt more than equal gains help.
In practice:
- For small decisions relative to your wealth, expected value is fine. A large company making many similar bets should mostly use it.
- For decisions that could ruin you, use utility, or at least look at the worst case alongside the average.
When you don’t have probabilities at all, three classic rules exist. With the launch payoffs:
- Maximin (pessimist): pick the option whose worst outcome is best. Worst of launch: −60. Worst of don’t: 0. Choose don’t.
- Maximax (optimist): pick the option whose best outcome is best. Launch.
- Minimax regret: for each outcome, “regret” is how much worse you did than the best choice for that outcome. Launch’s worst regret: 60 (if bad, you could have had 0). Don’t’s worst regret: 100 (if good, you missed 100). Choose launch.
They disagree, which is the point: without probabilities, the decision depends on your attitude, and it’s better to say so openly than to pretend otherwise.
5. Two-player zero-sum games
Now the uncertainty is an opponent. Two firms, Row and Column, each choose a strategy. The matrix gives Row’s payoff; Column’s is the negative.
Column: C1 C2
Row: R1 3 −1
R2 −2 1
First, look for a saddle point. Row, being cautious, looks at the worst of each row: R1 → −1, R2 → −2. The best of those is −1 (the maximin). Column looks at the worst for them — the largest of each column: C1 → 3, C2 → 1. The best of those is 1 (the minimax). Maximin −1 ≠ minimax 1, so there’s no saddle point. Any fixed choice can be exploited: if Row always plays R1, Column plays C2 and wins 1.
So both should randomise. Row plays R1 with probability and R2 with . Choose so that Column gets the same result whichever column they choose — then Column can’t exploit Row.
- If Column plays C1, Row’s expected payoff is .
- If Column plays C2, it’s .
- Set them equal: , so .
Row plays R1 with probability 3/7, R2 with 4/7. Row’s expected payoff: whatever Column does.
By the same reasoning for Column ( = probability of C1): gives , and the value is again .
The game’s value is 1/7: Row can guarantee an average of at least 1/7, and Column can hold Row to at most 1/7.
The minimax theorem is LP duality
Von Neumann’s minimax theorem (1928) states that every finite two-player zero-sum game has a value, and both players have mixed strategies that guarantee it.
Row’s problem is an LP: choose probabilities and a value to
In words: maximise the payoff Row is guaranteed, whichever column Column picks. Column’s problem is exactly the dual of Row’s, and strong duality (note 05) says their optimal values are equal. That is the minimax theorem. Dantzig reportedly explained LP to von Neumann in 1947, and von Neumann immediately sketched duality from his game theory.
6. Beyond zero-sum
Most real interactions aren’t zero-sum: both firms can do well, or both badly. Then the concept is the Nash equilibrium — strategies where no one gains by changing alone.
The famous example is the prisoner’s dilemma. Two firms each choose a high or low price. If both price high, each earns 5. If one cuts, the cutter earns 7 and the other 1. If both cut, each earns 2. Whatever the other does, cutting pays more (7 > 5 and 2 > 1). So both cut, and both earn 2 — worse for both than (5, 5). Individually rational choices produce a collectively bad outcome. This structure explains price wars, arms races and overfishing, and why contracts, regulation and repeated relationships exist.
Nash equilibria of non-zero-sum games aren’t LPs in general and can be hard to compute. This is the boundary where operations research hands over to economics.
Worked example — solving the game as an LP
Runnable. SciPy 1.7+.
# game.py — note 11: solve a zero-sum game for the row player with an LP
import numpy as np
from scipy.optimize import linprog
A = np.array([[3, -1],
[-2, 1]]) # payoff to the row player
m, n = A.shape
# variables: p_1..p_m, v. maximise v -> minimise -v
c = np.r_[np.zeros(m), -1]
# for every column j: v - sum_i p_i A[i, j] <= 0
A_ub = np.c_[-A.T, np.ones(n)]
b_ub = np.zeros(n)
A_eq = np.r_[np.ones(m), 0].reshape(1, -1) # probabilities sum to 1
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=[1],
bounds=[(0, None)] * m + [(None, None)], method="highs")
p, v = res.x[:m], res.x[m]
print("row player mixes:", p.round(4), " value:", round(v, 4))
print("column player mixes (from the duals):", (-res.ineqlin.marginals).round(4))uv run --with scipy python game.pyExpected output (, , ):
row player mixes: [0.4286 0.5714] value: 0.1429
column player mixes (from the duals): [0.2857 0.7143]
The column player’s strategy comes free from the duals — one LP solves both sides of the game. Note that must be allowed to be negative ((None, None)), since a game’s value can be.
Common pitfalls and traps
- Reading expected value as a forecast. “Expected ₦36 million” doesn’t mean you’ll get it; you’ll get 100 or −60.
- Using the survey’s accuracy directly. “The survey is 80% accurate, so a positive result means 80% chance of success” is wrong. You need Bayes’ rule, which also uses the 60% starting belief. Here the right answer was 85.7%.
- Paying more than EVPI. No information source is worth more than perfect information.
- Ignoring risk attitude when the stakes are large. Expected value is right for many small repeated bets, and can be disastrously wrong for one big one.
- Playing a fixed strategy without a saddle point. It can be exploited. Equalising the opponent’s payoffs is the defence.
- Treating the other side as nature. A competitor who reacts to you isn’t a chance node.
Check your understanding
- In the launch example, at what probability of a good market does launching stop being worthwhile?
- Why is the survey worth less than perfect information? Can information ever have negative expected value in a decision tree?
- In the game, check that if Row plays (3/7, 4/7) and Column plays C2 for certain, Row’s expected payoff is 1/7.
- A matrix is (payoffs to Row). Is there a saddle point? What should each player do?
After your attempt — answers
- Launch is worth . That’s above 0 when . Below 37.5%, don’t launch.
- The survey sometimes gives the wrong signal, so you sometimes still launch into a bad market or miss a good one; perfect information never does. Free information can’t have negative expected value, because you can always ignore it and do what you’d have done anyway — the worst it can do is not change your decision (value 0).
- Against C2: . ✓ Against C1: . ✓
- Row minimums: 2 and 1, maximin = 2 (R1). Column maximums: 4 and 2, minimax = 2 (C2). They’re equal: the saddle point is (R1, C2) with value 2. Row should always play R1 and Column always C2.
Practice — independent task
- Apply: a firm can build a large plant (₦200m profit if demand is high, −₦80m if low), a small plant (₦90m high, ₦20m low), or nothing (0). . Draw the tree, roll it back, and compute EVPI.
- Bayes: a test-market costs ₦15m and is correct 75% of the time in both directions. Compute its expected value of information and decide whether to buy it.
- Games: use
game.pyto solve rock–paper–scissors (win 1, lose −1, draw 0). Predict the answer first.
Done when: your tree gives a clear decision with its expected value and EVPI, you’ve decided on the test-market with numbers, and game.py confirms your prediction for rock–paper–scissors.
Answers to part 1 and part 3 — after your attempt
Part 1: large ; small ; nothing . Build large, EV 60. With perfect information: high → large (200), low → small (20), EV . EVPI .
Part 3: each player plays each move with probability 1/3; the value is 0.
Before moving on
You’re ready when you can roll back a two-stage tree, compute EVPI and the value of an imperfect forecast with Bayes’ rule, and find a 2×2 game’s mixed strategies by equalising payoffs.
Recap:
- Roll trees back: expected value at chance nodes, best option at decision nodes.
- EVPI caps what any information is worth; imperfect information needs Bayes’ rule.
- Expected value ignores risk; utility puts it back.
- Zero-sum games without a saddle point need mixed strategies, and solving one is an LP whose dual is the opponent’s problem.
Next: Queueing Theory — uncertainty in time: why waiting lines behave the way they do.
Related
- Probability — Bayes’ rule and expected value
- Duality and Sensitivity — the minimax theorem in LP form
- Dynamic Programming — a decision tree with many stages is a stochastic dynamic program
- Data science — where A/B tests are information you pay for
- Operations research map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering