Hello. Today our topic is multi-stage games. The physical interpretation of multistage games could be chess or any other similar type of games, where players make their moves one after another and in each stage or each time instant they observe the actions of the other players. Theoretically, it is possible to compute all possible outcomes for this class of games, but practically, the computation complexity is too high. On the slide, you can see the example model which could be used to describe the chess. In here, we have several players or to be precise, two players, which make their moves one after another by choosing one of the several alternatives. You can see that in each node or in each state of the game players have full information or perfect information about the state of the game. So they know where they are on the graph and they observe the actions of the other players. Before we define the game, we need to get some or we need to have some preliminary information. We need to define the graph. Graph is a pair (X, F), where X is a finite set of states and F is a mapping from X to X. So F_x is the set of vertexes that are connected to the vertex X. We also need to define the notion of arc. Arc is any pair of vertexes (x,y), where y belongs to the set F_x. So the arc is the interval which connects some point on the graph to one of the next points on the graph. Path is the ordered sequence of arcs. The notions of edge and chain are very similar to arc and path but in case of unordered sequences. On this slide, you can see the graph. We need to define the notion of cycle. The cycle is a finite chain starting in some node and terminating in this same node. For example, if we connect two nodes on the graph in here, which are not already connected, then we can say that this graph has a cycle. We also need to define of when the graph is connected. The graph is called connected if for any two nodes or vertexes, we can construct a chain which connects them. Now we're ready to define the graph, which we will need in order to define the multi-stage game. The tree graph is a finite connected graph without cycles. Why do we need a finite graph? Because we want our game to have a finite number of stages. Why do we need a connected graph? Because we want from the initial state of the graph or for initial vertex to get to any possible vertex of the graph, or to have any possible realization of the game. We need the graph without cycles because we want to have a unique path on the graph which corresponds to some realization of the game. On the slide, you can see the tree graph which we will use for multi-stage games with perfect information. One more thing we need to define is, we need to define the notion of sub-graph. Say the sub-graph G_z, is a tree graph which starts at the position z, and which is defined as a pair (X_z, F). F is the same mapping which we used for the initial graph, and X_z is this set of vertexes from the initial graph, where you can get from the initial vertex z. On the slide, you can see the sub-graph of the initial graph, which starts at the position X_(2.4). On this slide, you can see a list of references where you could get more information about the graph theory and introduction to the multistage games.