Dynamic Games

Dynamic games (extensive-form games) are representations of strategic interaction where the order of moves, the information available at each move, and chance events are explicit. Unlike normal-form games where strategies are chosen simultaneously, an extensive-form game is a labeled rooted tree in which nodes represent decision points, edges represent actions, and terminal nodes produce payoffs. This representation is necessary whenever timing, observation and contingent plans matter.

Formal ingredients: a finite set of players $N$, a finite (or countable) set of histories $H$ where each nonterminal history $h\in H$ has an associated player $P(h)\in N\cup\{c\}$ (where $c$ is chance), a set of available actions $A(h)$ at $h$, information sets that partition decision nodes for imperfect information, a chance probability function for chance nodes, and payoffs defined on terminal histories. A history is a sequence of actions leading from the root; a terminal history has no continuation. In symbols, the extensive form is a tuple $\Gamma=(N,H,P,A,I,u,\pi)$ with $I$ the set of information sets and $\pi$ chance probabilities.

Example (concrete): the ultimatum game in extensive form. Player 1 proposes a split $x\in\{0,1,2\}$ of a pie of size 2; player 2 either Accept (A) or Reject (R). If 2 accepts, payoffs are $(2-x,x)$; if 2 rejects, payoffs are $(0,0)$. Here $H$ are sequences: root, then (propose $x$), then (respond A or R); all nodes are singletons (perfect information). This is a canonical dynamic game with numerically specified payoffs.

Imperfect information and information sets: an information set for player $i$ groups decision nodes between which $i$ cannot distinguish; within an information set the available action set must be identical. For example, in a signaling game (see Section 4) the receiver's move may be made without knowing the sender's type; those nodes form an information set for the receiver.

Why dynamic analysis is different from static (normal-form) analysis: strategies in an extensive form specify contingent plans (an action at every information set), not just a single move. This makes Nash equilibrium sometimes permissive, allowing strategies that use incredible threats to sustain behavior. Subgame perfect equilibrium (SPE) refines Nash by requiring that strategies constitute a Nash equilibrium in every subgame — removing noncredible threats. In games with imperfect information and incomplete information, sequential rationality and belief refinement (e.g., Perfect Bayesian equilibrium) are required to ensure consistency of off-path belief updates.

Relation to prerequisites: In "Repeated Games" we learned how history-dependent strategies sustain cooperation when future payoffs matter; an extensive-form game is a single-shot temporal structure where history matters within one play rather than across repeated plays. In "Bayesian Games" we learned about type spaces and Bayes' rule; Perfect Bayesian equilibrium integrates those ideas into dynamic settings by pairing strategies with beliefs over types at information sets and imposing Bayesian updating wherever possible.

Key notions to keep in mind going forward:

• •Strategy: a complete contingent plan assigning an action to every information set of a player.
• •Subgame: a node and all its descendants that form a tree starting at a single decision node and not cutting any information sets. For example, in the ultimatum game the move after a given proposal is a subgame.
• •Backward induction: a constructive method to compute equilibria in finite games with perfect information by solving subgames from the end.
• •Sequential rationality: given beliefs at each information set, players' actions must maximize expected payoff given those beliefs.

Concrete formula with numbers: suppose at a decision node player $i$ faces two actions $a_1$ and $a_2$, and the payoffs from the subsequent terminal nodes are $u_i(a_1)=3$ and $u_i(a_2)=2$. Then sequential rationality requires choosing $a_1$ because $3>2$. If there is a chance that a downstream chance node yields payoff 3 with probability $0.4$ and payoff $1$ with probability $0.6$, the expected payoff is $0.4\cdot 3+0.6\cdot 1=1.8$; compare numerically to other actions.

This section has set the stage: extensive form = tree + information sets; strategies are contingent plans; SPE and sequential rationality refine Nash to handle sequential moves and beliefs. The remainder will operationalize these notions and show how to solve real problems.

Backward induction is the principal algorithm for solving finite extensive-form games with perfect information. It embodies the idea of sequential rationality: at each decision node, the acting player chooses an action that maximizes her payoff given the continuations (which are already solved because we move from leaves toward the root). The solution produced by backward induction is a subgame perfect equilibrium (SPE).

