What is a game?
Same machinery as decision theory — but we replace the faceless environment with a roomful of self-interested, rational agents.
Basically we refine the environment: instead of an abstract environment, we have a collection of self-interested and rational agents.
A game is a set of agents O = {o₁,…,oₘ} where each agent oᵢ has a set of actions Aᵢ (its pure strategies), plus a utility function that gives every agent a payoff for each combination of actions.
Agents needn't commit to one action. A strategy lets them randomise:
A pure strategy = commit to one action. A (mixed) strategy sᵢ = a probability distribution over Aᵢ — flip a weighted coin over your actions. A strategy profile s̄ = (s₁,…,sₘ) picks one strategy per agent.
Writing it down: normal form
Just like decision matrices, we lay a (2-player) game in a table — its normal form. Rows = Agent 1's actions, columns = Agent 2's actions, and each cell holds both payoffs: Agent 1, Agent 2.
Normal form flattens the structure: in chess one "action" would be an entire game of moves. When that structure matters you'd use an extensive representation instead — but for this lecture, the table is enough.
A little zoo of games
Three famous 2×2 games cover the whole spectrum from pure cooperation to pure competition.
Driving game — pure coordination
| 1 ↓ / 2 → | Left | Right |
|---|---|---|
| Left | 1, 1 | −1, −1 |
| Right | −1, −1 | 1, 1 |
Two drivers approach each other; they're both happy if they pick the same side. A pure coordination game: every agent gets the same payoff (U(ā)ᵢ = U(ā)ⱼ), so there's no reason to compete — coordination helps everyone.
Matching Pennies — zero-sum
| 1 ↓ / 2 → | Heads | Tails |
|---|---|---|
| Heads | 1, −1 | −1, 1 |
| Tails | −1, 1 | 1, −1 |
Player 1 wants to match, Player 2 wants to mismatch. A zero-sum game: two agents, and in every cell the payoffs sum to zero — one wins exactly what the other loses. Purely competitive. Remember this game — your exam question is a 99-action version of it.
Chess, checkers — pretty much all table games are zero-sum games. And all sports are typically zero-sum: one team wins, the other loses.
Prisoner's Dilemma — a bit of both
| 1 ↓ / 2 → | Cooperate | Defect |
|---|---|---|
| Cooperate | −1, −1 | −4, 0 |
| Defect | 0, −4 | −3, −3 |
Two suspects are interrogated separately. "Cooperate" = confess with your partner; "Defect" = blame them. The most realistic kind of game — it mixes cooperation and competition. (The numbers are arbitrary; only their order matters.) We'll return to its unsettling solution in §4.
Analysing a game: Pareto
In decision theory we hunted for the optimal action. In a game there's a twist.
The optimal strategy of an agent depends also on what the other agents do.
Because of that, there's no single "best." Instead we study solution concepts — sets of outcomes that are interesting in some defined sense. The first takes an outside observer's view.
Profile s̄ Pareto dominates t̄ if it's at least as good for every agent and strictly better for at least one. s̄ is Pareto optimal if nothing Pareto-dominates it. (It's exactly decision theory's dominance, lifted to many agents.)
Here "Pareto" is the name of a person — an Italian mathematician and social scientist; the name of this relationship derives from his.
In a zero-sum game every profile is Pareto optimal — one agent's gain is the other's loss, so no profile beats another for both. So Pareto optimality often can't single anything out. We need a concept that takes the agent's own view.
Nash equilibrium
The most important solution concept in all of game theory — and the one your exam asks you to define.
Start from one agent's point of view. Suppose you knew everyone else's strategies (write them s̄₋ᵢ). Then your problem collapses to ordinary decision-under-risk: just pick what maximises your utility.
Given the others' fixed strategies s̄₋ᵢ, a best response is a strategy that maximises your own payoff: sᵢ* ∈ argmaxsᵢ U(sᵢ, s̄₋ᵢ)ᵢ.
A strategy profile s̄ is a Nash equilibrium when every agent is simultaneously playing a best response to everyone else. Strict if each best response is the unique best; weak if some agent is tied between strategies.
If I select the best response to the others, then I have no reason for changing my decision — as long as the other agents do not change theirs. No incentive to deviate unilaterally.
See it live 🎮
Below is a 2×2 game. Pick a classic, or edit any payoff. Each agent's best responses light up in their colour (P1 blue in each column, P2 magenta in each row); a cell where both are best-responding is a pure Nash equilibrium.
A pure Nash equilibrium = a cell highlighted in both colours at once.
| P1 ↓ / P2 → | Left | Right |
|---|---|---|
| Left | ,NE |
,NE |
| Right | ,NE |
,NE |
Two examples worth memorising
Driving game (try it above): the two Nash equilibria — (Left,Left) and (Right,Right) — exactly coincide with the Pareto-optimal outcomes. Everyone agreeing on a side is stable and good.
Its unique Nash equilibrium is (Defect, Defect) → payoff (−3, −3). But that's Pareto-dominated by (Cooperate, Cooperate) → (−1, −1)! Rational self-interest drives both to an outcome that's worse for everyone. (Switch the Explorer to "Prisoner's Dilemma" and watch only one cell light up green.)
Do they even exist?
Four natural questions: do Nash equilibria always exist, how many are there, why are they interesting, and how do we compute them?
In any game with finitely many agents, each with finitely many actions, at least one Nash equilibrium exists. (The proof uses Brouwer's fixed-point theorem — you won't be asked to prove it.)
But wait — try Matching Pennies in the Explorer: no cell lights up green. There's no Nash equilibrium in pure strategies! How does that square with the theorem?
The theorem promises an equilibrium — just not necessarily a pure one. Matching Pennies has a unique mixed equilibrium: both players play (½ Heads, ½ Tails). Randomising 50/50 makes you unpredictable, so the opponent can't exploit you — neither can do better by deviating.
How many?
Not unique in general. The slides note that once you have two equilibria s̄ and t̄, you can interpolate between them:
Why care, and can we compute it?
Beyond "stability," Nash equilibria have a beautiful interpretation in two-player zero-sum games — and that's also where they're easy to compute.
Recall maximin from Lecture 1 — the pessimist who maximises their worst case. Lift it to games:
In any finite two-player zero-sum game, Nash equilibria coincide with the minimax = maximin strategies. Each player's maximin value equals their minimax value — that common number is the value of the game. So a Nash equilibrium is what you get when both players play as cautious pessimists.
Computation
Zero-sum → easy
The minimax theorem turns it into a linear program. So Nash equilibria of zero-sum games are computable efficiently — the problem is in P.
General → hard
For general games it becomes a non-linear program. Finding a Nash equilibrium is believed intractable: it's PPAD-complete.
Zero-sum: Nash equilibria reduce to linear programming → in P (efficient). General games: believed not efficiently solvable → PPAD-complete. In practice you use solvers that work well on real instances (see Shoham & Leyton-Brown).
Correlated equilibria
A broader notion that's both more cooperative and easier to compute than Nash.
Add a trusted coordination mechanism — a shared random signal with joint distribution π — and let each agent's strategy σᵢ depend on the private signal it sees. It's a correlated equilibrium if no agent can do better by ignoring its recommendation. Every Nash equilibrium is a correlated equilibrium, but not the reverse.
Battle of the Sexes: a couple prefer being together but disagree on where — Ballet or Fight.
| 1 ↓ / 2 → | Ballet | Fight |
|---|---|---|
| Ballet | 2, 1 | 0, 0 |
| Fight | 0, 0 | 1, 2 |
Its mixed Nash equilibrium pays each only 2/3. But add a fair coin both can see: "Heads → both Fight, Tails → both Ballet." Now they always end up together, for an expected payoff of (2 + 1)/2 = 1.5 each — far better than 2/3. The shared coin let them coordinate.
Unlike Nash, correlated equilibria can be found via linear programming. Questions that are hard for Nash (uniqueness, Pareto-optimality, guaranteed payoff) are all in P for correlated equilibria.
The Exam Lab
Lecture 3 is the heart of the DSS exam. The first question below is your actual sample exam — fully worked.
① Define precisely in your own words · ② Apply to his scenario · ③ Decide & motivate. Written exam mandatory (need ≥ 18); optional essay for up to +4; no theorem proofs required — state & use them.
Define, in your own words but as precisely as possible, the notion of a Nash equilibrium. Then: Alice and Bob each bet on a natural number between 1 and 99. Alice wins if the two numbers coincide; Bob wins if they differ. Alice claims there is no Nash equilibrium; Bob claims Alice is wrong. Who is correct? Motivate.
Define a zero-sum game and a pure coordination game. Classify Matching Pennies and the Driving game. What does Pareto optimality tell you in a zero-sum game, and why? Motivate.
Define best response and Nash equilibrium (strict vs weak). For the Prisoner's Dilemma — (C,C)=−1,−1; (C,D)=−4,0; (D,C)=0,−4; (D,D)=−3,−3 — find the Nash equilibrium and explain why it is paradoxical. Motivate.
State Nash's existence theorem and the Minimax theorem. What is the computational complexity of finding a Nash equilibrium in (a) two-player zero-sum games and (b) general games? Discuss.
Define a correlated equilibrium and explain how, in the Battle of the Sexes, a shared fair coin beats the mixed-Nash payoff. How do Nash and correlated equilibria relate? Motivate.
• Define a Nash equilibrium in one precise sentence.
• Why does Matching Pennies have no pure equilibrium — and what is its mixed one?
• Prisoner's dilemma: what's the equilibrium, and why is it a "tragedy"?
• Zero-sum vs coordination vs prisoner's dilemma — one line each.
• Zero-sum vs general games: which is in P, which is PPAD-complete?
• How does a correlated equilibrium let players beat their mixed-Nash payoff?