Overview
This lecture introduces extensive form games, focusing on game trees, key definitions, and the rules that structures must follow to be considered game trees. It also distinguishes between perfect and imperfect information in extensive form games.
Extensive Form Games and Game Trees
- Extensive form games involve sequential moves by players, represented as a game tree.
- A game tree is a directed graph with nodes (decision points) and branches (actions).
- Nodes at the end of the tree are terminal nodes and show player payoffs.
- Each branch is a one-way connection between nodes, indicating the direction of play.
Key Concepts in Game Trees
- A node is a predecessor if it comes before another node; a successor if it comes after.
- The relationship of predecessor and successor is transitive.
- The game tree starts with exactly one initial node (game start) and ends with one or more terminal nodes (game end).
- A path is a sequence from the initial node to a terminal node via immediate successors.
Rules for Game Trees
- Every node is a successor of the initial node, and the initial node has no predecessor.
- Each decision node (except the initial) has exactly one immediate predecessor.
- Branches from the same node must have different action labels (distinct choices).
- Each information set contains nodes for only one player.
- All nodes in an information set must have the same number of immediate successors and identical action labels.
Information Sets and Perfect Recall
- Information set: a collection of decision nodes where a player cannot distinguish between nodes within the set at the time of decision.
- Perfect recall: players always remember their own past actions within the game.
- Games in this course assume perfect recall.
Perfect vs. Imperfect Information Games
- Perfect information: all information sets are singletons (contain one decision node); every player sees all previous actions.
- Imperfect information: at least one information set contains multiple nodes, so some past actions are hidden.
Key Terms & Definitions
- Extensive Form Game — a game with sequential moves represented by a game tree.
- Game Tree — a directed graph with nodes (decisions) and branches (actions).
- Node — a point in the tree representing a game state or decision.
- Terminal Node — an endpoint in the tree with associated payoffs.
- Initial Node — the root or starting point of a game tree.
- Predecessor/Successor — nodes preceding or following each other in the tree.
- Path — a sequence from the initial node to a terminal node.
- Information Set — a group of nodes between which a player cannot distinguish when making a decision.
- Perfect Recall — the property that players remember all their own decisions.
- Perfect Information — all actions by all players are observed.
- Imperfect Information — some player actions are not observed by others.
Action Items / Next Steps
- Review posted lecture notes on the course website.
- Prepare by reading about strategies and solution concepts in extensive form games.