Definition (subgame): A subgame is a node $h$ such that the tree consisting of $h$ and all its descendants contains only information sets that are subsets of that tree (i.e., no information set is cut). A proper subgame excludes the root if desired. In games of perfect information every node starts a subgame.

Definition (SPE): A strategy profile $s^*$ is a subgame perfect equilibrium if for every subgame $G'$ the restriction $s^*|_{G'}$ is a Nash equilibrium of $G'$. Equivalently, no player can profitably deviate at any history, taking as given that future play follows $s^*$.

The backward induction algorithm (constructive):

1. 1)Identify all terminal nodes and their payoffs.
2. 2)Find a decision node whose immediate successors are terminal. For that node, choose the action that yields the highest payoff for the acting player; record that action and replace the node with the resulting payoff.
3. 3)Repeat: treat the reduced tree similarly until reaching the root. The actions chosen at each step assemble into a strategy profile; this profile is an SPE.

Theorem (Backward induction yields an SPE in finite perfect-information games): For any finite extensive-form game of perfect information, the action choices generated by backward induction define a unique SPE (unique path-of-play under generic payoffs; strategies may be multiple if indifferent choices exist). Proof sketch: solve base nodes to get best responses, then contract these nodes; at each contraction the chosen actions are best replies given future play; since every subgame will be one of these contracted trees, the final profile is a Nash equilibrium in every subgame.

Concrete numeric example (Ultimatum game): Player 1 proposes $x\in\{0,1,2\}$ to split a pie of 2. Player 2 accepts or rejects. Payoffs: accept -> $(2-x,x)$; reject -> $(0,0)$. Backward induction: for each $x$, player 2 compares acceptance payoff $x$ vs rejection payoff $0$; accept iff $x\ge 0$. Numerically: if $x=0$ then accept (0 vs 0 indifferent; assume accept), if $x=1$ accept (1>0), if $x=2$ accept (2>0). Anticipating this, player 1 chooses $x$ maximizing his payoff among those accepted: $x=0$ gives 2 to player 1, $x=1$ gives 1, $x=2$ gives 0. So player 1 picks $x=0$ and player 2 accepts — backward induction yields outcome (2,0). This demonstrates how backward induction eliminates non-credible threats: any rejection by player 2 when offered $x=0$ would be costly to her and thus non-credible.

Numeric illustration of contract step: at nodes after proposals, the best replies for player 2 are A for $x=1$ since $1>0$, and A for $x=0$ assuming tie-break. Replace those nodes by payoffs. Player 1 then chooses the proposal maximizing his payoff across the replaced nodes.

Remark about uniqueness and tie-breaking: if player 2 is indifferent for some offers (e.g., $x=0$ gives 0 either way), multiple SPE strategy profiles can exist (tied responses). However the backward induction path (outcome) is unique if payoffs are generic or if tie-breaking is fixed.

Games with imperfect information: backward induction requires perfect information. If there are non-singleton information sets, the notion of subgame is narrower, and backward induction cannot be applied directly across an information set that gets cut. For such games we need richer equilibrium concepts (sequential rationality plus beliefs).

Numeric example with chance: consider a decision node where the player faces two actions leading to chance node with probabilities $(0.3,0.7)$. If action $a_1$ leads to expected payoff $0.3\cdot 5+0.7\cdot 1=1.5+0.7=2.2$ and $a_2$ leads to payoff 2, the player prefers $a_1$ since $2.2>2.0$.

Backward induction is mechanistic, but it encodes a strong rationality assumption: players will correctly anticipate future rational behavior and use that to plan current moves. In the next section we'll generalize this by making beliefs explicit and imposing sequential rationality in the presence of incomplete information.

When imperfect information or incomplete information is present, backward induction alone is insufficient. We need a refinement that incorporates beliefs about which node within an information set has been reached, and requires that actions maximize expected payoffs given those beliefs. Perfect Bayesian equilibrium (PBE) formalizes this idea by pairing strategies with a belief system and imposing sequential rationality plus Bayes' rule wherever possible.

