0Trees, frames and games
Often interactions are not simultaneous but sequential. For example, in Chess's game, the two players, White and Black, take turns moving pieces on the board, having full knowledge of the opponent’s (and their own) past moves. Games with sequential interaction are called dynamic games or games in extensive form. This chapter is devoted to the subclass of dynamic games characterized by perfect information, namely the property. Whenever it is her turn to move, a player knows all the preceding moves.
Perfect-information games are represented by means of rooted directed trees.
Definition 3.1.1 A rooted directed tree consists of a set of nodes and directed edges joining them.
• The tree's root has no directed edges leading to it (has indegree 0), while every other node has precisely one directed edge leading to it (has indegree 1).
• There is a unique path (that is, a unique sequence of directed edges) leading from the root to any other node. A node with no directed edges (has outdegree 0) is called a terminal node, while every other node is called a decision node.
• We shall denote the set of nodes by X, the set of decision nodes by D and the set of terminal nodes by Z. Thus, X = D∪Z.
