博弈论笔记 2

Key Topics

• Multi-stage games
• Extensive-form games
• Markov state games

Review of Previous Lecture

In practice, games often involve sequential rather than simultaneous moves:

• Normal-form game: Players move simultaneously
• Extensive-form game: Players move sequentially

While any extensive-form game can be represented as a normal-form game, this conversion fails to preserve sequential properties.
Example: In Stackelberg games, converting to normal-form obscures the leader's explicit strategy revelation to followers.

Information Sets

Key concept: An information set groups nodes indistinguishable to a player.
Example: Penny-matching game

• In normal-form games, simultaneous actions imply players have no information about others' moves.
• Extensive-form representation uses information sets to encode this uncertainty.

Extensive-Form Game Definition

An extensive-form game is defined by:

1. Players: Finite set $N$
2. Game tree:
   • Nodes $T$ with terminal nodes $Z \subseteq T$
   • Payoff functions $u_i: Z \to \mathbb{R}$ for each player $i$
3. Node properties $\forall t \notin Z$:
   • $i(t)$: Player acting at node $t$
   • $A(t)$: Action space at $t$
   • $N(t,a)$: Successor node when action $a$ is taken
   • $h(t)$: Information set containing $t$
4. Perfect information: $h(t) = \{t\}$ (singleton information sets)
5. Subgame: A node with all its descendants in the game tree

Strategies and Equilibria

Pure Strategy Profile

A collection of functions $\{S_t\}_{t \notin Z}$ where each $S_t: h(t) \to A(t)$ maps information sets to actions.

Subgame-Perfect Equilibrium (SPE)

A strategy profile that constitutes a Nash Equilibrium (NE) in every subgame.
Solution method: Backward Induction

Multistage Games and SPE Analysis

Observed-Action Multistage Games

• $N$ players
• Stages $t = 0,1,...,K$
• History $h_t$: Sequence of actions up to stage $t$
• Strategy $S_i(t,h_t)$: Maps history $h_t$ to action $a_i \in A_i(t,h_t)$
• Payoff: $$J_i(S_i, S_{-i}) = \sum_{t=0}^K U_i\left(t, S_i(t,h_t), S_{-i}(t,h_t)\right)$$

SPE Characterization

A strategy profile $\{S_i^*\}_{i=1}^N$ is SPE iff $\forall k \leq K$ and $\forall h_k$:

1. The restricted profile $\{S_i^*|_{t \geq k}\}$ forms a NE for the subgame starting at $h_k$
2. Payoff dominance:$$J_i^{(k)}(S_i^*, S_{-i}^* | h_k) \geq J_i^{(k)}(S_i, S_{-i} | h_k) \quad \forall S_i \text{ feasible}, \forall h_k$$

One-Step Deviation Principle

A strategy profile $\{S_i^*\}$ is SPE if and only if no player can benefit by deviating at exactly one stage-history pair $(t,h_t)$.

Formally, for any alternative strategy $S_i$ differing from $S_i^*$ at only one $(t,h_t)$:

This principle allows verification of SPE by checking local optimality at every decision point.