Science Fair Project Encyclopedia
Extensive form game
An extensive form game is a specification of a game in game theory. This form captures the order of play and how equilibria are determined. It specifies:
- the players of a game
- for every player every opportunity they have to move
- what each player can do at each of their moves
- what each player knows for every move
- the payoffs received by every player for every possible combination of moves.
The game is represented by a game tree. Each node (called a decision node) represents every possible stage of the game as it is played. There is a unique node called the initial node that represents the start of the game. Any node that has only one edge connected to it is a terminal node and represents the end of the game (and also a strategy profile). Every non-terminal node belongs to a player in the sense that it represents a stage in the game in which it is that player's move. Every edge represents a possible action that can be taken by a player. Every terminal node has a payoff for every player associated with it. These are the payoffs for every player if the combination of actions required to reach that terminal node are actually played.
The game on the right has two players: 1 and 2. The numbers by every non-terminal node indicate to which player that decision node belongs. The numbers by every terminal node represent the payoffs to the players (e.g. 2,1 represents a payoff of 2 to player 1 and a payoff of 1 to player 2). The labels by every edge of the graph are the name of the action that that edge represents.
The initial node belongs to player 1, indicating that that player moves first. Play according to the tree is as follows: player 1 chooses between U and D; player 2 observes player 1's choice and then chooses between U' and D' . The payoffs are as specified in the tree. There are four outcomes represented by the four terminal nodes of the tree: (U,U'), (U,D'), (D,U') and (U,U'). The payoffs associated with each outcome respectively are as follows (0,0), (2,1), (1,2) and (3,1).
If player 1 plays D, player 2 will play U' to maximise his payoff and so player 1 will only receive 1. However, if player 1 plays U, player 2 maximises his payoff by playing D' and player 1 receives 2. Player 2 prefers 2 to 1 and so will play U and player 2 will play D' . This is the subgame perfect equilibrium.
Infinite Action Space
It may be that a player has an infinite number of possible actions to choose from at a particular decision node. The device used to represent this is an arc joining two edges protuding from the decision node in question. If the action space is a continuum between two numbers, the lower and upper delimiting numbers are placed at the bottom and top of the arc respectively, usually with a variable that is used to express the payoffs. At the top and bottom The infinite number of decision nodes that could result are represented by a single node placed in the centre of the arc. A similar device is used to represent action spaces that, whilst not infinite, are large enough to prove impractical to represent with an edge for each action.
The tree on the left represents such a game, either with infinite action spaces (any real number between 0 and 5000) or with very large action spaces (perhaps any integer between 0 and 5000). This would be specified by elsewhere. Here, it will be supposed that it is the latter and, for concreteness, it will be supposed it represents two firms engaged in Stackelberg competition. The payoffs to the firms are represented on the left, with q1 and q2 as the strategy they adopt and c1 and c2 as some constants (here marginal costs to each firm). The Nash equilibria of this game can be found by taking the first partial derivative of each payoff function with respect to the follower's (firm 2) strategy variable (q2) and finding its best response function, q2(q1) = (5000 - q1 - c2) / 2. The same process can be done for the leader except that in calculating its profit, it knows that firm 2 will play the above response and so this can be substituted into its maximisation problem. It can then solve for q1 by taking the first derivative, yielding q1 * = (5000 + c2 - 2c1) / 2. Feeding this into firm 2's best response function, q2 * = (5000 + 2c1 - 3c2) / 4 and (q1*,q2*) is the Nash equilibrium. For example, if c1=c2=1000, the Nash equilibrium is (2000, 1000).
An advantage of representing the game in this way is that it is clear what the order of play is. The tree shows clearly that player 1 moves first and player 2 observes this move. However, in some games play does not occur like this. One player does not always observe the choice of another (for example, moves may be simultaneous or a move may be hidden). An information set is a set of decision nodes such that:
- Every node in the set belongs to one player.
- When play reaches the information set, the player with the move cannot differentiate between nodes within the information set, i.e. if the information set contains more than one node, the player to whom that set belongs does not know which node in the set has been reached.
In extensive form, an information set is indicated by a dotted line connecting all nodes in that set or sometimes by a loop drawn around all the nodes in that set.
If a game has an information set with more than one member that game is said to have imperfect information. A game with perfect information is such that at any stage of the game, every player knows exactly what has taken place earlier in the game, i.e. every information set is a singleton set. Any game without perfect information has imperfect information.
The game on the left is the same as the above game except that player 2 does not know what player 1 does when he comes to play. The first game described has perfect information; the game on the left does not. If both players are rational and both know that both players are rational and everything that is known by any player is known to be known by every player (i.e. player 1 knows player 2 knows that player 1 is rational and player 2 knows this, etc. ad infinitum), play in the first game will be as follows: player 1 knows that if he plays U, player 2 will play D' (because for player 2 a payoff of 1 is preferable to a payoff of 0) and so player 1 will receive 2. However, if player 1 plays D, player 2 will play U' (because to player 2 a payoff of 2 is better than a payoff of 1) and player 1 will receive 1. Hence, in the first game, the equilibrium will be (U, D' ) because player 1 prefers to receive 2 to 1 and so will play U and so player 2 will play D' .
In the second game it is less clear: player 2 cannot observe player 1's move. Player 1 would like to fool player 2 into thinking he has played U when he has actually played D so that player 2 will play D' and player 1 will receive 3. In fact in the second game there is a perfect Bayesian equilibrium where player 1 plays D and player 2 plays U' and player 2 holds the belief that player will definitely play D. In this equilibrium, every strategy is rational given the beliefs held and every belief is consistent with the strategies played. Notice how the imperfection of information changes the outcome of the game.
In games with infinite action spaces and imperfect information, non-singleton information sets are represented, if necessary, by inserting a dotted line connecting the (non-nodal) endpoints behind the arc described above or by dashing the arc itself. In the Stackelberg game described above, if the second player had not observed the first player's move the game would no longer fit the Stackelberg model; it would be Cournot competition.
It may be the case that a player does not know exactly what the payoffs of the game are or what of type his opponents are. This sort of game has incomplete information. It is represented in extensive form by introducing the notion of nature's choice or God's choice. Consider a game consisting of an employer considering whether to hire a job applicant. The job applicant's ability might be one of two things: high or low. His ability level is random; he is low ability with probability 1/3 and high ability with probability 2/3. In this case, it is convenient to model nature as another player of sorts who chooses the applicant's ability according to those probabilities. Nature however does not have any payoffs. Nature's choice is represented in the game tree by a non-filled node. Edges coming from a nature's choice node are labelled with the probability of the event it represents occurring.
The game on the right has incomplete information. The initial node is in the centre and it is not filled, so nature moves first. Nature selects with the same probability the type of player 1 (which in this game is tantamount to selecting the payoffs in the subgame played), either t1 or t2. Player 1 has distinct information sets for these, i.e. player 1 knows what type he is (this need not be the case). However, player 2 does not observe nature's choice. He does not know the type of player 1; however, in this game he does observe player 1's actions, i.e. there is perfect information. Indeed, it is now appropriate to alter the above definition of perfect information: at every stage in the game, every player knows what has been played by the other players. In the case of complete information, every player what has been played by nature. Information sets are represented as before by broken lines.
In this game, if nature selects t1 as player 1's type, the game played will be like the very first game described, except that player 2 does not know it (and the very fact that this cuts through his information sets disqualify it from subgame status). If nature selects t2 as player 1's type, the difference resides in the payoffs should player 1 play U and player 2 play D' and should player 1 play D and player 2 play U' . The payoffs for (U, D' ) are (1,2) instead of (2,1) and the payoffs for (D, U' ) are (2,1) instead of (1,2). If player 1 is type t1 or type t2, he wants the outcome (D, D' ) so he can receive 3. If player 2 observes type t2 player 1 play D, he is indifferent between U' and D' . If player 2 observes type t1 player 1 play D, he wants to play U' . So, since player 2 does not know player 1's type, he will play U' no matter what if he observes player 1 play D. However, player 1 knows this and if he is type t1, he would prefer (U,D' ) to (D, U' ). Hence, if player 2 observes U he knows he is faced with type t1 player 1 (and will play D' ) and if he observes D knows he is faced with type t2. Through his actions, player 1 has signalled his type to player 2.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details