Definition: extensive-form representation The extensive-form representation of a game specifies the players in the game when each player has the move what each player can do at each of his or her opportunities to move what each player knows at each of his or her opportunities to move the payoff received by each player for each combination of moves that could be chosen by the players
Definition: extensive-form representation ◼ The extensive-form representation of a game specifies: ➢ the players in the game ➢ when each player has the move ➢ what each player can do at each of his or her opportunities to move ➢ what each player knows at each of his or her opportunities to move ➢ the payoff received by each player for each combination of moves that could be chosen by the players 6
Dynamic games of complete and perfect information Perfect information >All previous moves are observed before the next move is chosen a player knows Who has moved What before she makes a decision
Dynamic games of complete and perfect information ◼ Perfect information ➢ All previous moves are observed before the next move is chosen. ➢ A player knows Who has moved What before she makes a decision 7
Game tree a game tree has a set of a path from a node nodes and a set of edges Xo to xa such that eacn eage connects two nodes(these two X2 nodes are said to be adjacent for any paIr of nodes, X there is a unique path 5 that connects these two nodes an eage connecting nodes X, and X5
Game tree ◼ A game tree has a set of nodes and a set of edges such that ➢ each edge connects two nodes (these two nodes are said to be adjacent) ➢ for any pair of nodes, there is a unique path that connects these two nodes 8 x0 x1 x2 x3 x4 x5 x6 x7 x8 a node an edge connecting nodes x1 and x5 a path from x0 to x4
Game tree a path tromSo A path is a sequence of distinct xo to X4 nodes yi,y yn, yn such that y i and y+ f are adjacent,for n-1. We say that this path is from y, to yn We can also use the sequence X2 of edges induced by these nodes to denote the path The length of a path is the X number of edges contained in the path Example 1: Xo, X2, X3, X, is a path of length 3 Example 2: X4, X1, Xo, X2, X6 is a path of length 4
Game tree ◼ A path is a sequence of distinct nodes y1 , y2 , y3 , ..., yn-1 , yn such that yi and yi+1 are adjacent, for i=1, 2, ..., n-1. We say that this path is from y1 to yn . ◼ We can also use the sequence of edges induced by these nodes to denote the path. ◼ The length of a path is the number of edges contained in the path. ◼ Example 1: x0 , x2 , x3 , x7 is a path of length 3. ◼ Example 2: x4 , x1 , x0 , x2 , x6 is a path of length 4 9 x0 x1 x2 x3 x4 x5 x6 x7 x8 a path from x0 to x4
Game tree There is a special node Xo called the root of the tree which is the beginning of the game The nodes adjacent to xo are successors of Xo.The X2 successors of xo are x,, X2 For any two adjacent nodes the node that is connected to X the root by a longer path is a 5 successor of the other node EXample 3: X, is a successor of xa because they are adjacent and the path from x, to xo is longer than the path from xa to xo 10
Game tree ◼ There is a special node x0 called the root of the tree which is the beginning of the game ◼ The nodes adjacent to x0 are successors of x0 . The successors of x0 are x 1 , x2 ◼ For any two adjacent nodes, the node that is connected to the root by a longer path is a successor of the other node. ◼ Example 3: x7 is a successor of x3 because they are adjacent and the path from x7 to x0 is longer than the path from x3 to x0 10 x0 x 1 x2 x3 x4 x5 x6 x7 x8