Assessment: An assessment is a pair $\langle s,\mu\rangle$ where $s$ is a strategy profile and $\mu$ assigns to each information set an internal probability distribution over the nodes in that information set (players' beliefs about where they are). The beliefs must satisfy consistency: on the path of play they should be derived from the strategies and nature's probabilities using Bayes' rule; off the path they must be specified but should be justifiable by some limit argument (Kreps-Wilson consistency) to avoid arbitrary beliefs.

Sequential rationality: Given the assessment $\langle s,\mu\rangle$, at every information set of player $i$ the strategy $s_i$ must specify an action that maximizes $i$'s expected payoff conditional on the belief $\mu$ and given other players' strategies $s_{-i}$. Formally, for each information set $I$ of player $i$ and each available action $a$ at $I$,

where $s_i|_{I\to a}$ denotes the strategy that equals $s_i$ except it plays $a$ at $I$. Numeric example: suppose two nodes in $I$ with beliefs $\mu=(0.6,0.4)$. If action $a$ yields continuation payoffs $4$ and $1$ respectively, expected payoff is $0.6\cdot 4+0.4\cdot 1=2.4+0.4=2.8$. If action $b$ yields payoffs $2$ and $3$, expected payoff is $0.6\cdot 2+0.4\cdot 3=1.2+1.2=2.4$. Sequential rationality requires choosing $a$ (2.8>2.4).

Bayes' rule: On the equilibrium path, beliefs must satisfy Bayes' rule. If $I$ contains nodes $h_1,\dots,h_k$ and prior probabilities on types or chance and conditional probabilities induced by strategies give probability $p(h_j)$ to node $h_j$, then

Numeric example: suppose prior over two types is $\{\theta_1:0.7,\theta_2:0.3\}$ and type-dependent sender plays message $m$ with probabilities $0.5$ and $0.2$ respectively; then the probability of $m$ is $0.7\cdot 0.5+0.3\cdot 0.2=0.35+0.06=0.41$. The receiver's belief that the sender is $\theta_1$ given message $m$ is $0.35/0.41\approx 0.8537$.

Perfect Bayesian equilibrium (PBE): An assessment $\langle s,\mu\rangle$ is a PBE if (i) strategies are sequentially rational given beliefs $\mu$, and (ii) beliefs $\mu$ are Bayes-plausible (obtained from $s$ and prior by Bayes' rule wherever possible). Often one also asks for the stronger consistency requirement in Kreps and Wilson (1982): beliefs must be the limit of Bayes-updated beliefs induced by a sequence of completely mixed strategies converging to $s$.

Examples of PBE concepts:

• •Separating vs. pooling equilibria in signaling games: In separating equilibria different types choose different messages, yielding receiver beliefs that fully reveal type; in pooling equilibria multiple types choose the same message making the receiver's belief a posterior mixing types.
• •Off-path beliefs matter: In signaling games, off-path messages produce a family of possible beliefs for the receiver; only those beliefs that survive a reasonable refinement (e.g., the Intuitive Criterion or D1) are acceptable.

Concrete signaling numeric example: Sender has type H with prob. 0.6 and L with 0.4. If H sends message m_H with prob 1 and L sends m_L with prob 1, receiver upon m_H's occurrence has belief P(H|m_H)=1. If receiver's best response to m_H is action a_H yielding payoff 5 to both sender and receiver when type H, sequential rationality must hold: given belief 1, the receiver chooses a_H if its expected payoff exceeds alternatives. If instead off-path message m' is observed, the receiver's belief is unspecified by Bayes; one can select beliefs that make certain off-path strategies sequentially rational or not.

Comparison to Bayesian Nash equilibrium: In "Bayesian Games" we learned to pair strategies with beliefs about types and use Bayes' rule to compute expected payoffs. PBE refines this by tracking beliefs at each information set reached in the dynamic game and requiring sequential rationality at every information set (not just before play starts). In other words, PBE = strategy profile + belief system + Bayesian updating + sequential rationality.

Refinements and limitations: PBE does not uniquely resolve all off-path belief selection; refinements like the Intuitive Criterion (Cho-Kreps), D1, and divine equilibrium aim to eliminate implausible beliefs. For dynamic games with perfect information PBE reduces to SPE. For games with signaling and incomplete information PBE is the standard workhorse but must be used with care and often supplemented with plausibility refinements.

Dynamic games and equilibrium refinements are central to economic theory and adjacent fields. They connect closely to contract theory, industrial organization, political economy, mechanism design and behavioral economics where timing, observability and private information shape incentives.

1) Bargaining and negotiations. The Rubinstein alternating-offers model is an extensive-form game with infinite horizon; backward induction (in the limit) and subgame perfection identify unique stationary SPE dividing the surplus according to discount factors. Connection to "Repeated Games": the folk-theorem insights about supporting cooperative outcomes via trigger strategies can be read as an infinite-horizon extension of the logic of credible threats — but in finite-horizon bargaining backward induction collapses cooperation. Numeric illustration: with discount factor $\delta_1=0.9,\delta_2=0.8$ the SPE share for player 1 in the stationary solution is $1-\delta_2/(1-\delta_1\delta_2)$ etc. (specific formula derivable from first-order conditions).

2) Industrial organization: entry deterrence and Stackelberg leadership are naturally modeled as extensive-form games. Example: entrant chooses to enter or stay out; incumbent chooses to fight or accommodate. Subgame perfection deletes non-credible threats to fight if fighting is costly. Numeric example: entrant's payoff if enter & fight = $-1$, if enter & accommodate = $1$, if stay out = $0$. If incumbent fighting yields negative payoff to the incumbent, a credible deterrent must be supported by an SPE in which the incumbent's strategy after entering is optimal.

