In the section about simultaneous games it was shown how a matrix representation, the Normal Form, can be helpful in analyzing a game. In the sections about sequential games with or without randomness we have learned how to describe the game in Extensive Form, and that there is a very clearly defined solution and (expected) value of the game, that can be computed using backward induction. An important assumption there was perfect information.
However, most games are neither simultaneous nor purely perfect-information-sequential but something between. Some are essentiallly sequential with some moves done in parallel, like WAITING FOR MR PERFECT, some are sequential but lack perfect information like VNM-POKER. Recall that perfect information means that every player when moving is aware of all previous moves of all players. Simultaneous moves can always be rephrased as sequential moves with non-perfect information--- we simply put them into any order without allowing the later moving player knowledge about the move of the player moving first. In this chapter we will see that the description in extensive form can be applied to any game, even with imperfect information.
Similiar to sequential games with perfect information, games with complete but maybe imperfect information can be described by a tree or digraph, a so-called extensive form, as was first shown by Kuhn in 1953 [Kuhn]. We just need one additional concept---the concept of information sets.
The idea is rather simple. We still have the positions/vertices, one start position, and several end positions at which all payoffs of all players are given. Still every non-end position belongs to one player or is a random position (belongs to "Nature", the random player) where a random move will occur. But with non-perfect information a player supposed to move may not know exactly at which position he or she presently is. For instance, the cards are dealed but the player doesn't know the cards in the other player's hands, or another player has moved but our player doesn't know yet how. In such a case, the player to move cannot distingush between several possible positions. Then all these positions in which the game could be at that moment are combined into a so-called information set. There are certain requirements these information sets must obey:Since this is the third and last time we explain the extensive form, let me list carefully all ingredients:
As a first example, let us show how the extensive form of a simultaneous game looks like. Assume we have a two-player simultaneous game with two moves each. The general normal form looks as below:
| B1 | B2 | |
| A1 | A1,1, B1,1 | A1,2, B1,2 |
| A2 | A2,1, B2,1 | A2,2, B2,2 |
Example: PRISONER'S DILEMMA OR STAG HUNT: As our next example we take the following game: There are two players who first simultaneously vote whether they want to play PRISONER'S DILEMMA or STAG HUNT. If both vote for the same game, it is played, otherwise nothing is played, which outcome has a payoff of 0 for both players. Remember that the two games mentioned are simultaneous with the following bimatrix normal forms:
|
|
The extensive form looks as follows:
The same game may have different descriptions, different extensive forms.
For example, VNMPOKER(2,4,2,3) above could also be played in the following way.
First Ann gets her card and decides whether she wants to raise or check.
Only after that, in case of Ann raising, Beth gets her card and decides on her move.
Though described differently, and although it may make a difference for Ann
if she looks Beth straight into the eye before making her decision, whether
Beth has already her card or not, from a mathematical point of view
the game is identical to the one explained above.
Example: LE HER*(2,4): We play with four cards of value 1 and four cards of value 2. Ann and Beth get both randomly a card at which they look without showing it to their opponent. If Ann holds a card of value 1, she can exchange cards with Beth, if she wants to (of course without knowing what card Black holds). Next, if Beth holds a card of value 1, she has the opportunity to exchange her card with a randomly chosen card from the deck. Then both players reveal their cards, and each player wins as much as the value shows.
Versions of this game, which are variants of a rather old game,
has been introduced by Karlin [K 1959, p.100], and have been discussed
and analyzed in [BG 2002].
Actually in the versions discussed in the literature, both players can also swap
cards if they hold the highest value card, but isn't it obvious that they would
not do this? Therefore we may as well forbid this swap of a highest card
from the beginning, as we did in our description. The main purpose for that was to
keep the extensive form small enough.
The extensive form of that game
looks as follows:
The game starts with the random move of dealing the hands.
The pair (1,1) (a "1" to both Ann and Beth) is dealt with
probability 3/14, the same probability as for a (2,2), whereas the combinations (1,2) and (2,1)
each have the probabilities of 4/14. Next it is Ann's turn.
There are four possible positions,
but Ann, not being aware of Beth's card, can not distinguish between the (1,1) and (1,2)
case, nor can she distinguish (2,1) and (2,2). This is indicated by the dashed closed curves,
which indicate the two information sets for Ann. If Ann has a card of value 2, she has two options---
keeping her card or exchanging it with Beth's, otherwise Ann has just one option of keeping her card.
If Ann has exchanged, then Beth knows both Ann's and Beth's card value, so she knows her position
in that case. These two vertices of Beth form their own information sets. If Ann did not exchange, then
Beth knows only her own card, so there are two information sets for Beth in that case, both consisting of
two vertices. Finally there are a few random moves at the end if Beth decides to exchange
with a card from the deck,
with probabilities depending on the values of the six remaining cards in the deck.
The same game may have different descriptions, different extensive forms. In the present example. obviously the positions or information sets where there is only one choice could be eliminated in the extensive form. Doing so we get a slightly smaller .
We get another extensive form by playing the game in slightly different order.
First Ann gets her card and decides whether she wants to exchange.
Only after that, Beth gets her card and decides on her move.
Though described differently, and although it may make a difference for Ann
if she looks Beth straight into the eye before making her decision, whether
Beth has already her card or not, from a mathematical point of view
the game is identical to the one explained above.
Backward induction can be tried in any sequential game, but the procedure is stuck at information sets containing at least 2 vertices. In the example below we can and did already assign values to Ann's decision between A3 and A4, to Ann's decision between A5 and A6, and to the random move. But at Beth's move we are stuck. If Beth decides B1, her payoff could be 3 or 0. If Beth decides B2, her payoff could be 1 or 2. It is difficult to tell what Beth should do and what she would expect at this information set, in particular since Beth can not tell whether any of the two positions is more likely.
Some extensive forms of games can be broken into two "parts" along a vertex such that there is almost no connection between the remaining parts. The part, let's call it the "branch", where the vertex at which we cut forms now the start vertex, can be played without reference to the other part. And the other part, which we call "trunk", where the cut vertex forms now an end vertex, can also played without reference to the missing branch, except that this newly created end vertex does not have payoffs assigned yet. If the trunk game has clearly defined expected values, which is the case if there is for instance just one pure Nash equilibrium, it would be reasonable to assign these expected values as payoffs of that vertex in the trunk.
Breaking a game this way into two smaller games may help since both games have smaller complexity than the total game. Actually, for sequential games with perfect information every vertex could serve as such a cut vertex. If we however have a sequential game with imperfect information, or a nonsequential game reformulated this way, then in addition to the successor/predecessor arcs in the game tree, there are the information sets, which form another type of connection between vertices. When we try to cut a game into two parts, we have to take care that there is no connection between the two parts except at the cut vertex.
In the example PRISONER'S DILEMMA OR STAG HUNT introduced above, there are only two vertices at which we could cut the game into two parts: These are Ann's moves that are not the start move. In this example both these vertices are also the only non-start non-end vertices with one-vertex information set, but we will later see that such vertices x forming its own information set do not allways allow to cut the game at x. We need a second condition, namely that for every successor vertex y of x, all vertices in the same information set as y must also be successors of x. In the different representation of VNMPOKER(2,4,2,3) shown above, the game can not be cut into two parts at all. The two vertices of Ann are both single-vertex information sets, but the two successor sets are connected by information sets.
We call these possible cut vertices, together with all its successors a subgame. Thus a subgame consists of a vertex x and all its successors provided
For our example PRISONER'S DILEMMA OR STAG HUNT, let's look at the PRISONER' DILEMMA subgame.
It has one pure Nash equilibrium, defecting versus defecting, leading to a payoff of 1 to both players.
Since we know that such a single pure Nash equilibrium is very likely to occur for rational play,
in the overall game we could stop already when both have decided to play the PRISONER'S DILEMMA subgame,
since we know what the outcome will be. That means, instead of looking at the overall game,
we can look at the truncated game with payoff of 1 and 1 at (now terminal) vertex where the subgame
has been cut off.
since we know that both players will get a payoff of 1.
For the other other subgame, STAG HUNT, things are a little more complicated,
since we have two pure Nash equilibria---stag versus stag with a payoff of 3 for each player,
or hare versus hare with a payoff of 1 for each. And even though we might think that Z=3, W=3 are the right values
for this subgame, Z=1 and W=1 is also possible. Then, if we cut off this subgame and introduce
payoffs 3,3 or 1,1 at the (now terminal) cut vertex, we arrive at this totally truncated game.
In any case, this game, which is just the first simultaneous round of our two round game, has two Nash equilibria: both players selecting the same game for the second round. We still don't know what payoffs to expect, 1 and 1, or 3 and 3. The uncertainty of the subgame is affecting the overall game.
In the example given below, which occurs on the page Multiple-Round Chicken, there are only two vertices at which we could cut the game into two parts: One vertex is the random vertex, and the other the second vertex for Ann.
The two subgames (to the right), together with the corresponding trunk games (to the left) are displayed below.
Let's demonstrate the method also for our LE HER*(2,4) example, on the second extensive form. We can identify four small subgames, starting at the random move after Beth's swap, and two larger subgames starting at Beth's single-vertex information sets after Ann has swapped. Two of the smaller subgames are also subgames of the larger ones, so in what follows we will focus on the remaining four subgames. All of them are perfect-information sequential games, so they can be analyzed using backward induction. If we cut off these four branches and insert the backward induction values of the subgames at the new terminal vertices (indicated by the white diamonds) we get the truncated extensive form below to the left. If we do the same for the smaller extensive form where the moves with one options have been removed, we arrive at the truncated extensive form below to the right.
Many games are played in rounds, in which all players move simultaneously. It is also possible that these simultaneous moves are followed by a random move in each round. An example is WAITING FOR MR PERFECT discussed above. We reformulate these games as sequential game with nonperfect information, where in each round Ann moves first, followed by Beth and so on, with none of them knowing how the others have moved until the round is finished. Then all information sets for Ann are single-position information sets, and they all start subgames. Therefore the "chopping off subgames" method can be tried.
WAITING FOR MR PERFECT
(two player, two rounds)
In each of the two rounds, one of the awards of value 1, 2, or 3 is offered.
The probabilities for a "1" is 1/2, for a "2" is 1/3, and for a "3" is 1/6.
The players simultaneously either express interest, or not.
The award is given to that player having expressed interest.
If both express interest, the award is given randomly, with equal probability,
to one of them.
A player having obtained already an award can not get another one.
In this example there are two information sets for Ann with identical future but different past. But although the future is identical, the optimal player would play differently in them. Why? Since Ann has learned something from Beth's behavior there? Yes. She knows something about her position, which vertex in the information set she is at. If Ann faces the first information set, she can be quite sure that Beth did not move before, since Beth would very likely have moved B1, assuring Beth a decent payoff of 1. If Ann faces the second information set, every one of the two positions is likely.
...
