Game theory

1 Prisoner’s dilemma

When people talk about game theory they usually mean the class of mathematically formulated two-player “games,” which are typically not the fun type of games, being much shorter and more brutal than Carcassone or whatever.

The most famous one is the Prisoner’s dilemma; you’ve probably run into this one. Alice and Bob, co-conspirators, have been arrested by the cops for a crime they did commit, and they are interviewed separately. They offer them each the same choice: “Inform on your buddy and we will let you off lightly.” Obviously, they want to have as little time in prison; what should they each do?

There are four possible outcomes:

1. Both defect — Alice and Bob both turn informant: They both go to prison for 10 years
2. Bob defects — Bob informs and Alice stays stumm: Alice goes to prison for 10 years, Bob walks free in 1 year
3. Alice defects — Bob stays stumm and Alice informs: Bob goes to prison for 10 years, Alice walks free in 1 year
4. Both cooperate — Alice and Bob both stay stumm: They each go to prison for 2 years on a lesser charge

Label each player’s two actions $C$ (cooperate) and $D$ (defect), and let payoffs be:

where the usual ordering is $$T>R>P>S,2R>T+S.$$ Commonly we set $$T=5,R=3,P=1,S=0.$$

A player’s best response to a fixed opponent strategy is the action that maximises her payoff given what the other does.

• If Bob plays $C$, Alice’s payoffs are $$\{\begin{array}{l}\text{play }C\mapsto R=3,\\ \text{play }D\mapsto T=5,\end{array}$$ so Alice’s best response is $D$.

• If Bob plays $D$, Alice’s payoffs are $$\{\begin{array}{l}\text{play }C\mapsto S=0,\\ \text{play }D\mapsto P=1,\end{array}$$ so Alice’s best response is again $D$.

Because $D$ strictly dominates $C$ (it’s best regardless of the other’s move), defecting is each player’s unique best response.

A Nash equilibrium is a profile of strategies where each player is playing a best response to the others.

• Here, since both players’ best response is always $D$, $(D,D)$ is the unique Nash equilibrium.

An outcome is Pareto‐efficient (PE) if there’s no alternative outcome that makes at least one player strictly better off without making anyone worse off.

• Compare the four outcomes of PD:

  1. $(C,C)$ yields $(3,3)$.
  2. $(D,D)$ yields $(1,1)$.
  3. $(D,C)$ yields $(5,0)$ (asymmetric).
  4. $(C,D)$ yields $(0,5)$.

• $(C,C)$ is Pareto‐efficient: you can’t move to another outcome that raises one player’s payoff without dropping the other’s below 3.

• $(D,D)$ is not Pareto‐efficient: both players could switch jointly to $(C,C)$ and each move from 1→3, so $(C,C)$ Pareto‐dominates $(D,D)$.

• Dominance ⇒ Defection: Because $D$ is each player’s best response to anything, rational play leads to $(D,D)$.

• Pareto efficiency ⇒ Cooperation: In terms of group welfare, $(C,C)$ is strictly better for everybody than $(D,D)$.

This gap—individual incentives pushing towards $(D,D)$ despite a better mutual outcome at $(C,C)$—is the model of that stylised fact we often call a social dilemma.

This is a normal-form game, where the players choose their actions simultaneously and independently. Sequential and partially-observed games are more complicated, and we handle them in extensive form. Those pop up in e.g. causal agents.

2 Iterated games

Iterated games are a class of games where the players play the same game multiple times, and they can use the results of previous rounds to inform their decisions in later rounds. These parallel many interesting dynamics in the real world. See Iterated and evolutionary game theory for a more detailed discussion of iterated games.

3 Stochastic games

In standard game theory, mixed strategies involve probabilistic choices over pure strategies. Stochastic games extend this by incorporating state transitions that evolve over time.

Stochastic games combine game theory with Markov decision processes. Players make decisions in a sequence of states, with each action affecting both immediate payoffs and the probability distribution of future states. Unlike standard mixed strategies where randomisation occurs only over action choices, stochastic games include:

1. Multiple states that change over time
2. Transition probabilities between states
3. State-dependent payoff structures
4. Potentially infinite horizons

In this framework, optimal strategies must account not only for immediate rewards but also for how actions influence the game’s future trajectory. This makes stochastic games particularly suitable for modelling economic competition, resource management, and multi-agent reinforcement learning scenarios where the environment changes in response to players’ actions.

4 Shapley value

The Shapley value is a model of fair distribution of the proceeds of a coalition game. Ends up being interesting for feature selection and collective action problems and model explanation. TBC

5 Bargaining and commitment

See commitment for a discussion of bargaining and commitment in the context of game theory.

6 References