3) Signaling and reputation. In games of incomplete information (we studied "Bayesian Games" earlier), dynamic interactions let a long-run player build a reputation; Perfect Bayesian equilibrium is the language to describe reputation equilibria in repeated or long-lived games. Numeric example: firm with private quality type 'good' or 'bad' chooses quality signal; consumers update with Bayes' rule. The work by Milgrom and Roberts and Rubinstein and others connects PBE to reputational dynamics.

4) Mechanism design and dynamic contracting. When agents take sequential actions or have private information that evolves, designers use PBE concepts to ensure incentive compatibility over time. Example: dynamic moral hazard where actions today affect future information; sequential rationality ensures continuation incentives.

5) Empirical industrial organization and experimental economics. Dynamic game models are used to interpret observed deviations from static Nash predictions — e.g., why incumbents fight entry in data (reputation), or why people reject low offers in ultimatum-like settings (social preferences vs. off-path beliefs). Researchers estimate dynamic structural models by computing (or approximating) SPE or PBE and matching to data.

6) Computational aspects. Solving large extensive-form games (e.g., poker) requires equilibrium refinements and computational tools. Counterfactual regret minimization (CFR) and sequence-form representations exploit the extensive structure to compute approximations to Nash and sequential equilibria. Numeric illustration: in heads-up limit poker the game tree has on the order of $10^{10}$ nodes — computational algorithms operate on compressed sequence-form linear programs.

Bringing prerequisites to bear: In "Repeated Games" we used backward induction in finite-horizon repeated settings and folk-theorem logic in infinite horizons; here, backward induction is the local operation inside the single extensive-form tree. In "Bayesian Games" we learned how to form posteriors; PBE operationalizes that logic at every information set. Downstream, dynamic mechanism design, reputation models, and computational game theory build directly on the formalism of extensive forms and PBE.

Concluding numeric note: Suppose a signaling game where sender types are High (H) with prob 0.7 and Low (L) with 0.3. High sends message m_H costing 2 to produce but yields buyer belief leading to price 10; Low can mimic but net payoff 8-2=6 vs 0 if not. The incentive constraints become inequalities like: For H, 10-2\ge payoff of pooling; if numbers yield 8, inequality numerically holds. Checking such inequalities is the core of constructing separating PBEs.

In sum: dynamic games give precise language and operational tools to analyze sequential strategic interaction. Mastery of backward induction, SPE and PBE — together with the insights from "Repeated Games" and "Bayesian Games" — opens the door to modeling negotiations, signaling, reputation and dynamic contracts at research depth.