History in a Multistage Game¶

Definition¶

In a multistage game with observed actions and stages $t=0,1,2,\dots$ $0, 1, 2, \dots$ , the history up to stage $t$ is the sequence of action profiles played in the earlier stages,

h^t=(a^0,a^1,\dots,a^{t-1}),\qquad a^k=(a_1^k,\dots,a_n^k)\in A,

with $h^0=\varnothing$ (the empty history) at the start of the game. The set of possible histories at stage $t$ is $H^t$ ; in a repeated game with stage action-profile set $A$ , $H^t=A^{t}$ $A^{t}$ . A pure strategy of player $i$ is a sequence of maps $s_i^t\colon H^t\to A_i$ $A_{i}$ , one action for every history at every stage.

Interpretation¶

The history is the "state" on which players condition: it records who did what, not only payoffs. Because actions are observed by everyone, all players know the same $h^t$ , which is why it is also called the public history.

Tree of histories in the twice-repeated Prisoner's Dilemma: the empty history h^0 branches into the four histories h^1 = (C,C), (C,D), (D,C) and (D,D) before the second stage, each starting a subgame.

The figure draws the twice-repeated Prisoner's Dilemma of the Examples. Each edge is a whole action profile, player 1's action first (blue) and player 2's second (red), because both actions are observed before the next stage. From the empty history $h^0=\varnothing$ the four first-stage profiles lead to the four histories $h^1$ ; each of these, with the second-stage profiles below it (shaded), is a proper subgame. A pure strategy chooses an action at all $1+4=5$ non-terminal histories, hence the $2^5=32$ pure strategies.

A strategy in an extensive-form game must specify an action at every information set, including those never reached. In a multistage game these information sets are exactly the histories, so a strategy must say what to do after histories that the strategy itself rules out, for example after one's own past deviation. This is what makes threats such as punishment phases part of the strategy, and it is where subgame perfection bites.

A common slip is to index the history by the stage just completed. Time starts at $t=0$ $0$ , and $h^t$ is the history up to stage $t$ : the information available when choosing in stage $t$ , so it has $t$ entries, $a^0$ to $a^{t-1}$ .

Key Results¶

Each history $h^t$ (for $t$ up to the last stage) is the starting point of a subgame; $h^0$ gives the whole game, which is a subgame but not a proper subgame.
In a $T$ -period repeated game, with periods $t=0,\dots,T-1$ $1$ , the number of non-terminal histories is $\displaystyle \sum_{t=0}^{T-1}|A|^{t}$ .
The number of pure strategies of player $i$ in a $T$ -period repeated game is $|A_i|$ raised to the number of non-terminal histories.
An outcome path $(a^0,a^1,\dots)$ is one realized history; a strategy profile is not determined by its outcome path, since it also prescribes play after every other history.
A strategy that ignores $h^t$ (the same action after every history) is history-independent.

Examples¶

Counting in the twice-repeated Prisoner's Dilemma. Each player has $A_i=\{C,D\}$ ${C, D}$ , so $|A|=4$ $4$ . The histories are $h^0=\varnothing$ and the four histories $h^1\in\{(C,C),(C,D),(D,C),(D,D)\}$ before the second stage: $1+4=5$ non-terminal histories, hence 5 subgames (the whole game and 4 proper subgames). A pure strategy picks $C$ or $D$ at each of the 5 histories, so each player has $2^5=32$ pure strategies. For three periods there are $1+4+16=21$ histories and $2^{21}$ pure strategies.

A history-dependent rule. "Play $C$ at $h^0$ ; at $h^t$ with $t\ge1$ $1$ , play $C$ if $h^t$ contains only $(C,C)$ , otherwise $D$ " is the grim trigger strategy. At $h^2=((C,C),(D,C))$ it prescribes $D$ .

Prerequisites¶

Sources¶

Game Theory · Week 4

Aliases: History, history of play, public history Keywords: h^t, empty history, past action profiles, history-dependent strategy, repeated Prisoner's Dilemma Symbols: element of, sum

Last updated: 22 October 2026 19:04